Re: [PATCH v3 15/51] cpu: Use interval-tree for CPUBreakpoint

[Ilya Leoshkevich]

On 7/10/26 22:53, Richard Henderson wrote:

Use a balanced binary tree rather than a simple list for breakpoints.
Using an interval tree makes it easy to probe for all breakpoints on
a virtual page.

Signed-off-by: Richard Henderson <richard.hender...@linaro.org>
---
  include/exec/breakpoint.h   |  4 +--
  include/hw/core/cpu.h       |  3 +-
  accel/tcg/cpu-exec.c        | 58 +++++++++++++++++++++----------------
  accel/whpx/whpx-common.c    |  9 +++---
  cpu-common.c                | 46 +++++++++++++++--------------
  hw/core/cpu-common.c        |  1 -
  linux-user/main.c           | 14 ++++++---
  target/i386/whpx/whpx-all.c | 15 +++++-----
  8 files changed, 84 insertions(+), 66 deletions(-)

[...]

@@ -312,33 +312,34 @@ 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) {
-            bool match_bp = false;
-
-            if (bp->flags & BP_GDB) {
-                match_bp = true;
-            } else if (bp->flags & BP_CPU) {
+    n = interval_tree_iter_first(&cpu->breakpoints, pc, pc);
+    if (n) {
  #ifdef CONFIG_USER_ONLY
-                g_assert_not_reached();
+        bp = container_of(n, CPUBreakpoint, itree);
+        assert(bp->flags & BP_GDB);
+        goto found;
  #else
-                const TCGCPUOps *tcg_ops = cpu->cc->tcg_ops;
-                assert(tcg_ops->debug_check_breakpoint);
-                match_bp = tcg_ops->debug_check_breakpoint(cpu, bp);
-#endif
+        /* Prefer GDB breakpoint over architectural breakpoint. */
+        do {
+            bp = container_of(n, CPUBreakpoint, itree);
+            if (bp->flags & BP_GDB) {
+                goto found;
              }
+            n = interval_tree_iter_next(n, pc, pc);
+        } while (n);

- if (match_bp) {

-                cpu->exception_index = EXCP_DEBUG;
-                return true;
+        const TCGCPUOps *tcg_ops = cpu->cc->tcg_ops;
+        assert(tcg_ops->debug_check_breakpoint);
+
+        for (n = interval_tree_iter_first(&cpu->breakpoints, pc, pc); n;
+             n = interval_tree_iter_next(n, pc, pc)) {
+            bp = container_of(n, CPUBreakpoint, itree);
+            if ((bp->flags & BP_CPU) &&
+                tcg_ops->debug_check_breakpoint(cpu, bp)) {
+                goto found;
              }

Walking the tree twice feels slightly inefficient, but the only
alternative I can think of entails calling
tcg_ops->debug_check_breakpoint() for each node, which may be even
worse.

Reviewed-by: Ilya Leoskevich <i...@linux.ibm.com>