Implementing breakpoints

This post is part of my series on implemeting a debugger and covers the following point items the roadmap:

Implement breakpoints at a fixed address and add callbacks to the system.
- At this point start building a proper API

A Debugger API

We’ll start with the subpoint “start building a proper API”. To design an API we write tests to help discover a good API. For a breakpoint test this is what I came up with:

#include <assert.h>
#include <trap.h>
#include <unistd.h>

int g_breakpoint_count = 0;
trap_inferior_t g_inferior = 0;
trap_breakpoint_t g_bp = 0;

void breakpoint_callback(trap_inferior_t inferior, trap_breakpoint_t bp)
{
  assert(inferior == g_inferior);
  assert(bp == g_bp);

  g_breakpoint_count++;
}

int main()
{
  char *argv[1] = { 0 };

  trap_breakpoint_set_callback(breakpoint_callback);
  g_inferior = trap_inferior_exec("./inferiors/hello", argv);
  g_bp = trap_inferior_set_breakpoint(g_inferior, "main");
  trap_inferior_continue(g_inferior);

  assert(g_breakpoint_count == 1);

  return 0;
}

There’s a lot here. Let’s go over it line-by-line.

First of all, I’ve switched to the prefix “trap” while past posts were using “dbg”. Since the name is Trap we’ll use the “trap” prefix.
Lines 1-3 are just basic includes.
Lines 5-7 are global variables. The API I have in mind forces the use of global data in the application. Maybe I should rethink this in the future. There are some new types here.
- trap_inferior_t is a handle of an inferior managed by Trap. It can be used to identify a specific inferior in Trap API calls. This implies that Trap will be able to manage multiple inferiors at once.
- trap_breakpoint_t is the handle of a breakpoint set by Trap in some inferior. It can be used to indentify a specific breakppoint in Trap API calls and callbacks.
Lines 9-15 define a function called breakpoint_callback which Trap will call when a breakpoint is hit. The callback is passed the handle and inferior of the breakpoint that is hit.
- In our test we have only one inferior and one breakpoint so the test callback asserts that the inferior and breakpoint handles match the expected handles.
- It is because of this callback that we need global variables. The callback must match against known handles.
- Finally, breakpoint_callback() increments g_breakpoint_count so that we end up with a count of the number of times the breakpoint was hit.
Line 21 registers breakpoint_callback with Trap as our breakpoint callback. Trap will use the registered callback whenever a breakpoint is hit.
Line 22 executes the inferior. This coresponds to dbg_inferior_exec in test_exec. However, there are some subtle differences
- trap_inferior_exec returns a handle to the newly spawned inferior.
- trap_inferior_exec doesn’t run to completion, instead it leaves the inferior stopped (we’ll see more about this on line 24)
Line 23 sets a breakpoint in the function main.
Line 24 continues execution of the inferior. This is necessary because trap_inferior_exec left the inferior stopped. The reaon we want the inferior stopped is so we have an opportunity to set the breakpoint before the inferior executes anything. trap_inferior_continue() won’t return until the inferior has exited (normally or abnormally).
Line 26 asserts that our breakpoint callback was only called once. This verifies that the breakpoint triggered, called the callback, and that it happened exactly once.
I also had to add this test to the CMakeLists.txt (not shown).

Now of course this test fails and we’ll spend the rest of the post getting it to pass. First we have to get it to build. The first error is:

/home/joseph/src/c/trap/test/test_breakpoint.c:2:18: fatal error: trap.h: No \
such file or directory
 #include <trap.h>

Ok, well we have “debugger.h” but we want to change the name to “trap.h” so let’s rename the file we have. This breaks the build so we need to rename all includes of “debugger.h” as well.

Next errors:

/home/joseph/src/c/trap/test/test_breakpoint.c:9:52: error: unknown type name ‘\
trap_breakpoint_t’
 void breakpoint_callback(trap_inferior_t inferior, trap_breakpoint_t bp)
 
/home/joseph/src/c/trap/test/test_breakpoint.c:7:1: error: unknown type name ‘t\
rap_breakpoint_t’
 trap_breakpoint_t g_bp = 0;

Let’s define these types in “trap.h”. For now they will just be unsigned ints.

typedef int trap_inferior_t;
typedef int trap_breakpoint_t;

Fixed. And the next errors are:

Linking C executable test_breakpoint
CMakeFiles/test_breakpoint.dir/test_breakpoint.c.o: In function `main':
test_breakpoint.c:(.text+0x82): undefined reference to `trap_breakpoint_set_cal\
lback'
test_breakpoint.c:(.text+0x98): undefined reference to `trap_inferior_exec'
test_breakpoint.c:(.text+0xb5): undefined reference to `trap_inferior_set_break\
point'
test_breakpoint.c:(.text+0xcd): undefined reference to `trap_inferior_continue'
collect2: error: ld returned 1 exit status

Of course, these new functions don’t exist. Let’s start with trap_breakpoint_set_callback as it is pretty simple. First we need to declare the prototype in “trap.h”. This is what the test seems to suggest:

typedef	void (*trap_breakpoint_callback_t)(trap_inferior_t, trap_breakpoint_t);
void trap_breakpoint_set_callback(trap_breakpoint_callback_t);

First we have a typedef for that defines the type of the callback function pointer. It’s a function pointer that matches the signature of the test’s breakpoint_callback function. Then, we declare trap_breakpoint_set_callback which just takes a callback function pointer as an argument. Now, this is the declaration of our first API functon so we really ought to document it.

This will be a little bit of a diversion to set up Doxygen. I should have set it up in th last post with the rest of the infrastructure. But instead I’ll do it now.

Doxygen

This was much easier to setup than I thought. I just had to

Install doxygen using apt-get
Look up an example Doxyfile and make a few minor changes
Run doxygen Doxyfile as part of my build to generate the documentation.

My Doxyfile looks like this:

PROJECT_NAME = Trap
PROJECT_BRIEF =	"A lightweight debugger implemented in a	library."
OUTPUT_DIRECTORY = _out/docs
INPUT =	src include
FILE_PATTERNS = *.c *.h
RECURSIVE = yes
OPTIMIZE_OUTPUT_FOR_C =	yes
QUIET =	yes

Most of the options are self explanatory but I’ll explain a few

OPTIMIZE_OUTPUT_FOR_C - I enabled this because Doxygen supports C++ and includes sections for classes and methods. These don’t make sense for Trap.
QUIET - By default Doxygen outputs a lot of information indicating its progress. It also generates warnings about undocumented functions and types. I found the progress information made it harder to see the warnings. The QUIET option disbles the progress information.

Documenting a file

I added the following header to “trap.h”

/**
 * @file trap.h
 * @brief Trap main header file.
 * @author Joseph Kain
 * @date June 18, 2015
 *
 * Trap is a lightweight debugger controlled by the API described in
 * this file.
 * @see http://system.joekain.com/debugger/
 */

Documenting a function

And then I wrote documentation for our first API function, trap_breakpoint_set_callback:

/**
 * @brief Set the global breakpoint callback.
 *
 * @param callback A function that will be called whenever a
 *    breakpoint is encountered.
 */

test_breakpoint

I still have these warnings while compiling “test_breakpoint”

/home/joseph/src/c/trap/test/test_breakpoint.c: In function ‘main’:
/home/joseph/src/c/trap/test/test_breakpoint.c:22:3: warning: implicit declaration of function ‘trap_inferior_exec’ [-Wimplicit-function-declaration]
   g_inferior = trap_inferior_exec("./inferiors/hello", argv);
   ^
/home/joseph/src/c/trap/test/test_breakpoint.c:23:3: warning: implicit declaration of function ‘trap_inferior_set_breakpoint’ [-Wimplicit-function-declaration]
   g_bp = trap_inferior_set_breakpoint(g_inferior, "main");
   ^
/home/joseph/src/c/trap/test/test_breakpoint.c:24:3: warning: implicit declaration of function ‘trap_inferior_continue’ [-Wimplicit-function-declaration]
   trap_inferior_continue(g_inferior);
   ^

Let’s add these to “trap.h” and…

Declare the API

One thing this means is that we will update dbg_inferior_exec to trap_inferior_exec I’ve written up these function declarations and documentation:

/**
 * @brief Create and execute a new inferior processes.
 *
 * @param path The full path to the binary to execute.
 * @param argv A NULL terminated list of command line arguments to
 *   pass to the inferior process.
 *
 * @return Returns a handle for the new inferior.
 *
 * The arguments to this function match those of execv(3)
 */
trap_inferior_t trap_inferior_exec(const char *path, char *const argv[]);

/**
 * @brief Set a breakpoint in `inferior` at `location`
 *
 * `trap_inferior_set_breakpoint` will set a breakpoint in the
 * inferior so that when the breakpoint is encountered the breakpoint
 * callback will be called.
 *
 * @param inferior The handle of the inferior process in which to set the
 *   breakpoint.
 * @param location The location at which to set the breakpoint.
 */
trap_breakpoint_t trap_inferior_set_breakpoint(trap_inferior_t inferior,
                                               char *location);

/**
 * @brief Continue execution of `inferior`.
 *
 * Continue the execution of a stopped process.
 *
 * @param inferior The handle of a stopped inferior process which
 *   should continue execution.
 */
void trap_inferior_continue(trap_inferior_t inferior);

I’ve intentionally been vague when documenting the location parameter for trap_inferior_set_breakpoint. For the purpose of this post the location won’t matter much. But we will develop (and document) a specific syntax for describing breakpoint locations in a later post.

This change caused a regression with test_exec:

/home/joseph/src/c/trap/test/test_exec.c: In function ‘main’:
/home/joseph/src/c/trap/test/test_exec.c:42:3: warning: implicit declaration of \
function ‘dbg_inferior_exec’ [-Wimplicit-function-declaration]
   dbg_inferior_exec("./inferiors/hello", argv);

I’ll need to update the test to use the new function. This means a couple of changes to the implementation as well:

@@ -34,7 +34,7 @@ static void attach_to_inferior(pid_t pid)
   }
 }

-void dbg_inferior_exec(const char *path, char *const argv[])
+trap_inferior_t trap_inferior_exec(const char *path, char *const argv[])
 {
   pid_t result;

@@ -51,4 +51,6 @@ void dbg_inferior_exec(const char *path, char *const argv[])
       break;
     }
   } while (result == -1 && errno == EAGAIN);
+
+  return result;
 }

Currently, I return the pid as the handle. This may change in the future but for now I think it is good enough. As we write more tests we will determine when this needs to change.

Implement the API

trap_breakpoint_set_callback

trap_breakpoint_set_callback is pretty easy to implement. It doesn’t affect the inferior, it just sets up some state for Trap itself. We’ll save the application’s callback in a global variable.

In a new file called breakpoint.c I’ve written:

File Edit Options Buffers Tools C Help
#include <trap.h>

static trap_breakpoint_callback_t g_callback;

void trap_breakpoint_set_callback(trap_breakpoint_callback_t callback)
{
  g_callback = callback;
}

And that’s enough to implement trap_breakpoint_set_callback. The other APIs will be a little more challenging.

trap_inferior_exec

This we did in an earlier post.

trap_inferior_set_breakpoint

This one is a little more involved.

Before we start writing any code I’ll describe how breakpoints work.

On x86 and x86-64 based CPUs there is an instruction call INT which triggers an interrupt. The INT instruction takes an argument which defines the interrupt to be raised. Interrupt 3 is defined to as “trap to debugger” by Intel:

Intel's documentation for INT

When this instruction faults into the kernel the Linux kernel recognizes it as the debuggger trap and sends SIGTRAP to the process. If our debugger is attached then it can intercept the SIGTRAP and leave the inferior stopped for inspection. It is in this way that a debugger implements breakpoints.

Also, note that there is a special 1-byte variant of the INT instruction specifically for INT 3. This way the debugger can write an INT 3 instruction over the start of any instruction, even another 1-byte, instruction.

Other CPUs have similar means for implementing breakpoints.

Now that we know the theory we can reduce it to practice. When trap_inferior_set_breakpoint() is called we will write the INT 3 instruction to the inferior at the right address. Here’s the code:

#include <sys/ptrace.h>
#include <unistd.h>

trap_breakpoint_t trap_inferior_set_breakpoint(trap_inferior_t inferior,
                                               char *location)
{
  const void *target_address = (void *)0x000000000040079d;
  const void *int3_opcode = (void *)0xCC;
  pid_t inferior_pid = inferior;

  ptrace(PTRACE_POKETEXT, inferior_pid, int3_opcode, target_address);

  return 0;
}

By the way, this code is terrible and indicates we need more tests. Here’s what’s going on:

target_address is hardcoded to the address of main the “hello” test inferior. This implies we need to test other inferiors and breakpoints in different functions.
int3_opcode is taken directly from Intel’s manual.
We call ptrace() to write the INT3 instruction to the inferior. The PTRACE_POKETEXT request is used to write to the text or code section of the inferior. We write the value int3_opcode to the inferior’s address space at address target_address
We return 0 as the handle of the breakpoint. Since the test has only one breakpoint this will work. But this implies we need a test with more than one breakpoint.

We have a warning:

/home/joseph/src/c/trap/src/breakpoint.c:13:54: warning: unused parameter ‘locat\
ion’ [-Wunused-parameter]
                         			char *location)
                                                      ^

The warning will remind me that I have hardcoded target_address and need to use the location to lookup a real address.

Warnings are reminders that I need more tests.

trap_inferior_continue

This one is not so hard. In fact we’ve written it already. In inferior_load.c we continue to the inferior after it is initially stopped due to PTRACE_TRACEME. We can do the same like this:

static const pid_t ignored_pid;
static const void *ignored_ptr;

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

  ptrace(PTRACE_CONT, inferior_pid, ignored_ptr, no_continue_signal);
}

There is some duplication here that we should try to refactor away once the test is passing. Both the ptrace call is duplicated as well as the constants ignored_ptr and no_continue_signal.

At this point test_breakpoint builds!

And it crashes:

Test project /home/joseph/src/c/trap/_out
    Start 1: test_exec
1/2 Test #1: test_exec ........................   Passed    0.01 sec
    Start 2: test_breakpoint
2/2 Test #2: test_breakpoint ..................***Exception: Other  0.27 sec
Hello World!
Inferior stopped on SIGTRAP - continuing...
Inferior exited - debugger terminating...
test_breakpoint: /home/joseph/src/c/trap/test/test_breakpoint.c:26: main: Assert\
ion `g_breakpoint_count == 1' failed.

Debug the debugger

The assertion in test_breakpoint tells us that g_breakpoint_count is wrong. This means that the breakpoint callback, breakpoint_callback was called the wrong number of times. This makes sense given that we never actually call the callback from Trap. But the problem goes deeper than this. If we look at trap_inferior_exec() we see that it calls attach_to_inferior() which looks like this:

static void attach_to_inferior(pid_t pid)
{
  while(1) {
    int status;
    waitpid(pid, &status, 0);

    if (WIFSTOPPED(status) && WSTOPSIG(status) == SIGTRAP) {
      printf("Inferior stopped on SIGTRAP - continuing...\n");
      ptrace(PTRACE_CONT, pid, ignored_ptr, no_continue_signal);
    } else if (WIFEXITED(status)) {
      printf("Inferior exited - debugger terminating...\n");
      return;
    }
  }
}

This function does not return until the inferior terminates. Looking back at our test we have:

int main()
{
  char *argv[1] = { 0 };

  trap_breakpoint_set_callback(breakpoint_callback);
  g_inferior = trap_inferior_exec("./inferiors/hello", argv);
  g_bp = trap_inferior_set_breakpoint(g_inferior, "main");
  trap_inferior_continue(g_inferior);

  assert(g_breakpoint_count == 1);

  return 0;
}

So before we even call trap_inferior_set_breakpoint() and trap_inferior_continue() the inferior has already exited. This means we need move the loop from attach_to_inferior() to trap_inferior_continue(). Also, the ptrace() calls in trap_inferior_set_breakpoint() and trap_inferior_continue must have failed but we got no feedback. This tells us that we need to fix up the error checking.

Waiting on the inferior

Now that I think about it, trap_inferior_continue() doesn’t belongs in breakpoint.c it belongs in inferor_load.c (or some other inferior file if we ever write one). I’ll move it and it will make it easier to clean some things up.

Then I modify trap_inferior_continue() so it looks like this:

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

  ptrace(PTRACE_CONT, pid, ignored_ptr, no_continue_signal);
  while(1) {
    int status;
    waitpid(pid, &status, 0);

    if (WIFSTOPPED(status) && WSTOPSIG(status) == SIGTRAP) {
      breakpoint_trigger_callback(inferior);
      ptrace(PTRACE_CONT, pid, ignored_ptr, no_continue_signal);
    } else if (WIFEXITED(status)) {
      return;
    }
  }
}

And I modify attach_to_inferior() so it does much less:

static void attach_to_inferior(pid_t pid)
{
  int status;
  waitpid(pid, &status, 0);

  if (WIFSTOPPED(status) && WSTOPSIG(status) == SIGTRAP) {
    return;
  } else {
    fprintf(stderr, "Unexpected status for inferior %d when attaching\n", pid);
    abort();
  }
}

I’ve added a call in trap_inferior_continue() to a new function called breakpoint_trigger_callback() this function just asks the breakpoint module to trigger the callback.

test_breakpoint still fails.

The first problem is that my use of PTRACE_POKETEXT had the data and addr arguments reversed. I fixed this but found that inferior still crashed with SIGSEGV. This happened because I was setting the breakpoint incorrectly. The problem being that the PTRACE_PEEKTEXT request reads a whole word from the inferior not just a single byte. This means that to set the one-byte 0xCC opcode we need to read a whole word and modify the correct byte within it like this:

void trap_breakpoint_set_callback(trap_breakpoint_callback_t callback)
 {
@@ -17,13 +15,23 @@ void trap_breakpoint_set_callback(trap_breakpoint_callback_t callback)
 trap_breakpoint_t trap_inferior_set_breakpoint(trap_inferior_t inferior,
                                                char *location)
 {
-  const void *target_address = (void *)0x000000000040079d;
-  const void *int3_opcode = (void *)0xCC;
+  const uintptr_t target_address = (void *)0x000000000040079d;
+  const uintptr_t int3_opcode = 0xCC;
   pid_t inferior_pid = inferior;
+  uintptr_t modified_word;
+
+  uintptr_t aligned_address = target_address & ~(0x7UL);
+  uintptr_t target_offset = target_address - aligned_address;
+

-  ptrace(PTRACE_PEEKTEXT, inferior_pid, target_address,
-        &g_original_breakpoint_byte);
-  ptrace(PTRACE_POKETEXT, inferior_pid, target_address, int3_opcode);
+  g_original_breakpoint_word = ptrace(PTRACE_PEEKTEXT, inferior_pid,
+                                     aligned_address, 0);
+  modified_word = g_original_breakpoint_word;
+  modified_word &= ~(0xFFUL << (target_offset * 8));
+  modified_word |= int3_opcode << (target_offset * 8);
+  ptrace(PTRACE_POKETEXT, inferior_pid, aligned_address, modified_word);

   return 0;
 }

Additionally, when the breakpoint is hit we need to restore the original version of the word so that the program has the original set of instructions to execute. We can do this like this with a new function:

void breakpoint_remove(trap_inferior_t inferior, trap_breakpoint_t handle)
{
  const void *target_address = (void *)0x000000000040079d;
  pid_t inferior_pid = inferior;

  ptrace(PTRACE_POKETEXT, inferior_pid, target_address,
         g_original_breakpoint_word);
}

This function is called when trap_inferior_continue() encounters a SIGTRAP. After fixing this I found that the inferior started crashing with SIGILL - Illegal instruction. The reason for this failure is that breakpoint_remove isn’t enough. When the CPU executes the INT 3 instruction it advances the instruction pointer past the instruction. When we restore the original instruction we need to back the instruction pointer up to the beginning of the instruction and execute it properly. We can do that like this:

struct user_regs_struct regs;
ptrace(PTRACE_GETREGS, pid, ignored_ptr, &regs);
regs.rip -= 1;
ptrace(PTRACE_SETREGS, pid, ignored_ptr, &regs);

We use the PTRACE_GETREGS and PTRACE_SETREGS requests to read and write the CPU registers for the inferior. We modify the instruction pointer (in register rip) by backing up over the one-byte INT 3 instruction. Now, the function trap_inferior_continue() looks like this:

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

  ptrace(PTRACE_CONT, pid, ignored_ptr, no_continue_signal);
  while(1) {
    int status;
    waitpid(pid, &status, 0);

    if (WIFSTOPPED(status) && WSTOPSIG(status) == SIGTRAP) {
      struct user_regs_struct regs;

      trap_breakpoint_t bp = breakpoint_resolve(inferior);
      breakpoint_remove(inferior, bp);
      breakpoint_trigger_callback(inferior, bp);

      ptrace(PTRACE_GETREGS, pid, ignored_ptr, &regs);
      regs.rip -= 1;
      ptrace(PTRACE_SETREGS, pid, ignored_ptr, &regs);

      ptrace(PTRACE_CONT, pid, ignored_ptr, no_continue_signal);
    } else if (WIFEXITED(status)) {
      return;
    } else {
      fprintf(stderr, "Unexpected stop in trap_inferior_continue: 0x%x\n", status);
      abort();
    }
  }
}

The function trap_inferior_continue is getting a bit long. Once the tests are passing I should refactor this code. Speaking of tests pasing, test_breakpoint now passes!

    Start 2: test_breakpoint
2/2 Test #2: test_breakpoint ..................   Passed    0.01 sec

But we have regressed test_exec in the process:

    Start 1: test_exec
1/2 Test #1: test_exec ........................***Exception: Other  0.23 sec
Compare aginst:
Compare aginst:
test_exec: /home/joseph/src/c/trap/test/test_exec.c:33: verify_text: Assertion `!"verify_text could not find the specified text"' failed.

The fix here is to fix the test. We’ve changed the behavior of trap_inferior_exec() so that it doen’t automatically start the inferior. We need to add a call to trap_inferior_continue() in test_exec. With this small change to test_exec.c both our tests pass:

@@ -39,7 +39,8 @@ int main()

   int captured = capturefd(STDOUT_FILENO);

-  trap_inferior_exec("./inferiors/hello", argv);
+  trap_inferior_t inferior = trap_inferior_exec("./inferiors/hello", argv);
+  trap_inferior_continue(inferior);

   verify_text(captured, "Hello World!\n");

Wrapping up

In this post we wrote a test for a new set of API calls to set breakpoints and used the test to drive development of the feature. The code we have shows how to implement a breakpoint but its far from production ready. Along the way we made note of a number of things that need to be fixed:

Refactor
- trap_inferior_continue
- Other functions or duplication?
Pay attention to what the warnings are telling us
Write a test that sets a breakpoint in an inferior other than “hello”
Write a test that sets a breakpoint in a function other than “main”
Write a test that sets more than one breakpoint.
Write a test that hits the same breakpoint more than once.
Fix error checking
- Write tests that expect errors?

In the next post we will work through some of these improvements. We will also work on the next item on the roadmap: develop a formal state machine for hanlding events in a comprehensive way.