Skip to contentSkip to conversation

change cpu->breakpoints to a GTree

RFC PATCH In review Shivang Upadhyay 2 participants 10 messages Jun 30 RISC-V

lore
Share & tools
lore
#0 lore raw

cover change cpu->breakpoints to a GTree

Because of compiler inlining, a single source-level breakpoint may correspond to many guest physical addresses. For example, on ppc64:

    (gdb)
        Breakpoint 1  at 0xc000000000019964: arch_set_bit (1846 locations)
        Breakpoint 10 at 0xc00000000006fc80: eeh_readl     (1705 locations)

qemu currently stores breakpoints in a QLIST. While insertion is O(1), every translated instruction must linearly scan the list to determine whether the current PC matches a breakpoint. As the number of breakpoints grows, this check becomes a significant execution bottleneck.

This is particularly noticeable when debugging kernels built with heavy compiler inlining, where a relatively small number of logical breakpoints expand into thousands of breakpoint locations. On a ppc64 guest running under TCG on x86, firmware boot time increases from about 1 second to over 50 seconds with roughly 1800 breakpoint locations.

Replace the QLIST with a GTree so breakpoint lookup becomes O(log n) instead of O(n), while preserving efficient insertion and removal.

Measured on the same workload (ppc64 skiboot bringup):

| Configuration             | Firmware boot time |
| ------------------------- | -----------------: |
| No breakpoints            |             ~1.0 s |
| ~1846 breakpoints (QLIST) |              ~52 s |
| ~1846 breakpoints (GTree) |             ~1.4 s |

This removes the linear breakpoint lookup overhead and restores near-baseline TCG execution performance even with thousands of breakpoint locations.

At present, this series has been tested only with TCG. I was unable to test other accelerators, such as WHPX, because I do not have access to a Windows environment. I would appreciate feedback from the WHPX maintainers, particularly regarding any accelerator-specific changes required for the migration of cpu->breakpoints from QLIST to GTree. I also noticed an existing code comment referencing a future migration of the breakpoint data structure from QLIST to a tree [1].

[1] https://github.com/qemu/qemu/blob/master/target/i386/whpx/whpx-all.c#L1733

Shivang Upadhyay (2):
accel/tcg: use GTree for faster breakpoint lookups riscv/debug: migrate debug_check_breakpoint to use GTree breakpoints

 accel/tcg/cpu-exec.c      |  26 +++++----
 cpu-common.c              | 108 +++++++++++++++++++++++++++++++-------
 hw/core/cpu-common.c      |   1 -
 include/exec/breakpoint.h |   1 -
 include/hw/core/cpu.h     |  14 ++---
 linux-user/main.c         |  13 +++--
 target/riscv/debug.c      |  71 ++++++++++++++-----------
 7 files changed, 159 insertions(+), 75 deletions(-)
Signature · 1 line
2.54.0
#1 lore raw

RFC PATCH 1/2 accel/tcg: use GTree for faster breakpoint lookups

check_for_breakpoints_slow() currently performs a linear scan of cpu->breakpoints on every breakpoint check. As the number of breakpoints grows, this increases the cost of each lookup.

Replace cpu->breakpoints with a GTree to provide efficient lookups by address.

Additionally, maintain a second GTree, cpu->page_breakpoints, containing the guest page numbers of all installed breakpoints. This detaches, pc lookup and page lookup, into 2 different Gtrees.

Both trees are kept in sync when breakpoints are inserted or removed.

---
 accel/tcg/cpu-exec.c      |  26 +++++----
 cpu-common.c              | 108 +++++++++++++++++++++++++++++++-------
 hw/core/cpu-common.c      |   1 -
 include/exec/breakpoint.h |   1 -
 include/hw/core/cpu.h     |  14 ++---
 linux-user/main.c         |  13 +++--
 6 files changed, 118 insertions(+), 45 deletions(-)
accel/tcg/cpu-exec.c +15 -11
index 9c754b0365..008919a108 100644
@@ -296,8 +296,14 @@ static void log_cpu_exec(vaddr pc, CPUState *cpu,
 static bool check_for_breakpoints_slow(CPUState *cpu, vaddr pc,
                                        uint32_t *cflags)
 {
-    CPUBreakpoint *bp;
+    /* GTree key for cpu->breakpoints
+     */
+    CPUBreakpoint key = {
+        .pc = pc,
+        .flags = 0, /* not required */
+    };
     bool match_page = false;
+    uint64_t pb;
 
     /*
      * Singlestep overrides breakpoints.
@@ -312,12 +318,8 @@ static bool check_for_breakpoints_slow(CPUState *cpu, vaddr pc,
         return false;
     }
 
-    QTAILQ_FOREACH(bp, &cpu->breakpoints, entry) {
-        /*
-         * If we have an exact pc match, trigger the breakpoint.
-         * Otherwise, note matches within the page.
-         */
-        if (pc == bp->pc) {
+    CPUBreakpoint *bp = g_tree_lookup(cpu->breakpoints, &key);
+    if (bp) {
             bool match_bp = false;
 
             if (bp->flags & BP_GDB) {
@@ -336,9 +338,11 @@ static bool check_for_breakpoints_slow(CPUState *cpu, vaddr pc,
                 cpu->exception_index = EXCP_DEBUG;
                 return true;
             }
-        } else if (((pc ^ bp->pc) & TARGET_PAGE_MASK) == 0) {
-            match_page = true;
-        }
+    }
+
+    pb = pc & TARGET_PAGE_MASK;
+    if (g_tree_lookup(cpu->page_breakpoints, &pb)) {
+        match_page = true;
     }
 
     /*
@@ -362,7 +366,7 @@ static bool check_for_breakpoints_slow(CPUState *cpu, vaddr pc,
 static inline bool check_for_breakpoints(CPUState *cpu, vaddr pc,
                                          uint32_t *cflags)
 {
-    return unlikely(!QTAILQ_EMPTY(&cpu->breakpoints)) &&
+    return cpu->breakpoints && g_tree_nnodes(cpu->breakpoints) &&
         check_for_breakpoints_slow(cpu, pc, cflags);
 }
 
cpu-common.c +88 -20

160 lines not on this page · raw message

hw/core/cpu-common.c +0 -1
index e314f916f8..5c2d7ed42c 100644
@@ -322,7 +322,6 @@ static void cpu_common_initfn(Object *obj)
     qemu_mutex_init(&cpu->work_mutex);
     qemu_lockcnt_init(&cpu->in_ioctl_lock);
     QSIMPLEQ_INIT(&cpu->work_list);
-    QTAILQ_INIT(&cpu->breakpoints);
     QTAILQ_INIT(&cpu->watchpoints);
 
     cpu_exec_initfn(cpu);
include/exec/breakpoint.h +0 -1
index 95f0482e6d..f6a6826d05 100644
@@ -15,7 +15,6 @@
 typedef struct CPUBreakpoint {
     vaddr pc;
     int flags; /* BP_* */
-    QTAILQ_ENTRY(CPUBreakpoint) entry;
 } CPUBreakpoint;
 
 typedef struct CPUWatchpoint {
include/hw/core/cpu.h +7 -7
index 59d601465b..be4d502621 100644
@@ -526,7 +526,8 @@ struct CPUState {
     QTAILQ_ENTRY(CPUState) node;
 
     /* ice debug support */
-    QTAILQ_HEAD(, CPUBreakpoint) breakpoints;
+    GTree *breakpoints;
+    GTree *page_breakpoints;
 
     QTAILQ_HEAD(, CPUWatchpoint) watchpoints;
     CPUWatchpoint *watchpoint_hit;
@@ -1161,13 +1162,12 @@ void cpu_breakpoint_remove_all(CPUState *cpu, int mask);
 /* Return true if PC matches an installed breakpoint.  */
 static inline bool cpu_breakpoint_test(CPUState *cpu, vaddr pc, int mask)
 {
-    CPUBreakpoint *bp;
+    CPUBreakpoint bp = {.pc = pc};
 
-    if (unlikely(!QTAILQ_EMPTY(&cpu->breakpoints))) {
-        QTAILQ_FOREACH(bp, &cpu->breakpoints, entry) {
-            if (bp->pc == pc && (bp->flags & mask)) {
-                return true;
-            }
+    if (cpu->breakpoints) {
+        CPUBreakpoint *a = g_tree_lookup(cpu->breakpoints, &bp);
+        if (a && (a->flags & mask)) {
+            return true;
         }
     }
     return false;
linux-user/main.c +8 -5
index c08c73fd80..6f8016d20b 100644
@@ -234,12 +234,18 @@ void init_task_state(TaskState *ts)
     ts->sys_dispatch_len = -1;
 }
 
+static gboolean cpu_copy_breakpoint(gpointer key, gpointer value, gpointer cpustate) {
+    CPUState *newcpu = (CPUState*)cpustate;
+    CPUBreakpoint* bp = (CPUBreakpoint*)value;
+    cpu_breakpoint_insert(newcpu, bp->pc, bp->flags, NULL);
+    return true;
+}
+
 CPUArchState *cpu_copy(CPUArchState *env)
 {
     CPUState *cpu = env_cpu(env);
     CPUState *new_cpu = cpu_create(cpu_type);
     CPUArchState *new_env = cpu_env(new_cpu);
-    CPUBreakpoint *bp;
 
     /* Reset non arch specific state */
     cpu_reset(new_cpu);
@@ -258,10 +264,7 @@ CPUArchState *cpu_copy(CPUArchState *env)
     /* Clone all break/watchpoints.
        Note: Once we support ptrace with hw-debug register access, make sure
        BP_CPU break/watchpoints are handled correctly on clone. */
-    QTAILQ_INIT(&new_cpu->breakpoints);
-    QTAILQ_FOREACH(bp, &cpu->breakpoints, entry) {
-        cpu_breakpoint_insert(new_cpu, bp->pc, bp->flags, NULL);
-    }
+    g_tree_foreach(cpu->breakpoints, cpu_copy_breakpoint, new_cpu);
 
     return new_env;
 }
Signature · 1 line
2.54.0
#2 lore raw

Re: [RFC PATCH 1/2] accel/tcg: use GTree for faster breakpoint lookups

Quoted 14 lines · Shivang Upadhyay

check_for_breakpoints_slow() currently performs a linear scan of cpu->breakpoints on every breakpoint check. As the number of breakpoints grows, this increases the cost of each lookup.

Replace cpu->breakpoints with a GTree to provide efficient lookups by address.

Additionally, maintain a second GTree, cpu->page_breakpoints, containing the guest page numbers of all installed breakpoints. This detaches, pc lookup and page lookup, into 2 different Gtrees.

Both trees are kept in sync when breakpoints are inserted or removed.

Quoted 8 lines
---
  accel/tcg/cpu-exec.c      |  26 +++++----
  cpu-common.c              | 108 +++++++++++++++++++++++++++++++-------
  hw/core/cpu-common.c      |   1 -
  include/exec/breakpoint.h |   1 -
  include/hw/core/cpu.h     |  14 ++---
  linux-user/main.c         |  13 +++--
  6 files changed, 118 insertions(+), 45 deletions(-)

I think it would be better to use IntervalTree, so that we don't have to keep that second tree of pages. Obviously, IntervalTree can query an interval, which takes care of querying for entries within a page.

r~

#3 lore raw

Re: [RFC PATCH 1/2] accel/tcg: use GTree for faster breakpoint lookups

Quoted 7 lines · Richard Henderson

I think it would be better to use IntervalTree, so that we don't have to keep that second
tree of pages.  Obviously, IntervalTree can query an interval, which takes care of
querying for entries within a page.

I will read about InteralTrees.
Thanks for the suggestion.

Quoted 2 lines

r~

~Shivang

#4 lore raw

Re: [RFC PATCH 1/2] accel/tcg: use GTree for faster breakpoint lookups

In reply to Richard Henderson
Quoted 10 lines · Richard Henderson
Quoted 1 line
   6 files changed, 118 insertions(+), 45 deletions(-)

I think it would be better to use IntervalTree, so that we don't have to keep that second
tree of pages.  Obviously, IntervalTree can query an interval, which takes care of
querying for entries within a page.

r~

As per my initial understanding of Interval trees, The primary goal of them would be store intervals, and then query with point/intervals. But current usecase is storing points and querring with intervals? maybe i can be wrong with this idea.

Maybe i can just use cpu->breakpoint tree to find out page match, with using lower_bound on the pc & TARGET_PAGE_MASK and find if the bp->pc < (pc & TARGET_PAGE_MASK + PAGESIZE)?

~Shivang.

#5 lore raw

Re: [RFC PATCH 1/2] accel/tcg: use GTree for faster breakpoint lookups

Quoted 10 lines · Shivang Upadhyay
Quoted 9 lines · Richard Henderson
Quoted 1 line
    6 files changed, 118 insertions(+), 45 deletions(-)

I think it would be better to use IntervalTree, so that we don't have to keep that second
tree of pages.  Obviously, IntervalTree can query an interval, which takes care of
querying for entries within a page.

Quoted 6 lines
Quoted 1 line

r~

As per my initial understanding of Interval trees, The primary goal of them would be store intervals, and then query with point/intervals. But current usecase is storing points and querring with intervals? maybe i can be wrong with this idea.

A point is simply an interval of 1. In this case, start = last = pc.

r~

#6 lore raw

RFC PATCH 2/2 riscv/debug: migrate debug_check_breakpoint to use GTree breakpoints

In reply to Shivang Upadhyay

as cpu->breakpoints is migrated to GTree, change the breakpoint looping from QTAILQ_FOREACH to g_tree_foreach.

---
 target/riscv/debug.c | 71 +++++++++++++++++++++++++-------------------
 1 file changed, 41 insertions(+), 30 deletions(-)
target/riscv/debug.c +41 -30
index 30d39ee5cd..6b2ffd08db 100644
@@ -939,53 +939,64 @@ void riscv_cpu_debug_excp_handler(CPUState *cs)
     }
 }
 
-bool riscv_cpu_debug_check_breakpoint(CPUState *cs)
+static bool bp_found;
+
+static gboolean check_breakpoints(gpointer key, gpointer value, gpointer cpu_state)
 {
+    CPUState *cs = (CPUState*)cpu_state;
+    CPUBreakpoint *bp = (CPUBreakpoint*)value;
     RISCVCPU *cpu = RISCV_CPU(cs);
     CPURISCVState *env = &cpu->env;
-    CPUBreakpoint *bp;
+    int trigger_type;
     target_ulong ctrl;
     target_ulong pc;
-    int trigger_type;
     int i;
 
-    QTAILQ_FOREACH(bp, &cs->breakpoints, entry) {
-        for (i = 0; i < RV_MAX_TRIGGERS; i++) {
-            trigger_type = get_trigger_type(env, i);
+    for (i = 0; i < RV_MAX_TRIGGERS; i++) {
+        trigger_type = get_trigger_type(env, i);
+
+        if (!trigger_common_match(env, trigger_type, i)) {
+            continue;
+        }
+
+        switch (trigger_type) {
+        case TRIGGER_TYPE_AD_MATCH:
+            ctrl = env->tdata1[i];
+            pc = env->tdata2[i];
 
-            if (!trigger_common_match(env, trigger_type, i)) {
-                continue;
+            if ((ctrl & TYPE2_EXEC) && (bp->pc == pc)) {
+                env->badaddr = pc;
+                bp_found = true;
+                return true;
             }
+            break;
+        case TRIGGER_TYPE_AD_MATCH6:
+            ctrl = env->tdata1[i];
+            pc = env->tdata2[i];
 
-            switch (trigger_type) {
-            case TRIGGER_TYPE_AD_MATCH:
-                ctrl = env->tdata1[i];
-                pc = env->tdata2[i];
-
-                if ((ctrl & TYPE2_EXEC) && (bp->pc == pc)) {
-                    env->badaddr = pc;
-                    return true;
-                }
-                break;
-            case TRIGGER_TYPE_AD_MATCH6:
-                ctrl = env->tdata1[i];
-                pc = env->tdata2[i];
-
-                if ((ctrl & TYPE6_EXEC) && (bp->pc == pc)) {
-                    env->badaddr = pc;
-                    return true;
-                }
-                break;
-            default:
-                /* other trigger types are not supported or irrelevant */
-                break;
+            if ((ctrl & TYPE6_EXEC) && (bp->pc == pc)) {
+                env->badaddr = pc;
+                bp_found = true;
+                return true;
             }
+            break;
+        default:
+            /* other trigger types are not supported or irrelevant */
+            break;
         }
     }
 
     return false;
 }
 
+bool riscv_cpu_debug_check_breakpoint(CPUState *cs)
+{
+    bp_found = false;
+    g_tree_foreach(cs->breakpoints, check_breakpoints, cs);
+
+    return bp_found;
+}
+
 bool riscv_cpu_debug_check_watchpoint(CPUState *cs, CPUWatchpoint *wp)
 {
     RISCVCPU *cpu = RISCV_CPU(cs);
Signature · 1 line
2.54.0
#7 lore raw

Re: [RFC PATCH 2/2] riscv/debug: migrate debug_check_breakpoint to use GTree breakpoints

Quoted 5 lines · Shivang Upadhyay

as cpu->breakpoints is migrated to GTree, change the breakpoint looping from QTAILQ_FOREACH to g_tree_foreach.

---
  target/riscv/debug.c | 71 +++++++++++++++++++++++++-------------------
  1 file changed, 41 insertions(+), 30 deletions(-)

(1) This can't be a separate patch, because the first patch can't compile
(2) You can't use a global variable for bp_found.

r~

Quoted 100 lines
target/riscv/debug.c +41 -30
index 30d39ee5cd..6b2ffd08db 100644
@@ -939,53 +939,64 @@ void riscv_cpu_debug_excp_handler(CPUState *cs)
      }
  }
 
-bool riscv_cpu_debug_check_breakpoint(CPUState *cs)
+static bool bp_found;
+
+static gboolean check_breakpoints(gpointer key, gpointer value, gpointer cpu_state)
  {
+    CPUState *cs = (CPUState*)cpu_state;
+    CPUBreakpoint *bp = (CPUBreakpoint*)value;
      RISCVCPU *cpu = RISCV_CPU(cs);
      CPURISCVState *env = &cpu->env;
-    CPUBreakpoint *bp;
+    int trigger_type;
      target_ulong ctrl;
      target_ulong pc;
-    int trigger_type;
      int i;
 
-    QTAILQ_FOREACH(bp, &cs->breakpoints, entry) {
-        for (i = 0; i < RV_MAX_TRIGGERS; i++) {
-            trigger_type = get_trigger_type(env, i);
+    for (i = 0; i < RV_MAX_TRIGGERS; i++) {
+        trigger_type = get_trigger_type(env, i);
+
+        if (!trigger_common_match(env, trigger_type, i)) {
+            continue;
+        }
+
+        switch (trigger_type) {
+        case TRIGGER_TYPE_AD_MATCH:
+            ctrl = env->tdata1[i];
+            pc = env->tdata2[i];
 
-            if (!trigger_common_match(env, trigger_type, i)) {
-                continue;
+            if ((ctrl & TYPE2_EXEC) && (bp->pc == pc)) {
+                env->badaddr = pc;
+                bp_found = true;
+                return true;
              }
+            break;
+        case TRIGGER_TYPE_AD_MATCH6:
+            ctrl = env->tdata1[i];
+            pc = env->tdata2[i];
 
-            switch (trigger_type) {
-            case TRIGGER_TYPE_AD_MATCH:
-                ctrl = env->tdata1[i];
-                pc = env->tdata2[i];
-
-                if ((ctrl & TYPE2_EXEC) && (bp->pc == pc)) {
-                    env->badaddr = pc;
-                    return true;
-                }
-                break;
-            case TRIGGER_TYPE_AD_MATCH6:
-                ctrl = env->tdata1[i];
-                pc = env->tdata2[i];
-
-                if ((ctrl & TYPE6_EXEC) && (bp->pc == pc)) {
-                    env->badaddr = pc;
-                    return true;
-                }
-                break;
-            default:
-                /* other trigger types are not supported or irrelevant */
-                break;
+            if ((ctrl & TYPE6_EXEC) && (bp->pc == pc)) {
+                env->badaddr = pc;
+                bp_found = true;
+                return true;
              }
+            break;
+        default:
+            /* other trigger types are not supported or irrelevant */
+            break;
          }
      }
 
      return false;
  }
 
+bool riscv_cpu_debug_check_breakpoint(CPUState *cs)
+{
+    bp_found = false;
+    g_tree_foreach(cs->breakpoints, check_breakpoints, cs);
+
+    return bp_found;
+}
+
  bool riscv_cpu_debug_check_watchpoint(CPUState *cs, CPUWatchpoint *wp)
  {
      RISCVCPU *cpu = RISCV_CPU(cs);
#8 lore raw

Re: [RFC PATCH 2/2] riscv/debug: migrate debug_check_breakpoint to use GTree breakpoints

Quoted 6 lines · Richard Henderson
Quoted 3 lines

   target/riscv/debug.c | 71 +++++++++++++++++++++++++-------------
------

   1 file changed, 41 insertions(+), 30 deletions(-)

(1) This can't be a separate patch, because the first patch can't compile

Sure, Ill fix that. Its just found this riscv case only in all archs build, so it put it saperatly. ill squash it with main patch.

Quoted 2 lines

(2) You can't use a global variable for bp_found.

I could'nt find any looping mechanism in GTree. I think there is only g_tree_foreach. Maybe i can pass it as user_data.

Quoted 2 lines

r~

Regards
~Shivang.

#9 lore raw

Re: [RFC PATCH 2/2] riscv/debug: migrate debug_check_breakpoint to use GTree breakpoints

In reply to Richard Henderson
Quoted 2 lines · Richard Henderson

(1) This can't be a separate patch, because the first patch can't compile

Sure, Ill fix that. Its just that found this riscv case, only in all archs build, so it put it saperatly. ill squash it with main patch.

Quoted 2 lines

(2) You can't use a global variable for bp_found.

I could'nt find any looping mechanism in GTree. I think there is only g_tree_foreach. Maybe i can pass it as user_data.

Quoted 2 lines

r~

Regards
~Shivang.