change cpu->breakpoints to a GTree
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
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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
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 ofcpu->breakpointson every breakpoint check. As the number of breakpoints grows, this increases the cost of each lookup.Replace
cpu->breakpointswith 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.
Signed-off-by Shivang Upadhyay<[email protected]>
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~
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
Re: [RFC PATCH 1/2] accel/tcg: use GTree for faster breakpoint lookups
In reply to Richard HendersonQuoted 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.
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~
RFC PATCH 2/2 riscv/debug: migrate debug_check_breakpoint to use GTree breakpoints
In reply to Shivang Upadhyayas 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
@@ -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
Re: [RFC PATCH 2/2] riscv/debug: migrate debug_check_breakpoint to use GTree breakpoints
Quoted 5 lines · Shivang Upadhyay
as
cpu->breakpointsis migrated to GTree, change the breakpoint looping fromQTAILQ_FOREACHtog_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@@ -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);
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.
Re: [RFC PATCH 2/2] riscv/debug: migrate debug_check_breakpoint to use GTree breakpoints
In reply to Richard HendersonQuoted 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.