| Message ID | 20241009150855.804605-15-richard.henderson@linaro.org |
|---|---|
| State | Superseded |
| Headers | show |
| Series | accel/tcg: Convert victim tlb to IntervalTree | expand |
On 10/9/24 08:08, 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 | 62 +++++++++++++++++++++++----------------------- > 1 file changed, 31 insertions(+), 31 deletions(-) > > diff --git a/accel/tcg/cputlb.c b/accel/tcg/cputlb.c > index ec989f1290..b10b0a357c 100644 > --- a/accel/tcg/cputlb.c > +++ b/accel/tcg/cputlb.c > @@ -1398,36 +1398,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 page) > +/* > + * 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]; > - uint64_t cmp = tlb_read_idx(vtlb, access_type); > - > - if (cmp == page) { > - /* 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; > + } This is not something we were checking before. If this is an addition, maybe it would be better to split this out of this commit. Or maybe I missed a step in previous commits :) > + > + /* 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, > @@ -1469,7 +1471,7 @@ static int probe_access_internal(CPUState *cpu, vaddr addr, > CPUTLBEntryFull *full; > > if (!tlb_hit_page(tlb_addr, page_addr)) { > - if (!victim_tlb_hit(cpu, mmu_idx, index, access_type, page_addr)) { > + if (!tlbtree_hit(cpu, mmu_idx, access_type, page_addr)) { > if (!tlb_fill_align(cpu, addr, access_type, mmu_idx, > 0, fault_size, nonfault, retaddr)) { > /* Non-faulting page table read failed. */ > @@ -1749,8 +1751,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 & TARGET_PAGE_MASK)) { > + 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; > @@ -1929,8 +1930,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 & TARGET_PAGE_MASK)) { > + 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; Else, hurrah! Reviewed-by: Pierrick Bouvier <pierrick.bouvier@linaro.org>
On 10/9/24 17:10, Pierrick Bouvier wrote: >> +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]; >> - uint64_t cmp = tlb_read_idx(vtlb, access_type); >> - >> - if (cmp == page) { ... >> + if (!tlb_hit(tlb_read_idx(&node->copy, access_type), addr)) { >> + /* This access is not permitted. */ >> + return false; >> + } > > This is not something we were checking before. If this is an addition, maybe it would be > better to split this out of this commit. Or maybe I missed a step in previous commits :) It's there, with the comparison and page mask, but I agree it's not obvious. r~
On 10/10/24 12:29, Richard Henderson wrote: > On 10/9/24 17:10, Pierrick Bouvier wrote: >>> +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]; >>> - uint64_t cmp = tlb_read_idx(vtlb, access_type); >>> - >>> - if (cmp == page) { > ... >>> + if (!tlb_hit(tlb_read_idx(&node->copy, access_type), addr)) { >>> + /* This access is not permitted. */ >>> + return false; >>> + } >> >> This is not something we were checking before. If this is an addition, maybe it would be >> better to split this out of this commit. Or maybe I missed a step in previous commits :) > > It's there, with the comparison and page mask, but I agree it's not obvious. > > > r~ Subtle indeed, you don't expect & TARGET_PAGE_MASK to imply that protection is checked, even if that makes sense once said.
diff --git a/accel/tcg/cputlb.c b/accel/tcg/cputlb.c index ec989f1290..b10b0a357c 100644 --- a/accel/tcg/cputlb.c +++ b/accel/tcg/cputlb.c @@ -1398,36 +1398,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 page) +/* + * 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]; - uint64_t cmp = tlb_read_idx(vtlb, access_type); - - if (cmp == page) { - /* 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, @@ -1469,7 +1471,7 @@ static int probe_access_internal(CPUState *cpu, vaddr addr, CPUTLBEntryFull *full; if (!tlb_hit_page(tlb_addr, page_addr)) { - if (!victim_tlb_hit(cpu, mmu_idx, index, access_type, page_addr)) { + if (!tlbtree_hit(cpu, mmu_idx, access_type, page_addr)) { if (!tlb_fill_align(cpu, addr, access_type, mmu_idx, 0, fault_size, nonfault, retaddr)) { /* Non-faulting page table read failed. */ @@ -1749,8 +1751,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 & TARGET_PAGE_MASK)) { + 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; @@ -1929,8 +1930,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 & TARGET_PAGE_MASK)) { + 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;
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 | 62 +++++++++++++++++++++++----------------------- 1 file changed, 31 insertions(+), 31 deletions(-)