Handling multiple breakpoints in Trap

In the last post we implemented a state machine to manage breakpoints in Trap. In that post we were left with a small TODO list:

Pay attention to what the warnings are telling us
Write a test that sets more than one breakpoint.

We will address these remaining issues, and more, in this post.

Multiple Breakpoints

The first step is to write a new test. I’ve created test/test_multiple_breakpoints.c with the following:

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

int g_foo_count = 0;
int g_main_count = 0;

trap_inferior_t g_inferior = 0;
trap_breakpoint_t g_bp_main = 0;
trap_breakpoint_t g_bp_foo  = 0;

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

  if (bp == g_bp_main) {
    g_main_count++;
  } else if (bp == g_bp_foo) {
    g_foo_count++;
  }
}

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

  trap_breakpoint_set_callback(breakpoint_callback);
  g_inferior = trap_inferior_exec("./inferiors/loop", argv);
  g_bp_main = trap_inferior_set_breakpoint(g_inferior, (char *)0x0000000000400778);
  g_bp_foo  = trap_inferior_set_breakpoint(g_inferior, (char *)0x000000000040076d);
  trap_inferior_continue(g_inferior);

  assert(g_main_count == 1);
  assert(g_foo_count == 5);

  return 0;
}

This is an adaptation of test_multi_breakpoint.c. The key differences are

Two breakpoints, g_bp_main and g_bp_foo which are initialized on lines 29 and 30.
Two counters, g_foo_count and g_main_count
breakpoint_callback now checks bp against its set of breakpoint handles and advances the appropriate count.
On lines 33 and 34 assert both counts match the expectation.

This test fails:

4/4 Test #4: test_multiple_breakpoints ........***Exception: Other  0.46 sec
Unexpected stop in trap_inferior_continue: 0xb7f

The 0xb in 0xb7f means SIGNAL 11 or SIGSEGV. I haven’t looked at the exact cause here. But if i had to guess I would say that this is a problem removing the breakpoint – Trap can only remove one of the breakpoints due to the fact that the global g_breakpoint gets overwritten.

I will write the code that I belive is needed to make this test pass. That means getting rid of the global breakpoint and then supporting multiple breakpoint_t structures.

In the last post we build the breakpoint_t structure to hold breakpoints:

struct breakpoint_t {
  uintptr_t target_address;
  uintptr_t aligned_address;
  uintptr_t original_breakpoint_word;
};

We also anticipdated handling multiple breakpoints by returning a pointer to a breakpoint_t in

trap_breakpoint_t trap_inferior_set_breakpoint(trap_inferior_t inferior,
                                               char *location)
{
  const uintptr_t target_address = (uintptr_t)location;
  uintptr_t aligned_address = target_address & ~(0x7UL);
  breakpoint_t *bp = &g_breakpoint;

  bp->original_breakpoint_word = ptrace_util_peek_text(inferior,
						       aligned_address);
  bp->target_address = target_address;
  bp->aligned_address = aligned_address;
  
  breakpoint_set(inferior, bp);

  return bp;
}

As I mentioned above, you will note that on line 6 that we use the global g_breakpoint rather than allocating a unique breakpoint_t for each breakpoint. The first change we will make is to remove g_breakpoint. This will cause compilation failures that will point us to all references of g_breakpoint.

One of the errors is:

/home/joseph/src/c/trap/src/breakpoint.c: In function ‘breakpoint_resolve’:
/home/joseph/src/c/trap/src/breakpoint.c:60:11: error: ‘g_breakpoint’ undeclared (first use in this function)
   return &g_breakpoint;

Fixing breakpoint_resolve() is going to be a bit involved as it doesn’t get much context – just the inferior:

static trap_breakpoint_t breakpoint_resolve(trap_inferior_t inferior)
{
  return &g_breakpoint;
}

What is a breakpoint?

The goal of breakpoint_resolve() is to select the right breakpoint_t. But which one is the right one? Well, what we know is that the inferior encountered one of our INT 3 instructions and in response the kernel raised SIGTRAP. But how do we know which breakpoint it was? This comes down to the question: “what uniquely identifies a breakpoint?” And the answer to this question is that a breakpoint should be uniquely identified by the target_address. That is,

When we write an INT 3 we write it to a target adress.
We would never need to write an INT 3 to a single address more than once.

We should take note, that we need a test for #2.

TODO:

Pay attention to what the warnings are telling us
Write a test that sets more than one breakpoint.
Write a test that sets two breakpoints at the same address.

Anyway, we need to use the fact that a breakpoint should be uniquely identified by the target_address to implement breakpoint_resolve(). To do this, we need to maintain some kind of collection of breakpoint_t structures and then breakpoint_resolve() can search through the collection to find the one that matches the instruction pointer.

Step 1 is to create a collection. For simplicity we will use an array of breakpoints. This is simple but potentially inefficient and incomplete. Effectively, this means we will end up replacing a single global breakpoint with a global array of breakpoints:

typedef struct breakpoint_t breakpoint_t;

-breakpoint_t g_breakpoint;
+#define MAX_BREAKPOINTS 100
+static int g_num_breakpoints;
+static breakpoint_t g_breakpoints[MAX_BREAKPOINTS];

Allocating breakpoints

Then, we need to allocate breakpoints from the array and use them in trap_inferior_set_breakpoint():

+static breakpoint_t *breakpoint_allocate()
+{
+  int index = g_num_breakpoints;
+  g_num_breakpoints++;
+
+  assert(index < MAX_BREAKPOINTS);
+  return &g_breakpoints[index];
+}
+
 trap_breakpoint_t trap_inferior_set_breakpoint(trap_inferior_t inferior,
                                                char *location)
 {
   const uintptr_t target_address = (uintptr_t)location;
   uintptr_t aligned_address = target_address & ~(0x7UL);
-  breakpoint_t *bp = &g_breakpoint;
+  breakpoint_t *bp = breakpoint_allocate();

Now, breakpoint_allocate() is not graceful when running out of breakpoints. The code is currently simple but not robust. But this should be good enough to pass our test. I don’t expect to be able to fix this soon so I should file an issue on GitHub to remind myself to fix this. I won’t actually file this now because the code isn’t committed yet, instead I’ll add this to the TOOD list

TODO:

Pay attention to what the warnings are telling us
Write a test that sets more than one breakpoint.
Write a test that sets two breakpoints at the same address.
File a GitHub issue: breakpoint_allocate needs to be more graceful

Resolving breakpoints

Next, we need to implement breakpoint_resolve(). The first thing is to lookup the current instruction pointer. We already have a function ptrace_util_set_instruction_pointer() so it makes sense to write a ptrace_util_get_instruction_pointer() and then call it from breakpoint_resolve().

uintptr_t ptrace_util_get_instruction_pointer(pid_t pid)
{
  uintptr_t offset = offsetof(struct user, regs.rip);
  return ptrace(PTRACE_PEEKUSER, pid, offset, ignored_data);
}

Now we can write breakpoint_resolve():

static trap_breakpoint_t breakpoint_resolve(trap_inferior_t inferior)
{
  uintptr_t ip = ptrace_util_get_instruction_pointer(inferior) - 1;
  return find_breakpoint_with_target_address(ip);
}

Now we just need to write find_breakpoint_with_target_address() with a simple linear search:

static breakpoint_t *find_breakpoint_with_target_address(uintptr_t address)
{
  for (int i = 0; i < g_num_breakpoints; i++) {
    if (g_breakpoints[i].target_address == address) {
      return &g_breakpoints[i];
    }
  }

  assert(!"Could not find breakpoint with target address");
}

And with this change the test passes! And not only that there are no warnings left in breakpoint.c.

Refactor

We can make a small clean-up in step_over_breakpoint() by using ptrace_util_get_instruction_pointer() instead of ptrace_util_get_regs(). This doesn’t save much code but makes our intent clearer.

@@ -98,15 +98,15 @@ static void breakpoint_remove(trap_inferior_t inferior,

 static void step_over_breakpoint(trap_inferior_t inferior)
 {
-  struct user_regs_struct regs;
+  uintptr_t ip;
   pid_t pid = inferior;

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

-  ptrace_util_get_regs(pid, &regs);
-  ptrace_util_set_instruction_pointer(pid, regs.rip - 1);
+  ip = ptrace_util_get_instruction_pointer(pid);
+  ptrace_util_set_instruction_pointer(pid, ip - 1);

   ptrace_util_single_step(pid);
 }

With our test passing and our code cleaned up we’ve reduced our TODO list to:

Write a test that sets two breakpoints at the same address.
File a GitHub issue: breakpoint_allocate needs to be more graceful

We’ll work on passing the proposed test next.

Write a test that sets two breakpoints at the same address

I started by writing this test (test_duplicate_breakpoint):

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

trap_inferior_t g_inferior = 0;
trap_breakpoint_t g_bp_one = 0;
trap_breakpoint_t g_bp_two = 0;

void breakpoint_callback(trap_inferior_t inferior, trap_breakpoint_t bp)
{
  /* Nothing to do */
}

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

  trap_breakpoint_set_callback(breakpoint_callback);
  g_inferior = trap_inferior_exec("./inferiors/loop", argv);
  g_bp_one = trap_inferior_set_breakpoint(g_inferior, (char *)0x000000000040076d);
  g_bp_two = trap_inferior_set_breakpoint(g_inferior, (char *)0x000000000040076d);
  trap_inferior_continue(g_inferior);

  return 0;
}

But, I wasn’t sure what to assert. The problem is that this is really an API design issue revoling around the question: what should happen when a duplicate breakpoint is set? I can think of a few of possiblities:

Trap aborts with an error message
Trap succeeds and returns the same trap_breakpoint_t for both breakpoints.
Trap creates to distinct trap_breakpoint_t structures for each breakpoint.

Option 3 violates a point we described in defining how to uniquely identify a breakpoint. So Trap should not support this option.

Option 1 seems rather ungraceful. It could also be a little difficult for a client application once we support more elaborate breakpoint locations. For example, you could imagine for this inferior:

int foo()
{
  return 5;
}

int main()
{
  int i;
  for (i = 0; i < 5; i++) {
    foo();
  }

  return 0;
}

that an application could set a breakpoint in “main” and on line 8 and these could end up being the same target address. But it would be difficult for the application to know this.

This leaves us with option 2. Option 2 seems very nice from the application’s point of view. The one issue here is subtle: suppose the application sets two breakpoints at the same address and then deletes the breakpoint. Now, at the moment there is no API to delete a breakpoint, but we will need one at some point (add to TODO list). So, what should happen in this case? Does the application need to remove the breakpoint twice before it is really removed, or only once?

I think the same argument against option 1 applies in favor of duplicate break points require redundant deletes. That is, if the application has no way of knowing when it is creating duplicate breakpoints then it also has now way of knowing when it would need to issue redundant deletes.

That means that in order to test this properly we need to test functionality to delete a breakpoint. As I went to write this test I began with:

@@ -20,6 +20,8 @@ int main()
   g_bp_one = trap_inferior_set_breakpoint(g_inferior, (char *)0x000000000040076
   g_bp_two = trap_inferior_set_breakpoint(g_inferior, (char *)0x000000000040076

+  assert(g_bp_one == g_bp_two);

and then I asked myself if this new assert() was a good idea or not. I decided it was not. In thinking through this I realized there is another option. My thinking is that the fact that the two returned trap_breakpoint_t values are equal is an implementation detail.

Whenever I think something is an implementation detail I try to think of an alternative implementation. This helps me build better abstractions.

So what other possible implementation could we have here? Well, first of all g_bp_one and g_bp_two would have to be different. This would go back to option 3 which I had discarded based on our assumption about uniquely identifying breakpoints. But, I thought what if our g_breakpoints just contained multiple breakpoints with the same target address. This would break the search function we have built. But, an alternative implementation could do an exhaustive search for all breakpoints with matching target addresses and trigger the callback for all of them. This would mean multiple callbacks, one for each of the duplicated breakpoints. This is actually more in line with the argument I’ve been making. For example, supposed we take our main() vs. line 8 hypothetical then what does the application expect in the handler function? I think I would want to be able to write

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

  if (bp == g_bp_main) {
    do_main_action();
  } else if (bp == g_bp_line_8) {
    do_line_8_action();
  }
}

and expect both do_main_action() and do_line_8_action() to be called.

Ok, so enough theorizing, let’s write the test and let it drive the implementation. Here’s the test:

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

trap_inferior_t g_inferior = 0;
trap_breakpoint_t g_bp_one = 0;
trap_breakpoint_t g_bp_two = 0;
int g_bp_one_count;
int g_bp_two_count;

void do_bp_one(trap_inferior_t inferior)
{
  g_bp_one_count++;
  if (g_bp_one_count == 1) {
    trap_inferior_remove_breakpoint(inferior, g_bp_one);
  }
}

void do_bp_two()
{
  g_bp_two_count++;
}

void breakpoint_callback(trap_inferior_t inferior, trap_breakpoint_t bp)
{
  if (bp == g_bp_one) {
    do_bp_one(inferior);
  } else if (bp == g_bp_two) {
    do_bp_two();
  }
}

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

  trap_breakpoint_set_callback(breakpoint_callback);
  g_inferior = trap_inferior_exec("./inferiors/loop", argv);
  g_bp_one = trap_inferior_set_breakpoint(g_inferior, (char *)0x000000000040076d);
  g_bp_two = trap_inferior_set_breakpoint(g_inferior, (char *)0x000000000040076d);
  trap_inferior_continue(g_inferior);

  assert(g_bp_one_count == 1);
  assert(g_bp_two_count == 5);

  return 0;
}

You could make an argument that this test does too much since it does two things

Tests the delete functionality in do_bp_one()
Tests that duplicate breakpoints generate multiple calls to breakpoint_callback()

But I’m going to go ahead with this test anyway.

Remove breakpoint

The first error we have with the test is a compilation error:

/home/joseph/src/c/trap/test/test_duplicate_breakpoint.c: In function ‘do_bp_one’:
/home/joseph/src/c/trap/test/test_duplicate_breakpoint.c:15:5: warning: implicit declaration of function ‘trap_inferior_remove_breakpoint’ [-Wimplicit-function-declaration]
     trap_inferior_remove_breakpoint(inferior, g_bp_one);

I start by declaring and documenting the new API:

/**
 * @brief Remove breakpoint `bp` from `inferior`
 *
 * `trap_inferior_remove_breakpoint` will remove a previously set breakpoint in
 * the inferior.  Callbacks will no longer be generated for this breakpoint.
 * Execution will no longer stop at the breakpoint unless another breakpoint
 * at the same location already exists.
 *
 * @param inferior The handle of the inferior process from which to remove the
 *   breakpoint.
 * @param bp The handle of the breakpoint to remove.
 */
void trap_inferior_remove_breakpoint(trap_inferior_t inferior,
                                     trap_breakpoint_t bp);

With this the test compiles but does not link:

CMakeFiles/test_duplicate_breakpoint.dir/test_duplicate_breakpoint.c.o: In function `do_bp_one':
test_duplicate_breakpoint.c:(.text+0x35): undefined reference to `trap_inferior_remove_breakpoint'

So we implement the functionality to remove a breakpoint

void trap_inferior_remove_breakpoint(trap_inferior_t inferior,
		                                 trap_breakpoint_t handle)
{
  breakpoint_t *bp = (breakpoint_t *)handle;
  breakpoint_t tempBP;

  assert(&g_breakpoints[0] <= bp && bp < &g_breakpoints[g_num_breakpoints]);

  tempBP = *bp;
  bp->target_address = 0;
  bp->aligned_address = 0;
  bp->original_breakpoint_word = 0;

  if (!find_breakpoint_with_target_address(tempBP.target_address)) {
    breakpoint_remove(inferior, &tempBP);
  }
}

So how does this work?

On line 4 we get our breakpoint_t from the abstract trap_breakpoint_t
On line 7 we check that the breakpoint is actually from the global array g_breakpoints.
On line 9 we save the breakpoint_t into a temporary variable, tempBP to be used later.
On lines 10-12 we zero out the breakpoint_t from the global array
On line 14 we search for the target address (using the temporary). This checks to see if there is another breakpoint at the same address.
On line 15, if there is no duplicate breakpoint we remove the breakpoint. That is, we clear the INT 3 instruction. We pass tempBP though to breakpoint_remove so it can find the target_address and original_breakpoint_word.

Now, zeroing out the breakpoint_t entry is limited in that it basically leaks a breakpoint entry from g_breakpoints. We should fix this in the future but it will take a smarter method of allocating breakpoints. We’ll add a TODO item to file a GitHub issue about this.

At this point the test fails:

5/5 Test #5: test_duplicate_breakpoint ........***Exception: Other  0.47 sec
Unexpected stop in trap_inferior_continue: 0xb7f

Again, a SIGSEGV in the inferior.

Processing duplicate breakpoints

I suspect the reason for the SIGSEGV is that we need to process all the breakpoints but the current code only processes one.

While trying to implement callbacks for redundant breakpoints I found that I had burried the callback inside step_over_breakpoint(). But what does the callback have to do with stepping? This meant making changes to step_over_breakpoint() which didn’t make sense.

I first refactor the code until the change I want to make was easy and clean.

This is the refactoring I did in order to separate single stepping and triggering callbacks.

@@ -98,14 +98,12 @@ static void breakpoint_remove(trap_inferior_t inferior,
                        bp->original_breakpoint_word);
 }

-static void step_over_breakpoint(trap_inferior_t inferior)
+static void step_over_breakpoint(trap_inferior_t inferior, breakpoint_t *bp)
 {
   uintptr_t ip;
   pid_t pid = inferior;

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

   ip = ptrace_util_get_instruction_pointer(pid);
   ptrace_util_set_instruction_pointer(pid, ip - 1);
@@ -113,22 +111,24 @@ static void step_over_breakpoint(trap_inferior_t inferior)
   ptrace_util_single_step(pid);
 }

-static void finish_breakpoint(trap_inferior_t inferior)
+static void finish_breakpoint(trap_inferior_t inferior, breakpoint_t *bp)
 {
-  breakpoint_t *bp = breakpoint_resolve(inferior);
   breakpoint_set(inferior, bp);
   ptrace_util_continue(inferior);
 }

 enum inferior_state_t breakpoint_handle(trap_inferior_t inferior, enum inferior
 {
+  trap_breakpoint_t bp = breakpoint_resolve(inferior);
+
   switch(state) {
     case INFERIOR_RUNNING:
-      step_over_breakpoint(inferior);
+      breakpoint_trigger_callback(inferior, bp);
+      step_over_breakpoint(inferior, bp);
       return INFERIOR_SINGLE_STEPPING;

     case INFERIOR_SINGLE_STEPPING:
-      finish_breakpoint(inferior);
+      finish_breakpoint(inferior, bp);
       return INFERIOR_RUNNING;

     default:

Technically, this changed the order of breakpoint_remove() and breakpoint_trigger_callback() but that should be OK as they don’t depend on one another. As a confirmation, all the tests (except test_duplicate_breakpoint) pass. However, thinking about this I wonder this could make a difference somehow. The real question is about what can happen in the callback itself? While this seems safe now it left me with a lingering doubt. We’ll revisit this issue later.

Fro now, I need to call the callback multiple times, one for each breakpoint at the given location. This will get a bit detailed and I don’t want that detail in breakpoint_handle() so I write a new function:

static void do_callbacks(trap_inferior_t inferior, breakpoint_t *bp)
{
  for (int i = 0; i < g_num_breakpoints; i++) {
    if (g_breakpoints[i].target_address == bp->target_address) {
      breakpoint_trigger_callback(inferior, &g_breakpoints[i]);
    }
  }
}

and call it from breakpoint_handle(). The test fails in a new and intersting way:

5/5 Test #5: test_duplicate_breakpoint ........***Exception: Other  0.47 sec
PTRACE_POKETEXT: : Input/output error

I can added a quick print-out to ptrace_util_poke_text

@@ -36,6 +36,7 @@ void ptrace_util_poke_text(pid_t pid, unsigned long target_add
   int result = ptrace(PTRACE_POKETEXT, pid, (void *)target_address, (void *)dat
   if (result != 0) {
     perror("PTRACE_POKETEXT: ");
+    fprintf(stderr, "Writing %p", (void *)target_address);
     abort();
   }
 }

and find out that we are writing to address 0. I think the problem here is that we are calling ptrace_util_poke_text() on a target_address that we have already deleted. There are a couple of places where this could happen, so I’ll use gdb to figure out which one:

Program received signal SIGABRT, Aborted.
0x00007ffff7a4bcc9 in __GI_raise (sig=sig@entry=6)
    at ../nptl/sysdeps/unix/sysv/linux/raise.c:56
56	../nptl/sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) bt
#0  0x00007ffff7a4bcc9 in __GI_raise (sig=sig@entry=6)
    at ../nptl/sysdeps/unix/sysv/linux/raise.c:56
#1  0x00007ffff7a4f0d8 in __GI_abort () at abort.c:89
#2  0x00000000004017d4 in ptrace_util_poke_text (pid=4974, target_address=0,
    data=0) at /home/joseph/src/c/trap/src/ptrace_util.c:39
#3  0x00000000004014c1 in breakpoint_remove (inferior=4974,
    handle=0x6030e0 <g_breakpoints>)
    at /home/joseph/src/c/trap/src/breakpoint.c:97
#4  0x0000000000401561 in step_over_breakpoint (inferior=4974,
    bp=0x6030e0 <g_breakpoints>)
    at /home/joseph/src/c/trap/src/breakpoint.c:115
#5  0x0000000000401608 in breakpoint_handle (inferior=4974,
    state=INFERIOR_RUNNING) at /home/joseph/src/c/trap/src/breakpoint.c:136
#6  0x00000000004011fb in trap_inferior_continue (inferior=4974)
    at /home/joseph/src/c/trap/src/inferior_load.c:72
#7  0x0000000000400ffe in main ()
    at /home/joseph/src/c/trap/test/test_duplicate_breakpoint.c:41

OK, so the problem occurs when calling breakpoint_remove() to remove the breakpoint when stepping over it. This goes back to my suspicion about ordering of calls in breakpoint_handle(). As I said, the real question is about what can happen in the callback itself? And the thing that can happen in the callback is that the application can call trap_inferior_remove_breakpoint()! Right now we have:

trap_breakpoint_t bp = breakpoint_resolve(inferior);

switch(state) {
  case INFERIOR_RUNNING:
    do_callbacks(inferior, bp);
    step_over_breakpoint(inferior, bp);
    return INFERIOR_SINGLE_STEPPING;

So one problem is that we resolve the breakpoint only once, but after do_callbacks() the resolved breakpoint is invalid. We should reresolve. This is going to get a bit complex so I’ll move this code into a new function:

@@ -126,15 +126,22 @@ static void finish_breakpoint(trap_inferior_t inferior, br
   ptrace_util_continue(inferior);
 }

+static enum inferior_state_t start_breakpoint(trap_inferior_t inferior,
+                                              breakpoint_t *bp)
+{
+  do_callbacks(inferior, bp);
+  step_over_breakpoint(inferior, bp);
+
+  return INFERIOR_SINGLE_STEPPING;
+}
+
 enum inferior_state_t breakpoint_handle(trap_inferior_t inferior, enum inferior
 {
   trap_breakpoint_t bp = breakpoint_resolve(inferior);

   switch(state) {
     case INFERIOR_RUNNING:
-      do_callbacks(inferior, bp);
-      step_over_breakpoint(inferior, bp);
-      return INFERIOR_SINGLE_STEPPING;
+      return start_breakpoint(inferior, bp);

     case INFERIOR_SINGLE_STEPPING:
       finish_breakpoint(inferior, bp);

This just creates the function but the functionality hasn’t changed yet. Running the tests shows we haven’t introduced any regressions. Next, we make the functional change

static enum inferior_state_t start_breakpoint(trap_inferior_t inferior,
                                              breakpoint_t *bp)
{
  breakpoint_t temp_bp = *bp;

  do_callbacks(inferior, bp);
  if (!bp->target_address) {
    /*
     * The breakpoint was deleted in the callback. There are two possiblities.
     * 1. This breakpoint was unique and we should now continue and go to the
     *    running state.
     * 2. There was another breakpoint at this address and we need to single
     *    step over it.
     */
    breakpoint_t *duplicate_bp =
      find_breakpoint_with_target_address(temp_bp.target_address);
    if (duplicate_bp) {
      // Use the duplicate_bp for the single step
      bp = duplicate_bp;
    } else {
      // Unique
      ptrace_util_continue(inferior);
      return INFERIOR_RUNNING;
    }
  }
  step_over_breakpoint(inferior, bp);

  return INFERIOR_SINGLE_STEPPING;
}

Given the comments in the code, I hope this is self explanatory. At this point the test still fails:

5/5 Test #5: test_duplicate_breakpoint ........***Exception: Other  0.46 sec
Unexpected stop in trap_inferior_continue: 0xb7f

I think the code we’ve written was necessary but I must have had the wrong idea about what was causing the SIGSEGV.

At this point we have two options. The frist is to continue to debug the issue head on as we have been. The second option is to take a step back and try a different methodology. We can use TDD principles and take smaller steps toward our goals. I’m opting to follow the second option.

Write a test to delete breakpoints

A while back I expressed a small reservation about test_duplicate_breakpoint:

You could make an argument that this test does too much since it does two things

1. Tests the delete functionality in `do_bp_one()`
2. Tests that duplicate breakpoints generate multiple calls to `breakpoint_callback()`

But I'm going to go ahead with this test anyway.

In retrospect, it would have been more prudent to test the delete functionality separately. This would have allowed me to take smaller steps and given me more confidence in the delete functionality before embarking on the feature to handle multiple breakpoints. It is possible that the SIGSEGV is due to a problem in the delete functionality. We can confirm or deny this theory by writing the test for delete now. It will be a simpler test than test_duplicate_breakpoint so if it fails we know the problem is in delete and if it passes then we know to look for the problem in the duplicate handling code (in the core code or in the interaction with delete).

So first I wrote this very simple test:

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

int g_main_count = 0;

trap_inferior_t g_inferior = 0;
trap_breakpoint_t g_bp_main = 0;

void breakpoint_callback(trap_inferior_t inferior, trap_breakpoint_t bp)
{
  assert(inferior == g_inferior);
  g_main_count++;
}

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

  trap_breakpoint_set_callback(breakpoint_callback);
  g_inferior = trap_inferior_exec("./inferiors/loop", argv);
  g_bp_main = trap_inferior_set_breakpoint(g_inferior, (char *)0x0000000000400778);
  trap_inferior_remove_breakpoint(g_inferior, g_bp_main);
  trap_inferior_continue(g_inferior);

  assert(g_main_count == 0);

  return 0;
}

This test actually deletes its breakpoint right away. The breakpoint will never be hit. This test passes:

    Start 5: test_delete_breakpoint
5/5 Test #5: test_delete_breakpoint ...........   Passed    0.01 sec

Now, I need a test that deletes the breakpoint in the callback. Note, that I don’t consider this an extreme case. It is the case in the test above basically doesn’t make sense in practice as the breakpoint is never used. It might as well have never been created. The only practical usage for trap_inferior_remove_breakpoint() is to call it from a callback after the breakpoint has triggered at least once (or possibly after some other event has occured). Here’s the test to delete a breakpoint from the callback:

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

int g_foo_count = 0;

trap_inferior_t g_inferior = 0;
trap_breakpoint_t g_bp_foo = 0;

void breakpoint_callback(trap_inferior_t inferior, trap_breakpoint_t bp)
{
  assert(inferior == g_inferior);
  g_foo_count++;
  trap_inferior_remove_breakpoint(g_inferior, bp);
}

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

  trap_breakpoint_set_callback(breakpoint_callback);
  g_inferior = trap_inferior_exec("./inferiors/loop", argv);
  g_bp_foo = trap_inferior_set_breakpoint(g_inferior, (char *)0x000000000040076d);
  trap_inferior_continue(g_inferior);

  assert(g_foo_count == 1);

  return 0;
}

This test fails with SIGSEGV

6/6 Test #6: test_delete_breakpoint_in_callback ...***Exception: Other  0.47 sec
Unexpected stop in trap_inferior_continue: 0xb7f

So this shows that there is a problem, in general, with removing a breakpoint from within the callback.

I looked over the code again and ecided it is too complex. I don’t like the number of temporary breakpoint_t structures that I have to used to work around the fact that I’m deleting breakpoints. I should simplify this code. Here’s my thinking about how to simplify:

Defer the removal of the breakpoint until after the single step completes
Use the inferior state to decide this
Maybe even introduce a new inferior state, INFERIOR_SINGLE_STEPPING_WITH_DEFERED_REMOVE, to handle it

First, I need to add a state to breakpoint_t to track what’s going on with the breakpoint. These are the states we have:

+enum breakpoint_state_t {
+  BREAKPOINT_UNALLOCATED,
+  BREAKPOINT_ACTIVE,
+  BREAKPOINT_DEFERED_REMOVE
+};
+
 struct breakpoint_t {
   uintptr_t target_address;
   uintptr_t aligned_address;
   uintptr_t original_breakpoint_word;
+  enum breakpoint_state_t state;
 };

Next, we need to change the implementation of trap_inferior_remove_breakpoint() to setup the defered removal. This function becomes very simple:

void trap_inferior_remove_breakpoint(trap_inferior_t inferior,
		                                 trap_breakpoint_t handle)
{
  breakpoint_t *bp = (breakpoint_t *)handle;
  assert(bp->state == BREAKPOINT_ACTIVE);
  bp->state = BREAKPOINT_DEFERED_REMOVE;
}

This change causes test_delete_breakpoint to fail on our new assert:

5/7 Test #5: test_delete_breakpoint ...............***Exception: Other  0.46 sec
test_delete_breakpoint: /home/joseph/src/c/trap/src/breakpoint.c:188: trap_inferior_remove_breakpoint: Assertion `bp->state == BREAKPOINT_ACTIVE' failed.

We need to set the breakpoint active when we create it:

@@ -50,6 +51,7 @@ static breakpoint_t *breakpoint_allocate()
   g_num_breakpoints++;

   assert(index < MAX_BREAKPOINTS);
+  g_breakpoints[index].state = BREAKPOINT_ACTIVE;
   return &g_breakpoints[index];
 }

test_delete_breakpoint still fails but this is more expected:

5/7 Test #5: test_delete_breakpoint ...............***Exception: Other  0.23 sec
test_delete_breakpoint: /home/joseph/src/c/trap/test/test_delete_breakpoint.c:26: main: Assertion `g_main_count == 0' failed.

We are not actually deleting any breakpoints. For the case where the application is stopped we should just remove the breakpoint immediately rather than defering it. Let’s write this instead:

void trap_inferior_remove_breakpoint(trap_inferior_t inferior,
		                                 trap_breakpoint_t handle)
{
  breakpoint_t *bp = (breakpoint_t *)handle;
  assert(bp->state == BREAKPOINT_ACTIVE);

  breakpoint_remove(inferior, bp);
  bp->state = BREAKPOINT_UNALLOCATED;
}

This passes test_delete_breakpoint. However it still fails test_delete_breakpoint_in_callback:

    Start 6: test_delete_breakpoint_in_callback
6/7 Test #6: test_delete_breakpoint_in_callback ...***Exception: Other  0.46 sec
test_delete_breakpoint_in_callback: /home/joseph/src/c/trap/src/breakpoint.c:189: trap_inferior_remove_breakpoint: Assertion `bp->state == BREAKPOINT_ACTIVE' failed.

In this case we need to defer the deletion. We should inspect the inferior state to do this however we don’t have access to the inferior state. We’ll need to add an accessor that returns the state which I’ve called inferior_get_state().

void trap_inferior_remove_breakpoint(trap_inferior_t inferior,
		                                 trap_breakpoint_t handle)
{
  breakpoint_t *bp = (breakpoint_t *)handle;
  enum inferior_state_t state = inferior_get_state(inferior);

  assert(bp->state == BREAKPOINT_ACTIVE);

  switch(state) {
    case INFERIOR_STOPPED:
      breakpoint_remove(inferior, bp);
      bp->state = BREAKPOINT_UNALLOCATED;
      break;

    case INFERIOR_RUNNING:
      bp->state = BREAKPOINT_DEFERED_REMOVE;
      break;

    default:
      abort();
  }
}

This version still fails:

6/7 Test #6: test_delete_breakpoint_in_callback ...***Exception: Other  0.46 sec
test_delete_breakpoint_in_callback: /home/joseph/src/c/trap/src/breakpoint.c:194: trap_inferior_remove_breakpoint: Assertion `bp->state == BREAKPOINT_ACTIVE' failed.

I added a small print-out to trap_inferior_remove_breakpoint() just before the assert like this:

fprintf(stderr, "Removing bp %p with bp->state = %d  inferior state = %d\n",
        bp, bp->state, state);

and determined that the breakpoint is being removed twice. The reason for this is that we don’t actually remove the breakpoint but the test’s callback looks like this:

void breakpoint_callback(trap_inferior_t inferior, trap_breakpoint_t bp)
{
  assert(inferior == g_inferior);
  g_foo_count++;
  trap_inferior_remove_breakpoint(g_inferior, bp);
}

so the test will try to remove the breakpoint as many times as the callback is triggered.

Clean up the deferred removals

To actually process the deferred removals I’ve written this:

+static void do_deferred_removals(trap_inferior_t inferior)
+{
+  for (int i = 0; i < g_num_breakpoints; i++) {
+    if (g_breakpoints[i].state == BREAKPOINT_DEFERRED_REMOVE) {
+      g_breakpoints[i].target_address = 0;
+      g_breakpoints[i].aligned_address = 0;
+      g_breakpoints[i].original_breakpoint_word = 0;
+      g_breakpoints[i].state = BREAKPOINT_UNALLOCATED;
+    }
+  }
+}
+
 static void finish_breakpoint(trap_inferior_t inferior, breakpoint_t *bp)
 {
-  breakpoint_set(inferior, bp);
+  do_deferred_removals(inferior);
+  if (bp && bp->state == BREAKPOINT_ACTIVE) {
+    breakpoint_set(inferior, bp);
+  }
   ptrace_util_continue(inferior);
 }

And I’ve also removed all the complex code from start_breakpoint(). With these changes the test passes:

    Start 6: test_delete_breakpoint_in_callback
6/7 Test #6: test_delete_breakpoint_in_callback ...   Passed    0.01 sec

However, the final test, test_duplicated_breakpoint still fails:

7/7 Test #7: test_duplicate_breakpoint ............***Exception: Other  0.24 sec
test_duplicate_breakpoint: /home/joseph/src/c/trap/test/test_duplicate_breakpoint.c:44: main: Assertion `g_bp_two_count == 5' failed.

A little more debugging to make the tests pass

I wonder how many times g_bp_two was actually hit. A quick print-out shows:

g_bp_two_count = 1

A few more print-outs confirmed that I was deleting the correct breakpoint. Thinking more I realized that finish_breakpoint() wasn’t reseting the breakpoint when done. I needed to look for an active breakpoint:

static void finish_breakpoint(trap_inferior_t inferior, breakpoint_t *bp)
{
  uintptr_t target_address = bp->target_address;
  
  do_deferred_removals(inferior);
  breakpoint_t *new_bp = find_breakpoint_with_target_address(target_address);
  if (new_bp) {
    breakpoint_set(inferior, new_bp);
  }
  ptrace_util_continue(inferior);
}

With this change the test still fails, now with SIGSEGV:

7/7 Test #7: test_duplicate_breakpoint ............***Exception: Other  0.46 sec
Remove breakpoint 0x603100 bp->state = 1  inferior state = 0
do_deferred_removals: Removing 0x603100
Unexpected stop in trap_inferior_continue: 0xb7f

I believe the problem here is that when setting the second breakpoint we read the “original breakpoint word” after the first breakpoint has already written an INT 3. If another breakpoint exists I should copy its original_breakpoint_word like this:

@@ -58,17 +69,22 @@ static breakpoint_t *breakpoint_allocate()
 trap_breakpoint_t trap_inferior_set_breakpoint(trap_inferior_t inferior,
                                                char *location)
 {
   const uintptr_t target_address = (uintptr_t)location;
   uintptr_t aligned_address = target_address & ~(0x7UL);
   breakpoint_t *bp = breakpoint_allocate();

-  bp->original_breakpoint_word = ptrace_util_peek_text(inferior,
-                                                      aligned_address);
+  breakpoint_t *existing = find_breakpoint_with_target_address(target_address);
+  if (existing) {
+    bp->original_breakpoint_word = existing->original_breakpoint_word;
+  } else {
+    bp->original_breakpoint_word = ptrace_util_peek_text(inferior,
+
+  }
   bp->target_address = target_address;
   bp->aligned_address = aligned_address;

   breakpoint_set(inferior, bp);

   return bp;
 }

With this change all the tests pass!

Refactor the breakpoint code a bit

Now that the test pass I want to do a little clean up. There is an inconsistency in breakpoint_handle() now in terms of the way the new state is computed:

case INFERIOR_RUNNING:
  return start_breakpoint(inferior, bp);

case INFERIOR_SINGLE_STEPPING:
  finish_breakpoint(inferior, bp);
  return INFERIOR_RUNNING;

This looks unbalanced to me. Because start_breakpoint() only has one possible return value now I will bring the new state back out to breakpoint_handle(). With this change:

case INFERIOR_RUNNING:
  start_breakpoint(inferior, bp);
  return INFERIOR_SINGLE_STEPPING;

case INFERIOR_SINGLE_STEPPING:
  finish_breakpoint(inferior, bp);
  return INFERIOR_RUNNING;

I actually really like the balance now. The parity between start_breakpoint() and finish_breakpoint() is an improvement over the version that included the content of start_breakpoint() inline.

We could do more refacoring in breakpoint.c as the file is getting a little long and the function ordering is getting convoluted but we’ll wait until a new change to breakpoints can drive our design. I will keep in the back of my mind the duplication that has cropped up in:

find_breakpoint_with_target_address()
do_callbacks()
do_deferred_removals()

There is repeated code to iterate over the collection of breakpoints and all three functions would need to change if we changed the type of collection used.

Wrapping Up

In this post we implemented two features - multiple breakpoints and duplicate breakpoints. Along the way we explored the API design issues related to these features and cleaned up some code. We also used TDD to drive feature development and debugging. By the end of it all we left ourselves with a few long term TODO items:

File a GitHub issue: breakpoint_allocate needs to be more graceful
File a GitHub issue: trap_inferior_remove_breakpoint needs to deallocate the entry
Duplicaton enumerating breakpoints

which I think really collapse down into a single issue:

File a GitHub issue: Replace g_breakpoints with a more robust breakpoint container.

We also have one warning left in breakpoint.c:

/home/joseph/src/c/trap/src/breakpoint.c: In function ‘do_deferred_removals’:
/home/joseph/src/c/trap/src/breakpoint.c:137:50: warning: unused parameter ‘inferior’ [-Wunused-parameter]
 static void do_deferred_removals(trap_inferior_t inferior)

This is and indication that we don’t support multiple inferiors correctly. I’ve filed another GitHub issue for this:

The next milestone on the Trap roadmap is to add support for debugging multiple threads and we’ll tackle that in the next post.