RFC change cpu->breakpoints to a GTree
Get series with b4
b4 am [email protected]Versions newest first
- v1 RFC Latest2 patches 7 repliesIn review
Patches in v1 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/2 | accel/tcg: use GTree for faster breakpoint lookupsaccel/ cpu-common.c hw/ +3 more | +118 | 4 replies | |
| 2/2 | riscv/debug: migrate debug_check_breakpoint to use GTree breakpointstarget/ | +41 | 3 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
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