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. Signed-off-by: Shivang Upadhyay <[email protected]> --- 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(-) diff --git a/accel/tcg/cpu-exec.c b/accel/tcg/cpu-exec.c index 9c754b0365..008919a108 100644 --- a/accel/tcg/cpu-exec.c +++ b/accel/tcg/cpu-exec.c @@ -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); } diff --git a/cpu-common.c b/cpu-common.c index 988d057d84..1488d63921 100644 --- a/cpu-common.c +++ b/cpu-common.c @@ -23,6 +23,7 @@ #include "hw/core/cpu.h" #include "qemu/lockable.h" #include "trace/trace-root.h" +#include "exec/target_page.h" QemuMutex qemu_cpu_list_lock; static QemuCond exclusive_cond; @@ -388,28 +389,77 @@ void process_queued_cpu_work(CPUState *cpu) qemu_cond_broadcast(&qemu_work_cond); } +/* Comparator for breakpoints, used by cpu->breakpoints. + * we just care for order of pc's. flags values + * are unused. + */ +static gint compare_breakpoints(gconstpointer _a, + gconstpointer _b, + gpointer user_data) +{ + CPUBreakpoint a = *(const CPUBreakpoint*)_a; + CPUBreakpoint b = *(const CPUBreakpoint*)_b; + + if (a.pc < b.pc) { + return -1; + } else if (a.pc > b.pc) { + return 1; + } + return 0; +} + +/* Comparator for page numbers, used by cpu->page_breakpoints. + */ +static gint compare_page_breakpoints(gconstpointer _a, + gconstpointer _b, + gpointer user_data) +{ + uint64_t a = *(const uint64_t*)_a; + uint64_t b = *(const uint64_t*)_b; + + if (a < b) { + return -1; + } else if (a > b) { + return 1; + } + return 0; +} + /* Add a breakpoint. */ int cpu_breakpoint_insert(CPUState *cpu, vaddr pc, int flags, CPUBreakpoint **breakpoint) { CPUBreakpoint *bp; + uint64_t *pbp; if (cpu->cc->gdb_adjust_breakpoint) { pc = cpu->cc->gdb_adjust_breakpoint(cpu, pc); } bp = g_malloc(sizeof(*bp)); + pbp = g_malloc(sizeof(*pbp)); bp->pc = pc; bp->flags = flags; - - /* keep all GDB-injected breakpoints in front */ - if (flags & BP_GDB) { - QTAILQ_INSERT_HEAD(&cpu->breakpoints, bp, entry); - } else { - QTAILQ_INSERT_TAIL(&cpu->breakpoints, bp, entry); + *pbp = pc & TARGET_PAGE_MASK; + + if (!cpu->breakpoints) { + /* + * Inserting same value as the key, and the value. + * freeing only value removal from tree. + */ + cpu->breakpoints = g_tree_new_full(compare_breakpoints, NULL, g_free, NULL); + cpu->page_breakpoints = g_tree_new_full(compare_page_breakpoints, NULL, g_free, NULL); } + /* + * For each breakpoint, we insert the breakpoint as well as + * its page number. Duplicate pages are fine, as we remove one + * page per each match. + */ + g_tree_insert(cpu->breakpoints, bp, bp); + g_tree_insert(cpu->page_breakpoints, pbp, pbp); + if (breakpoint) { *breakpoint = bp; } @@ -421,38 +471,56 @@ int cpu_breakpoint_insert(CPUState *cpu, vaddr pc, int flags, /* Remove a specific breakpoint. */ int cpu_breakpoint_remove(CPUState *cpu, vaddr pc, int flags) { - CPUBreakpoint *bp; + /* Keys for GTree lookup */ + CPUBreakpoint bp_key = {.pc = pc}, *bp; + uint64_t pbp_key = pc & TARGET_PAGE_MASK, *pbp; if (cpu->cc->gdb_adjust_breakpoint) { pc = cpu->cc->gdb_adjust_breakpoint(cpu, pc); } - QTAILQ_FOREACH(bp, &cpu->breakpoints, entry) { - if (bp->pc == pc && bp->flags == flags) { - cpu_breakpoint_remove_by_ref(cpu, bp); - return 0; - } + if (cpu->breakpoints) { + bp = g_tree_lookup(cpu->breakpoints, &bp_key); + if (bp) { + g_tree_remove(cpu->breakpoints, bp); + pbp = g_tree_lookup(cpu->page_breakpoints, &pbp_key); + if (pbp) + g_tree_remove(cpu->page_breakpoints, pbp); + else { + + /* because we added one page number per breakpoint + * we shouldn't end up with a case where we dont + * find the same page number in page_breakpoints. + */ + + g_assert_not_reached(); + } + } + return 0; } + return -ENOENT; } /* Remove a specific breakpoint by reference. */ void cpu_breakpoint_remove_by_ref(CPUState *cpu, CPUBreakpoint *bp) { - QTAILQ_REMOVE(&cpu->breakpoints, bp, entry); + uint64_t pbp = bp->pc & TARGET_PAGE_MASK; trace_breakpoint_remove(cpu->cpu_index, bp->pc, bp->flags); - g_free(bp); + + if(cpu->breakpoints) { + g_tree_remove(cpu->breakpoints, g_tree_lookup(cpu->breakpoints, &bp)); + g_tree_remove(cpu->page_breakpoints, g_tree_lookup(cpu->page_breakpoints, &pbp)); + } + } /* Remove all matching breakpoints. */ void cpu_breakpoint_remove_all(CPUState *cpu, int mask) { - CPUBreakpoint *bp, *next; - - QTAILQ_FOREACH_SAFE(bp, &cpu->breakpoints, entry, next) { - if (bp->flags & mask) { - cpu_breakpoint_remove_by_ref(cpu, bp); - } + if (cpu->breakpoints) { + g_tree_destroy(cpu->breakpoints); + g_tree_destroy(cpu->page_breakpoints); } } diff --git a/hw/core/cpu-common.c b/hw/core/cpu-common.c index e314f916f8..5c2d7ed42c 100644 --- a/hw/core/cpu-common.c +++ b/hw/core/cpu-common.c @@ -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); diff --git a/include/exec/breakpoint.h b/include/exec/breakpoint.h index 95f0482e6d..f6a6826d05 100644 --- a/include/exec/breakpoint.h +++ b/include/exec/breakpoint.h @@ -15,7 +15,6 @@ typedef struct CPUBreakpoint { vaddr pc; int flags; /* BP_* */ - QTAILQ_ENTRY(CPUBreakpoint) entry; } CPUBreakpoint; typedef struct CPUWatchpoint { diff --git a/include/hw/core/cpu.h b/include/hw/core/cpu.h index 59d601465b..be4d502621 100644 --- a/include/hw/core/cpu.h +++ b/include/hw/core/cpu.h @@ -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; diff --git a/linux-user/main.c b/linux-user/main.c index c08c73fd80..6f8016d20b 100644 --- a/linux-user/main.c +++ b/linux-user/main.c @@ -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; } -- 2.54.0
