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.hender...@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.bouv...@linaro.org>
