Re: [PATCH v2 17/54] accel/tcg: Replace victim_tlb_hit with tlbtree_hit

[Pierrick Bouvier <pierrick.bouvier@linaro.org>]

On 11/14/24 08:00, Richard Henderson wrote:
> Change from a linear search on the victim tlb
> to a balanced binary tree search on the interval tree.
> 
> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
> ---
>   accel/tcg/cputlb.c | 59 ++++++++++++++++++++++++----------------------
>   1 file changed, 31 insertions(+), 28 deletions(-)
> 
> diff --git a/accel/tcg/cputlb.c b/accel/tcg/cputlb.c
> index 3aab72ea82..ea4b78866b 100644
> --- a/accel/tcg/cputlb.c
> +++ b/accel/tcg/cputlb.c
> @@ -1384,35 +1384,38 @@ static void io_failed(CPUState *cpu, CPUTLBEntryFull *full, vaddr addr,
>       }
>   }
>   
> -/* Return true if ADDR is present in the victim tlb, and has been copied
> -   back to the main tlb.  */
> -static bool victim_tlb_hit(CPUState *cpu, size_t mmu_idx, size_t index,
> -                           MMUAccessType access_type, vaddr addr)
> +/*
> + * Return true if ADDR is present in the interval tree,
> + * and has been copied back to the main tlb.
> + */
> +static bool tlbtree_hit(CPUState *cpu, int mmu_idx,
> +                        MMUAccessType access_type, vaddr addr)
>   {
> -    size_t vidx;
> +    CPUTLBDesc *desc = &cpu->neg.tlb.d[mmu_idx];
> +    CPUTLBDescFast *fast = &cpu->neg.tlb.f[mmu_idx];
> +    CPUTLBEntryTree *node;
> +    size_t index;
>   
>       assert_cpu_is_self(cpu);
> -    for (vidx = 0; vidx < CPU_VTLB_SIZE; ++vidx) {
> -        CPUTLBEntry *vtlb = &cpu->neg.tlb.d[mmu_idx].vtable[vidx];
> -
> -        if (tlb_hit(tlb_read_idx(vtlb, access_type), addr)) {
> -            /* Found entry in victim tlb, swap tlb and iotlb.  */
> -            CPUTLBEntry tmptlb, *tlb = &cpu->neg.tlb.f[mmu_idx].table[index];
> -
> -            qemu_spin_lock(&cpu->neg.tlb.c.lock);
> -            copy_tlb_helper_locked(&tmptlb, tlb);
> -            copy_tlb_helper_locked(tlb, vtlb);
> -            copy_tlb_helper_locked(vtlb, &tmptlb);
> -            qemu_spin_unlock(&cpu->neg.tlb.c.lock);
> -
> -            CPUTLBEntryFull *f1 = &cpu->neg.tlb.d[mmu_idx].fulltlb[index];
> -            CPUTLBEntryFull *f2 = &cpu->neg.tlb.d[mmu_idx].vfulltlb[vidx];
> -            CPUTLBEntryFull tmpf;
> -            tmpf = *f1; *f1 = *f2; *f2 = tmpf;
> -            return true;
> -        }
> +    node = tlbtree_lookup_addr(desc, addr);
> +    if (!node) {
> +        /* There is no cached mapping for this page. */
> +        return false;
>       }
> -    return false;
> +
> +    if (!tlb_hit(tlb_read_idx(&node->copy, access_type), addr)) {
> +        /* This access is not permitted. */
> +        return false;
> +    }
> +
> +    /* Install the cached entry. */
> +    index = tlbfast_index(fast, addr);
> +    qemu_spin_lock(&cpu->neg.tlb.c.lock);
> +    copy_tlb_helper_locked(&fast->table[index], &node->copy);
> +    qemu_spin_unlock(&cpu->neg.tlb.c.lock);
> +
> +    desc->fulltlb[index] = node->full;
> +    return true;
>   }
>   
>   static void notdirty_write(CPUState *cpu, vaddr mem_vaddr, unsigned size,
> @@ -1453,7 +1456,7 @@ static int probe_access_internal(CPUState *cpu, vaddr addr,
>       CPUTLBEntryFull *full;
>   
>       if (!tlb_hit(tlb_addr, addr)) {
> -        if (!victim_tlb_hit(cpu, mmu_idx, index, access_type, addr)) {
> +        if (!tlbtree_hit(cpu, mmu_idx, access_type, addr)) {
>               if (!tlb_fill_align(cpu, addr, access_type, mmu_idx,
>                                   0, fault_size, nonfault, retaddr)) {
>                   /* Non-faulting page table read failed.  */
> @@ -1733,7 +1736,7 @@ static bool mmu_lookup1(CPUState *cpu, MMULookupPageData *data, MemOp memop,
>   
>       /* If the TLB entry is for a different page, reload and try again.  */
>       if (!tlb_hit(tlb_addr, addr)) {
> -        if (!victim_tlb_hit(cpu, mmu_idx, index, access_type, addr)) {
> +        if (!tlbtree_hit(cpu, mmu_idx, access_type, addr)) {
>               tlb_fill_align(cpu, addr, access_type, mmu_idx,
>                              memop, data->size, false, ra);
>               maybe_resized = true;
> @@ -1912,7 +1915,7 @@ static void *atomic_mmu_lookup(CPUState *cpu, vaddr addr, MemOpIdx oi,
>       /* Check TLB entry and enforce page permissions.  */
>       flags = TLB_FLAGS_MASK;
>       if (!tlb_hit(tlb_addr_write(tlbe), addr)) {
> -        if (!victim_tlb_hit(cpu, mmu_idx, index, MMU_DATA_STORE, addr)) {
> +        if (!tlbtree_hit(cpu, mmu_idx, MMU_DATA_STORE, addr)) {
>               tlb_fill_align(cpu, addr, MMU_DATA_STORE, mmu_idx,
>                              mop, size, false, retaddr);
>               did_tlb_fill = true;

Reviewed-by: Pierrick Bouvier <pierrick.bouvier@linaro.org>