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

On 7/14/26 05:39, Ilya Leoshkevich wrote:
> 
> 
> 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.

That's what I thought -- if we ever called debug_check_breakpoint when a gdb breakpoint 
exists, then we're doing something wrong.  The only alternative is to separate the two 
types of breakpoints into two different interval trees.


r~

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