Re: [PATCH v3 15/51] cpu: Use interval-tree for CPUBreakpoint

On 7/10/26 22:53, Richard Henderson wrote:
> Use a balanced binary tree rather than a simple list for breakpoints.
> Using an interval tree makes it easy to probe for all breakpoints on
> a virtual page.
> 
> Signed-off-by: Richard Henderson <[email protected]>
> ---
>   include/exec/breakpoint.h   |  4 +--
>   include/hw/core/cpu.h       |  3 +-
>   accel/tcg/cpu-exec.c        | 58 +++++++++++++++++++++----------------
>   accel/whpx/whpx-common.c    |  9 +++---
>   cpu-common.c                | 46 +++++++++++++++--------------
>   hw/core/cpu-common.c        |  1 -
>   linux-user/main.c           | 14 ++++++---
>   target/i386/whpx/whpx-all.c | 15 +++++-----
>   8 files changed, 84 insertions(+), 66 deletions(-)

[...]

> @@ -312,33 +312,34 @@ 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) {
> -            bool match_bp = false;
> -
> -            if (bp->flags & BP_GDB) {
> -                match_bp = true;
> -            } else if (bp->flags & BP_CPU) {
> +    n = interval_tree_iter_first(&cpu->breakpoints, pc, pc);
> +    if (n) {
>   #ifdef CONFIG_USER_ONLY
> -                g_assert_not_reached();
> +        bp = container_of(n, CPUBreakpoint, itree);
> +        assert(bp->flags & BP_GDB);
> +        goto found;
>   #else
> -                const TCGCPUOps *tcg_ops = cpu->cc->tcg_ops;
> -                assert(tcg_ops->debug_check_breakpoint);
> -                match_bp = tcg_ops->debug_check_breakpoint(cpu, bp);
> -#endif
> +        /* Prefer GDB breakpoint over architectural breakpoint. */
> +        do {
> +            bp = container_of(n, CPUBreakpoint, itree);
> +            if (bp->flags & BP_GDB) {
> +                goto found;
>               }
> +            n = interval_tree_iter_next(n, pc, pc);
> +        } while (n);
>   
> -            if (match_bp) {
> -                cpu->exception_index = EXCP_DEBUG;
> -                return true;
> +        const TCGCPUOps *tcg_ops = cpu->cc->tcg_ops;
> +        assert(tcg_ops->debug_check_breakpoint);
> +
> +        for (n = interval_tree_iter_first(&cpu->breakpoints, pc, pc); n;
> +             n = interval_tree_iter_next(n, pc, pc)) {
> +            bp = container_of(n, CPUBreakpoint, itree);
> +            if ((bp->flags & BP_CPU) &&
> +                tcg_ops->debug_check_breakpoint(cpu, bp)) {
> +                goto found;
>               }


Walking the tree twice feels slightly inefficient, but the only
alternative I can think of entails calling
tcg_ops->debug_check_breakpoint() for each node, which may be even
worse.

Reviewed-by: Ilya Leoskevich <[email protected]>