Use a balanced binary tree rather than a simple list for watchpoints. Using an interval tree makes it easy to probe for any overlapping address.
Signed-off-by: Richard Henderson <[email protected]> --- include/exec/breakpoint.h | 7 +- include/hw/core/cpu.h | 3 +- accel/tcg/cpu-exec.c | 8 +- accel/tcg/watchpoint.c | 155 +++++++++++++++++++++----------------- hw/core/cpu-common.c | 1 - system/watchpoint.c | 43 ++++++----- target/arm/hyp_gdbstub.c | 3 +- 7 files changed, 119 insertions(+), 101 deletions(-) diff --git a/include/exec/breakpoint.h b/include/exec/breakpoint.h index bb7cbc626d..e0826a1a2d 100644 --- a/include/exec/breakpoint.h +++ b/include/exec/breakpoint.h @@ -9,7 +9,6 @@ #define EXEC_BREAKPOINT_H #include "qemu/interval-tree.h" -#include "qemu/queue.h" #include "exec/vaddr.h" #include "exec/memattrs.h" @@ -36,13 +35,11 @@ struct CPUBreakpoint { }; struct CPUWatchpoint { - vaddr vaddr; - vaddr len; + IntervalTreeNode itree; vaddr hitaddr; MemTxAttrs hitattrs; - int flags; /* BP_* */ + BreakpointFlags flags; unsigned id; - QTAILQ_ENTRY(CPUWatchpoint) entry; }; int cpu_breakpoint_insert(CPUState *cpu, vaddr pc, BreakpointFlags flags, diff --git a/include/hw/core/cpu.h b/include/hw/core/cpu.h index b8a1419860..7e19ea418d 100644 --- a/include/hw/core/cpu.h +++ b/include/hw/core/cpu.h @@ -525,8 +525,7 @@ struct CPUState { /* ice debug support */ IntervalTreeRoot breakpoints; - - QTAILQ_HEAD(, CPUWatchpoint) watchpoints; + IntervalTreeRoot watchpoints; CPUWatchpoint *watchpoint_hit; void *opaque; diff --git a/accel/tcg/cpu-exec.c b/accel/tcg/cpu-exec.c index 2762cf6705..ab299387e3 100644 --- a/accel/tcg/cpu-exec.c +++ b/accel/tcg/cpu-exec.c @@ -682,10 +682,12 @@ static inline bool cpu_handle_halt(CPUState *cpu) static inline void cpu_handle_debug_exception(CPUState *cpu) { const TCGCPUOps *tcg_ops = cpu->cc->tcg_ops; - CPUWatchpoint *wp; + IntervalTreeNode *n; - if (!cpu->watchpoint_hit) { - QTAILQ_FOREACH(wp, &cpu->watchpoints, entry) { + for (n = interval_tree_iter_first(&cpu->watchpoints, 0, -1); n; + n = interval_tree_iter_next(n, 0, -1)) { + CPUWatchpoint *wp = container_of(n, CPUWatchpoint, itree); + if (wp != cpu->watchpoint_hit) { wp->flags &= ~BP_WATCHPOINT_HIT; } } diff --git a/accel/tcg/watchpoint.c b/accel/tcg/watchpoint.c index 5ea66e9763..a7ce5fa9dd 100644 --- a/accel/tcg/watchpoint.c +++ b/accel/tcg/watchpoint.c @@ -30,38 +30,18 @@ #include "hw/core/cpu.h" #include "internal-common.h" -/* - * Return true if this watchpoint address matches the specified - * access (ie the address range covered by the watchpoint overlaps - * partially or completely with the address range covered by the - * access). - */ -static inline bool watchpoint_address_matches(CPUWatchpoint *wp, - vaddr addr, vaddr len) -{ - /* - * We know the lengths are non-zero, but a little caution is - * required to avoid errors in the case where the range ends - * exactly at the top of the address space and so addr + len - * wraps round to zero. - */ - vaddr wpend = wp->vaddr + wp->len - 1; - vaddr addrend = addr + len - 1; - - return !(addr > wpend || wp->vaddr > addrend); -} - /* Return flags for watchpoints that match addr + prot. */ BreakpointFlags cpu_watchpoint_address_matches(CPUState *cpu, vaddr addr, vaddr len) { - CPUWatchpoint *wp; + vaddr last = addr + len - 1; BreakpointFlags ret = 0; + IntervalTreeNode *n; - QTAILQ_FOREACH(wp, &cpu->watchpoints, entry) { - if (watchpoint_address_matches(wp, addr, len)) { - ret |= wp->flags; - } + for (n = interval_tree_iter_first(&cpu->watchpoints, addr, last); n; + n = interval_tree_iter_next(n, addr, last)) { + CPUWatchpoint *wp = container_of(n, CPUWatchpoint, itree); + ret |= wp->flags; } return ret; } @@ -70,7 +50,10 @@ BreakpointFlags cpu_watchpoint_address_matches(CPUState *cpu, void cpu_check_watchpoint(CPUState *cpu, vaddr addr, vaddr len, MemTxAttrs attrs, BreakpointFlags flags, uintptr_t ra) { - CPUWatchpoint *wp; + vaddr last = addr + len - 1; + IntervalTreeNode *n; + CPUWatchpoint *found_wp = NULL; + bool have_cpu_wp = false; assert(tcg_enabled()); if (cpu->watchpoint_hit) { @@ -88,56 +71,90 @@ void cpu_check_watchpoint(CPUState *cpu, vaddr addr, vaddr len, if (cpu->cc->tcg_ops->adjust_watchpoint_address) { /* this is currently used only by ARM BE32 */ addr = cpu->cc->tcg_ops->adjust_watchpoint_address(cpu, addr, len); + last = addr + len - 1; } assert((flags & ~BP_MEM_ACCESS) == 0); - QTAILQ_FOREACH(wp, &cpu->watchpoints, entry) { - BreakpointFlags hit_flags = wp->flags & flags; - if (hit_flags && watchpoint_address_matches(wp, addr, len)) { - if (replay_running_debug()) { - /* - * replay_breakpoint reads icount. - * Force recompile to succeed, because icount may - * be read only at the end of the block. - */ - if (!cpu->neg.can_do_io) { - /* Force execution of one insn next time. */ - cpu->cflags_next_tb = 1 | CF_NOIRQ | curr_cflags(cpu); - cpu_loop_exit_restore(cpu, ra); - } - /* - * Don't process the watchpoints when we are - * in a reverse debugging operation. - */ - replay_breakpoint(); - return; - } + for (n = interval_tree_iter_first(&cpu->watchpoints, addr, last); n; + n = interval_tree_iter_next(n, addr, last)) { + CPUWatchpoint *wp = container_of(n, CPUWatchpoint, itree); - wp->flags |= hit_flags << BP_HIT_SHIFT; - wp->hitaddr = MAX(addr, wp->vaddr); - wp->hitattrs = attrs; - - if (wp->flags & BP_CPU - && cpu->cc->tcg_ops->debug_check_watchpoint - && !cpu->cc->tcg_ops->debug_check_watchpoint(cpu, wp)) { + if (wp->flags & flags) { + /* + * Prefer GDB over CPU watchpoint, so we can take the first + * GDB watchpoint that we see. + */ + if (wp->flags & BP_GDB) { wp->flags &= ~BP_WATCHPOINT_HIT; - continue; - } - cpu->watchpoint_hit = wp; + wp->flags |= flags << BP_HIT_SHIFT; + wp->hitaddr = MAX(addr, wp->itree.start); + wp->hitattrs = attrs; - /* This call also restores vCPU state */ - tb_check_watchpoint(cpu, ra); - if (wp->flags & BP_STOP_BEFORE_ACCESS) { - cpu->exception_index = EXCP_DEBUG; - cpu_loop_exit(cpu); - } else { - /* Force execution of one insn next time. */ - cpu->cflags_next_tb = 1 | CF_NOIRQ | curr_cflags(cpu); - cpu_loop_exit_noexc(cpu); + found_wp = wp; + goto found; } - } else { - wp->flags &= ~BP_WATCHPOINT_HIT; + have_cpu_wp = true; } } + + if (have_cpu_wp) { + const TCGCPUOps *tcg_ops = cpu->cc->tcg_ops; + + for (n = interval_tree_iter_first(&cpu->watchpoints, addr, last); n; + n = interval_tree_iter_next(n, addr, last)) { + CPUWatchpoint *wp = container_of(n, CPUWatchpoint, itree); + + if ((wp->flags & BP_CPU) && (wp->flags & flags)) { + wp->flags &= ~BP_WATCHPOINT_HIT; + wp->flags |= flags << BP_HIT_SHIFT; + wp->hitaddr = MAX(addr, wp->itree.start); + wp->hitattrs = attrs; + + if (tcg_ops->debug_check_watchpoint + && !tcg_ops->debug_check_watchpoint(cpu, wp)) { + wp->flags &= ~BP_WATCHPOINT_HIT; + continue; + } + + found_wp = wp; + goto found; + } + } + } + return; + + found: + if (replay_running_debug()) { + /* + * replay_breakpoint reads icount. + * Force recompile to succeed, because icount may + * be read only at the end of the block. + */ + if (!cpu->neg.can_do_io) { + /* Force execution of one insn next time. */ + cpu->cflags_next_tb = 1 | CF_NOIRQ | curr_cflags(cpu); + cpu_loop_exit_restore(cpu, ra); + } + /* + * Don't process the watchpoints when we are + * in a reverse debugging operation. + */ + replay_breakpoint(); + return; + } + + cpu->watchpoint_hit = found_wp; + + /* This call also restores vCPU state */ + tb_check_watchpoint(cpu, ra); + if (found_wp->flags & BP_STOP_BEFORE_ACCESS) { + cpu->exception_index = EXCP_DEBUG; + cpu_loop_exit(cpu); + } else { + /* Force execution of one insn next time. */ + cpu->cflags_next_tb = 1 | CF_NOIRQ | curr_cflags(cpu); + cpu_loop_exit_noexc(cpu); + } + qemu_build_not_reached(); } diff --git a/hw/core/cpu-common.c b/hw/core/cpu-common.c index 5c2d7ed42c..868c7c4d46 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->watchpoints); cpu_exec_initfn(cpu); diff --git a/system/watchpoint.c b/system/watchpoint.c index a618bb5acd..ed505da403 100644 --- a/system/watchpoint.c +++ b/system/watchpoint.c @@ -30,26 +30,23 @@ int cpu_watchpoint_insert(CPUState *cpu, vaddr addr, vaddr len, CPUWatchpoint **watchpoint) { CPUWatchpoint *wp; + vaddr last = addr + len - 1; vaddr in_page; /* forbid ranges which are empty or run off the end of the address space */ - if (len == 0 || (addr + len - 1) < addr) { + if (len == 0 || last < addr) { error_report("tried to set invalid watchpoint at %" VADDR_PRIx ", len=%" VADDR_PRIu, addr, len); return -EINVAL; } - wp = g_malloc(sizeof(*wp)); - wp->vaddr = addr; - wp->len = len; + wp = g_new0(CPUWatchpoint, 1); + + wp->itree.start = addr; + wp->itree.last = last; wp->flags = flags; - /* keep all GDB-injected watchpoints in front */ - if (flags & BP_GDB) { - QTAILQ_INSERT_HEAD(&cpu->watchpoints, wp, entry); - } else { - QTAILQ_INSERT_TAIL(&cpu->watchpoints, wp, entry); - } + interval_tree_insert(&wp->itree, &cpu->watchpoints); in_page = -(addr | TARGET_PAGE_MASK); if (len <= in_page) { @@ -68,11 +65,16 @@ int cpu_watchpoint_insert(CPUState *cpu, vaddr addr, vaddr len, int cpu_watchpoint_remove(CPUState *cpu, vaddr addr, vaddr len, BreakpointFlags flags) { - CPUWatchpoint *wp; + vaddr last = addr + len - 1; + IntervalTreeNode *n; - QTAILQ_FOREACH(wp, &cpu->watchpoints, entry) { - if (addr == wp->vaddr && len == wp->len - && flags == (wp->flags & ~BP_WATCHPOINT_HIT)) { + for (n = interval_tree_iter_first(&cpu->watchpoints, addr, addr); n; + n = interval_tree_iter_next(n, addr, addr)) { + CPUWatchpoint *wp = container_of(n, CPUWatchpoint, itree); + + if (addr == wp->itree.start && + last == wp->itree.last && + flags == (wp->flags & ~BP_WATCHPOINT_HIT)) { cpu_watchpoint_remove_by_ref(cpu, wp); return 0; } @@ -83,19 +85,20 @@ int cpu_watchpoint_remove(CPUState *cpu, vaddr addr, vaddr len, /* Remove a specific watchpoint by reference. */ void cpu_watchpoint_remove_by_ref(CPUState *cpu, CPUWatchpoint *watchpoint) { - QTAILQ_REMOVE(&cpu->watchpoints, watchpoint, entry); - - tlb_flush_page(cpu, watchpoint->vaddr); - + interval_tree_remove(&watchpoint->itree, &cpu->watchpoints); + tlb_flush_page(cpu, watchpoint->itree.start); g_free(watchpoint); } /* Remove all matching watchpoints. */ void cpu_watchpoint_remove_all(CPUState *cpu, BreakpointFlags mask) { - CPUWatchpoint *wp, *next; + IntervalTreeNode *n = interval_tree_iter_first(&cpu->watchpoints, 0, -1); - QTAILQ_FOREACH_SAFE(wp, &cpu->watchpoints, entry, next) { + while (n) { + CPUWatchpoint *wp = container_of(n, CPUWatchpoint, itree); + + n = interval_tree_iter_next(n, 0, -1); if (wp->flags & mask) { cpu_watchpoint_remove_by_ref(cpu, wp); } diff --git a/target/arm/hyp_gdbstub.c b/target/arm/hyp_gdbstub.c index c91efa7495..8dd1fbd440 100644 --- a/target/arm/hyp_gdbstub.c +++ b/target/arm/hyp_gdbstub.c @@ -130,7 +130,8 @@ int insert_gdbstub_hw_watchpoint(vaddr addr, vaddr len, GdbBreakpointType type) HWWatchpoint wp = { .wcr = R_DBGWCR_E_MASK, /* E=1, enable */ .wvr = addr & (~0x7ULL), - .details = { .vaddr = addr, .len = len } + .details.itree.start = addr, + .details.itree.last = addr + len - 1, }; if (cur_hw_wps >= max_hw_wps) { -- 2.43.0
