Skip to content

RFC change cpu->breakpoints to a GTree

Shivang Upadhyay qemu-devel qemu-riscv 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest2 patches 7 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/2accel/tcg: use GTree for faster breakpoint lookupsaccel/tcg/cpu-exec.c cpu-common.c hw/core/cpu-common.c +3 more+118 -454 replies
2/2riscv/debug: migrate debug_check_breakpoint to use GTree breakpointstarget/riscv/debug.c+41 -303 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [RFC PATCH 0/2] 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