Dynamic TLB sizing
cover Dynamic TLB sizing
After reading this paper [1], I wondered whether how far one could push the idea of dynamic TLB resizing. We discussed it briefly in this thread:
https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg02340.html
Since then, (1) rth helped me (thanks!) with TCG backend code, and (2) I've abandoned the idea of substituting malloc for memset, and instead focused on dynamically resizing the TLBs. The rationale is that if a process touches a lot of memory, having a large TLB will pay off, since the perf gains will dwarf the increased cost of flushing via memset.
This series shows that the indirection necessary to do this does not cause a perf decrease, at least for x86_64 hosts.
This series is incomplete, since it only implements changes to the i386 backend, and it probably only works on x86_64. But the whole point is to (1) see whether the performance gains are worth it, and (2) discuss how crazy this approach is. I was looking for things to break badly, but so far I've found no obvious issues. But there might be some assumptions about the TLB size baked in the code that I might have missed, so please point those out if they exist.
Performance numbers are in the last patch.
You can fetch this series from:
https://github.com/cota/qemu/tree/tlb-dyn
Note that it applies on top of my tlb-lock-v3 series:
https://lists.gnu.org/archive/html/qemu-devel/2018-10/msg01087.html
Thanks,
Emilio
[1] "Optimizing Memory Translation Emulation in Full System Emulators", Tong et al, TACO'15 https://dl.acm.org/citation.cfm?id=2686034
RFC 1/6 (XXX) cputlb: separate MMU allocation + run-time sizing
No dynamic sizing yet, but the indirection is there.
XXX:
- convert other TCG backends
--- accel/tcg/softmmu_template.h | 14 +++++---- include/exec/cpu-defs.h | 14 ++++++--- include/exec/cpu_ldst.h | 2 +- include/exec/cpu_ldst_template.h | 6 ++-- accel/tcg/cputlb.c | 49 +++++++++++++++++++++----------- tcg/i386/tcg-target.inc.c | 26 ++++++++--------- 6 files changed, 68 insertions(+), 43 deletions(-)
accel/tcg/softmmu_template.h +8 -6
@@ -112,7 +112,7 @@ WORD_TYPE helper_le_ld_name(CPUArchState *env, target_ulong addr, TCGMemOpIdx oi, uintptr_t retaddr) { unsigned mmu_idx = get_mmuidx(oi); -int index = (addr >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); +int index = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 );target_ulong tlb_addr = env->tlb_table[mmu_idx][index].ADDR_READ;unsigned a_bits =get_alignment_bits (get_memop (oi));uintptr_t haddr;
@@ -180,7 +180,7 @@ WORD_TYPE helper_be_ld_name(CPUArchState *env, target_ulong addr, TCGMemOpIdx oi, uintptr_t retaddr) { unsigned mmu_idx = get_mmuidx(oi); -int index = (addr >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); +int index = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 );target_ulong tlb_addr = env->tlb_table[mmu_idx][index].ADDR_READ;unsigned a_bits =get_alignment_bits (get_memop (oi));uintptr_t haddr;
@@ -276,7 +276,7 @@ void helper_le_st_name(CPUArchState *env, target_ulong addr, DATA_TYPE val, TCGMemOpIdx oi, uintptr_t retaddr) { unsigned mmu_idx = get_mmuidx(oi); -int index = (addr >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); +int index = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 );target_ulong tlb_addr =atomic_read (&env->tlb_table[mmu_idx][index].addr_write);unsigned a_bits =get_alignment_bits (get_memop (oi));
@@ -322,7 +322,8 @@ void helper_le_st_name(CPUArchState *env, target_ulong addr, DATA_TYPE val,is already guaranteed to be filled, and that the second page cannot evict the first. */ page2 = (addr +DATA_SIZE ) &TARGET_PAGE_MASK ; - index2 = (page2 >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); + index2 = (page2 >>TARGET_PAGE_BITS ) & + (env->tlb_desc[mmu_idx].size -1 ); tlb_addr2 =atomic_read (&env->tlb_table[mmu_idx][index2].addr_write);if (!tlb_hit_page (tlb_addr2, page2) && !VICTIM_TLB_HIT (addr_write, page2)) {
@@ -355,7 +356,7 @@ void helper_be_st_name(CPUArchState *env, target_ulong addr, DATA_TYPE val, TCGMemOpIdx oi, uintptr_t retaddr) { unsigned mmu_idx = get_mmuidx(oi); -int index = (addr >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); +int index = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 );target_ulong tlb_addr =atomic_read (&env->tlb_table[mmu_idx][index].addr_write);unsigned a_bits =get_alignment_bits (get_memop (oi));
@@ -401,7 +402,8 @@ void helper_be_st_name(CPUArchState *env, target_ulong addr, DATA_TYPE val,is already guaranteed to be filled, and that the second page cannot evict the first. */ page2 = (addr +DATA_SIZE ) &TARGET_PAGE_MASK ; - index2 = (page2 >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); + index2 = (page2 >>TARGET_PAGE_BITS ) & + (env->tlb_desc[mmu_idx].size -1 ); tlb_addr2 =atomic_read (&env->tlb_table[mmu_idx][index2].addr_write);if (!tlb_hit_page (tlb_addr2, page2) && !VICTIM_TLB_HIT (addr_write, page2)) {
include/exec/cpu-defs.h +10 -4
@@ -141,13 +141,19 @@ typedef struct CPUIOTLBEntry {MemTxAttrs attrs; } CPUIOTLBEntry; -#define CPU_COMMON_TLB \ +typedef struct CPUTLBDesc { +size_t size; +size_t mask;/* (.size - 1) << CPU_TLB_ENTRY_BITS for TLB fast path */ +}CPUTLBDesc ; + +#define CPU_COMMON_TLB \/* The meaning of the MMU modes is defined in the target code. */ \ -/* tlb_lock serializes updates to tlb_table and tlb_v_table */ \ +/* tlb_lock serializes updates to tlb_desc, tlb_table and tlb_v_table */ \ QemuSpin tlb_lock; \ - CPUTLBEntry tlb_table[NB_MMU_MODES][CPU_TLB_SIZE]; \ + CPUTLBDesc tlb_desc[NB_MMU_MODES]; \ + CPUTLBEntry *tlb_table[NB_MMU_MODES]; \ CPUTLBEntry tlb_v_table[NB_MMU_MODES][CPU_VTLB_SIZE]; \ - CPUIOTLBEntry iotlb[NB_MMU_MODES][CPU_TLB_SIZE]; \ + CPUIOTLBEntry *iotlb[NB_MMU_MODES]; \ CPUIOTLBEntry iotlb_v[NB_MMU_MODES][CPU_VTLB_SIZE]; \ size_t tlb_flush_count; \ target_ulong tlb_flush_addr; \
include/exec/cpu_ldst.h +1 -1
@@ -416,7 +416,7 @@ static inline void *tlb_vaddr_to_host(CPUArchState *env, abi_ptr addr,#if defined(CONFIG_USER_ONLY )return g2h (addr);#else -int index = (addr >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); +int index = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 );CPUTLBEntry *tlbentry = &env->tlb_table[mmu_idx][index];abi_ptr tlb_addr;uintptr_t haddr;
include/exec/cpu_ldst_template.h +3 -3
@@ -94,8 +94,8 @@ glue(glue(glue(cpu_ld, USUFFIX), MEMSUFFIX), _ra)(CPUArchState *env,#endif addr = ptr; - page_index = (addr >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); mmu_idx =CPU_MMU_INDEX ; + page_index = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 );if (unlikely (env->tlb_table[mmu_idx][page_index].ADDR_READ != (addr & (TARGET_PAGE_MASK | (DATA_SIZE -1 ))))) { oi =make_memop_idx (SHIFT , mmu_idx);
@@ -132,8 +132,8 @@ glue(glue(glue(cpu_lds, SUFFIX), MEMSUFFIX), _ra)(CPUArchState *env,#endif addr = ptr; - page_index = (addr >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); mmu_idx =CPU_MMU_INDEX ; + page_index = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 );if (unlikely (env->tlb_table[mmu_idx][page_index].ADDR_READ != (addr & (TARGET_PAGE_MASK | (DATA_SIZE -1 ))))) { oi =make_memop_idx (SHIFT , mmu_idx);
@@ -174,8 +174,8 @@ glue(glue(glue(cpu_st, SUFFIX), MEMSUFFIX), _ra)(CPUArchState *env,#endif addr = ptr; - page_index = (addr >>TARGET_PAGE_BITS ) & (CPU_TLB_SIZE -1 ); mmu_idx =CPU_MMU_INDEX ; + page_index = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 );if (unlikely (atomic_read (&env->tlb_table[mmu_idx][page_index].addr_write) != (addr & (TARGET_PAGE_MASK | (DATA_SIZE -1 ))))) { oi =make_memop_idx (SHIFT , mmu_idx);
accel/tcg/cputlb.c +33 -16
158 lines not on this page · raw message
tcg/i386/tcg-target.inc.c +13 -13
@@ -330,6 +330,7 @@ static inline int tcg_target_const_match(tcg_target_long val, TCGType type,#define OPC_ARITH_GvEv (0x03)/* ... plus (ARITH_FOO << 3) */ #define OPC_ANDN (0xf2 | P_EXT38)#define OPC_ADD_GvEv (OPC_ARITH_GvEv | (ARITH_ADD << 3)) +#define OPC_AND_GvEv (OPC_ARITH_GvEv | (ARITH_AND << 3))#define OPC_BLENDPS (0x0c | P_EXT3A | P_DATA16)#define OPC_BSF (0xbc | P_EXT)#define OPC_BSR (0xbd | P_EXT)
@@ -1633,6 +1634,15 @@ static inline void tcg_out_tlb_load(TCGContext *s, TCGReg addrlo, TCGReg addrhi, }tcg_out_mov (s, tlbtype, r0, addrlo); +tcg_out_shifti (s,SHIFT_SHR + tlbrexw, r0, +TARGET_PAGE_BITS -CPU_TLB_ENTRY_BITS ); + +tcg_out_modrm_offset (s, OPC_AND_GvEv + trexw, r0,TCG_AREG0 , + offsetof(CPUArchState, tlb_desc[mem_index].mask)); + +tcg_out_modrm_offset (s, OPC_ADD_GvEv + hrexw, r0,TCG_AREG0 , + offsetof(CPUArchState, tlb_table[mem_index])); +/* If the required alignment is at least as large as the access, simply copy the address and mask. For lesser alignments, check that we don't cross pages for the complete access. */
@@ -1642,20 +1652,10 @@ static inline void tcg_out_tlb_load(TCGContext *s, TCGReg addrlo, TCGReg addrhi,tcg_out_modrm_offset (s,OPC_LEA + trexw, r1, addrlo, s_mask - a_mask); } tlb_mask = (target_ulong )TARGET_PAGE_MASK | a_mask; - -tcg_out_shifti (s,SHIFT_SHR + tlbrexw, r0, -TARGET_PAGE_BITS -CPU_TLB_ENTRY_BITS ); -tgen_arithi (s,ARITH_AND + trexw, r1, tlb_mask,0 ); -tgen_arithi (s,ARITH_AND + tlbrexw, r0, - (CPU_TLB_SIZE -1 ) <<CPU_TLB_ENTRY_BITS ,0 ); - -tcg_out_modrm_sib_offset (s,OPC_LEA + hrexw, r0,TCG_AREG0 , r0,0 , - offsetof(CPUArchState, tlb_table[mem_index][0]) - + which);/* cmp 0(r0), r1 */ -tcg_out_modrm_offset (s, OPC_CMP_GvEv + trexw, r1, r0,0 ); +tcg_out_modrm_offset (s, OPC_CMP_GvEv + trexw, r1, r0, which);/* Prepare for both the fast path add of the tlb addend, and the slow path function argument setup. There are two cases worth note:
@@ -1672,7 +1672,7 @@ static inline void tcg_out_tlb_load(TCGContext *s, TCGReg addrlo, TCGReg addrhi,if (TARGET_LONG_BITS >TCG_TARGET_REG_BITS ) {/* cmp 4(r0), addrhi */ -tcg_out_modrm_offset (s, OPC_CMP_GvEv, addrhi, r0,4 ); +tcg_out_modrm_offset (s, OPC_CMP_GvEv, addrhi, r0, which +4 );/* jne slow_path */ tcg_out_opc (s, OPC_JCC_long +JCC_JNE ,0 ,0 ,0 );
@@ -1684,7 +1684,7 @@ static inline void tcg_out_tlb_load(TCGContext *s, TCGReg addrlo, TCGReg addrhi,/* add addend(r0), r1 */ tcg_out_modrm_offset (s, OPC_ADD_GvEv + hrexw, r1, r0, - offsetof(CPUTLBEntry , addend) - which); + offsetof(CPUTLBEntry , addend)); }/*
Signature · 1 line
2.17.1
Re: [Qemu-devel] [RFC 1/6] (XXX) cputlb: separate MMU allocation + run-time sizing
include/exec/cpu-defs.h typedef struct CPUIOTLBEntry { · line 147
Quoted 5 lines · Emilio G. Cota
include/exec/cpu-defs.h +4
-1-#define CPU_COMMON_TLB \ +typedef struct CPUTLBDesc { +size_t size; +size_t mask;/* (.size - 1) << CPU_TLB_ENTRY_BITS for TLB fast path */ +}CPUTLBDesc ;
I think you don't need both size and mask. Size is (or ought to be) used infrequently enough that I think it can be computed on demand. But on a related note, if you remember the out-of-line tlb changes, it'll be easier for x86 if you index an array of scalars.
Review
Quoted 2 lines
(quoted diff) +1
-1- int index = (addr >> TARGET_PAGE_BITS) & (CPU_TLB_SIZE - 1); + int index = (addr >> TARGET_PAGE_BITS) & (env->tlb_desc[mmu_idx].size - 1);
I just posted a patch to functionalize this. But I imagine
static inline uintptr_t tlb_index(CPUArchState *env, uintptr_t mmu_idx,
target_ulong addr)
{
uintptr_t ofs = (addr >> TARGET_PAGE_BITS) & env->tlb_mask[mmu_idx];
return ofs >> CPU_TLB_BITS;
}static inline CPUTLBEntry *tlb_entry(CPUArchState *env, uintptr_t mmu_idx,
target_ulong addr)
{
uintptr_t ofs = (addr >> TARGET_PAGE_BITS) & env->tlb_mask[mmu_idx];
return (void *)&env->tlb_table[mmu_idx][0] + ofs;
}In the few places where we use both of these functions, the compiler ought to be able to pull out the common sub-expression.
accel/tcg/cputlb.c static void tlb_flush_nocheck(CPUState *cpu) · line 154
Quoted 8 lines
accel/tcg/cputlb.c +3
-1@@ -139,7 +149,10 @@ static void tlb_flush_nocheck(CPUState *cpu)* that do not hold the lock are performed by the same owner thread. */ qemu_spin_lock (&env->tlb_lock); -memset (env->tlb_table,-1 ,sizeof (env->tlb_table)); +for (i =0 ; i <NB_MMU_MODES ; i++) { +memset (env->tlb_table[i],-1 , + env->tlb_desc[i].size *sizeof (CPUTLBEntry));
Here we can use something like
static inline uintptr_t sizeof_tlb(CPUArchState *env, uintptr_t mmu_idx)
{
return env->tlb_mask[mmu_idx] + (1 << CPU_TLB_BITS);
}memset(env->tlb_table[i], -1, sizeof_tlb(env, i));
accel/tcg/cputlb.c void tlb_reset_dirty(CPUState *cpu, ram_addr_t start1, ram_addr_t length) · line 542
Quoted 2 lines
accel/tcg/cputlb.c +1
-1-for (i =0 ; i <CPU_TLB_SIZE ; i++) { +for (i =0 ; i < env->tlb_desc[mmu_idx].size; i++) {
This seems to be one of the few places where you need the number of entries rather than the size. Perhaps
for (i = sizeof_tlb(env, mmu_idx) >> CPU_TLB_BITS; i-- > 0; ) {Or if you can think of a name for the function of the same effect...
r~
RFC 2/6 cputlb: do not evict invalid entries to the vtlb
In reply to Emilio G. CotaCurrently we evict an entry to the victim TLB when it doesn't match the current address. But it could be that there's no match because the current entry is invalid. Do not evict the entry to the vtlb in that case.
This change will help us keep track of the TLB's use rate.
--- include/exec/cpu-all.h | 14 ++++++++++++++ accel/tcg/cputlb.c | 2 +- 2 files changed, 15 insertions(+), 1 deletion(-)
include/exec/cpu-all.h +14 -0
@@ -362,6 +362,20 @@ static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr) return tlb_hit_page(tlb_addr, addr & TARGET_PAGE_MASK); } +/** +* tlb_is_valid - return true if at least one of the addresses is valid +* @te: pointer to CPUTLBEntry +* +* This is useful when we don't have a particular address to compare against, +* and we just want to know whether any entry holds valid data. +*/ +static inline bool tlb_is_valid (const CPUTLBEntry *te) +{ +return !(te->addr_read &TLB_INVALID_MASK ) || + !(te->addr_write &TLB_INVALID_MASK ) || + !(te->addr_code &TLB_INVALID_MASK ); +} +void dump_exec_info (FILE *f,fprintf_function cpu_fprintf);void dump_opcount_info (FILE *f,fprintf_function cpu_fprintf);#endif /* !CONFIG_USER_ONLY */
accel/tcg/cputlb.c +1 -1
@@ -695,7 +695,7 @@ void tlb_set_page_with_attrs(CPUState *cpu, target_ulong vaddr,* Only evict the old entry to the victim tlb if it's for a * different page; otherwise just overwrite the stale data. */ -if (!tlb_hit_page_anyprot (te, vaddr_page)) { +if (!tlb_hit_page_anyprot (te, vaddr_page) &&tlb_is_valid (te)) {unsigned vidx = env->vtlb_index++ %CPU_VTLB_SIZE ;CPUTLBEntry *tv = &env->tlb_v_table[mmu_idx][vidx];
Signature · 1 line
2.17.1
Re: [Qemu-devel] [RFC 2/6] cputlb: do not evict invalid entries to the vtlb
Quoted 24 lines · Emilio G. Cota
Currently we evict an entry to the victim TLB when it doesn't match the current address. But it could be that there's no match because the current entry is invalid. Do not evict the entry to the vtlb in that case.
This change will help us keep track of the TLB's use rate.
Signed-off-by Emilio G. Cota <[email protected]>--- include/exec/cpu-all.h | 14 ++++++++++++++ accel/tcg/cputlb.c | 2 +- 2 files changed, 15 insertions(+), 1 deletion(-)include/exec/cpu-all.h +3
-0@@ -362,6 +362,20 @@ static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr)return tlb_hit_page (tlb_addr, addr &TARGET_PAGE_MASK ); } +/** +* tlb_is_valid - return true if at least one of the addresses is valid +* @te: pointer to CPUTLBEntry
include/exec/cpu-all.h static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr) · line 377
Quoted 10 lines
include/exec/cpu-all.h +10
-0+* +* This is useful when we don't have a particular address to compare against, +* and we just want to know whether any entry holds valid data. +*/ +static inline bool tlb_is_valid (const CPUTLBEntry *te) +{ +return !(te->addr_read &TLB_INVALID_MASK ) || + !(te->addr_write &TLB_INVALID_MASK ) || + !(te->addr_code &TLB_INVALID_MASK ); +}
No, I think you misunderstand.
First, TLB_INVALID_MASK is only ever set for addr_write, in response to PAGE_WRITE_INV. Second, an entry that is invalid for write is still valid for read+exec. So there is benefit to swapping it out to the victim cache.
This is used by the s390x target to make the "lowpage" read-only, which is a special architected 512 byte range within pages 0 and 1. This is done by forcing writes, but not reads, back through tlb_fill.
r~
Re: [Qemu-devel] [RFC 2/6] cputlb: do not evict invalid entries to the vtlb
Quoted 38 lines · Richard Henderson
Quoted 24 lines · Emilio G. Cota
Currently we evict an entry to the victim TLB when it doesn't match the current address. But it could be that there's no match because the current entry is invalid. Do not evict the entry to the vtlb in that case.
This change will help us keep track of the TLB's use rate.
Signed-off-by Emilio G. Cota <[email protected]>--- include/exec/cpu-all.h | 14 ++++++++++++++ accel/tcg/cputlb.c | 2 +- 2 files changed, 15 insertions(+), 1 deletion(-)include/exec/cpu-all.h +3
-0@@ -362,6 +362,20 @@ static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr)return tlb_hit_page (tlb_addr, addr &TARGET_PAGE_MASK ); } +/** +* tlb_is_valid - return true if at least one of the addresses is valid +* @te: pointer to CPUTLBEntry include/exec/cpu-all.h static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr) · line 377
Quoted 10 lines
include/exec/cpu-all.h +10
-0+* +* This is useful when we don't have a particular address to compare against, +* and we just want to know whether any entry holds valid data. +*/ +static inline bool tlb_is_valid (const CPUTLBEntry *te) +{ +return !(te->addr_read &TLB_INVALID_MASK ) || + !(te->addr_write &TLB_INVALID_MASK ) || + !(te->addr_code &TLB_INVALID_MASK ); +}No, I think you misunderstand.
Quoted 7 lines
First,
TLB_INVALID_MASKis only ever set foraddr_write, in response toPAGE_WRITE_INV. Second, an entry that is invalid for write is still valid for read+exec. So there is benefit to swapping it out to the victim cache.This is used by the s390x target to make the "lowpage" read-only, which is a special architected 512 byte range within pages 0 and 1. This is done by forcing writes, but not reads, back through
tlb_fill.
Aah I see. The point is to avoid pushing to the victim cache an entry that is all invalid, not just partially invalid.
Thanks for the clarification!
Emilio
Re: [Qemu-devel] [RFC 2/6] cputlb: do not evict invalid entries to the vtlb
Quoted 43 lines · Emilio G. Cota
Quoted 42 lines · Richard Henderson
Quoted 24 lines · Emilio G. Cota
Currently we evict an entry to the victim TLB when it doesn't match the current address. But it could be that there's no match because the current entry is invalid. Do not evict the entry to the vtlb in that case.
This change will help us keep track of the TLB's use rate.
Signed-off-by Emilio G. Cota <[email protected]>--- include/exec/cpu-all.h | 14 ++++++++++++++ accel/tcg/cputlb.c | 2 +- 2 files changed, 15 insertions(+), 1 deletion(-)include/exec/cpu-all.h +3
-0@@ -362,6 +362,20 @@ static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr)return tlb_hit_page (tlb_addr, addr &TARGET_PAGE_MASK ); } +/** +* tlb_is_valid - return true if at least one of the addresses is valid +* @te: pointer to CPUTLBEntry include/exec/cpu-all.h static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr) · line 377
Quoted 10 lines
include/exec/cpu-all.h +10
-0+* +* This is useful when we don't have a particular address to compare against, +* and we just want to know whether any entry holds valid data. +*/ +static inline bool tlb_is_valid (const CPUTLBEntry *te) +{ +return !(te->addr_read &TLB_INVALID_MASK ) || + !(te->addr_write &TLB_INVALID_MASK ) || + !(te->addr_code &TLB_INVALID_MASK ); +}No, I think you misunderstand.
First,
TLB_INVALID_MASKis only ever set foraddr_write, in response toPAGE_WRITE_INV. Second, an entry that is invalid for write is still valid for read+exec. So there is benefit to swapping it out to the victim cache.
Quoted 6 lines
Quoted 3 lines
This is used by the s390x target to make the "lowpage" read-only, which is a special architected 512 byte range within pages 0 and 1. This is done by forcing writes, but not reads, back through
tlb_fill.Aah I see. The point is to avoid pushing to the victim cache an entry that is all invalid, not just partially invalid.
I've slightly misspoken here. It is (ab)used for the s390 thing, but that bit is also set by memset -1. Perhaps you might check
static inline bool tlb_is_invalid(const CPUTLBEntry *te)
{
return te->addr_read & te->addr_write & te->addr_code & TLB_INVALID_MASK;
}That is, all forms of access have the INVALID bit set.
r~
Re: [Qemu-devel] [RFC 2/6] cputlb: do not evict invalid entries to the vtlb
Quoted 54 lines · Richard Henderson
Quoted 43 lines · Emilio G. Cota
Quoted 42 lines · Richard Henderson
Quoted 24 lines · Emilio G. Cota
Currently we evict an entry to the victim TLB when it doesn't match the current address. But it could be that there's no match because the current entry is invalid. Do not evict the entry to the vtlb in that case.
This change will help us keep track of the TLB's use rate.
Signed-off-by Emilio G. Cota <[email protected]>--- include/exec/cpu-all.h | 14 ++++++++++++++ accel/tcg/cputlb.c | 2 +- 2 files changed, 15 insertions(+), 1 deletion(-)include/exec/cpu-all.h +3
-0@@ -362,6 +362,20 @@ static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr)return tlb_hit_page (tlb_addr, addr &TARGET_PAGE_MASK ); } +/** +* tlb_is_valid - return true if at least one of the addresses is valid +* @te: pointer to CPUTLBEntry include/exec/cpu-all.h static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr) · line 377
Quoted 10 lines
include/exec/cpu-all.h +10
-0+* +* This is useful when we don't have a particular address to compare against, +* and we just want to know whether any entry holds valid data. +*/ +static inline bool tlb_is_valid (const CPUTLBEntry *te) +{ +return !(te->addr_read &TLB_INVALID_MASK ) || + !(te->addr_write &TLB_INVALID_MASK ) || + !(te->addr_code &TLB_INVALID_MASK ); +}No, I think you misunderstand.
First,
TLB_INVALID_MASKis only ever set foraddr_write, in response toPAGE_WRITE_INV. Second, an entry that is invalid for write is still valid for read+exec. So there is benefit to swapping it out to the victim cache.Quoted 6 lines
Quoted 3 lines
This is used by the s390x target to make the "lowpage" read-only, which is a special architected 512 byte range within pages 0 and 1. This is done by forcing writes, but not reads, back through
tlb_fill.Aah I see. The point is to avoid pushing to the victim cache an entry that is all invalid, not just partially invalid.
I've slightly misspoken here. It is (ab)used for the s390 thing, but that bit is also set by memset -1. Perhaps you might check
Quoted 6 lines
static inline bool
tlb_is_invalid(const CPUTLBEntry *te){ return te->addr_read & te->addr_write & te->addr_code & TLB_INVALID_MASK; }That is, all forms of access have the INVALID bit set.
I see. I just ran a few tests and the below gives the best performance, so I'll go with it:
static inline bool tlb_is_empty(const CPUTLBEntry *te)
{
return te->addr_read == -1 && te->addr_write == -1 && te->addr_code == -1;
}I renamed it from "invalid" to "empty" to avoid even thinking about the invalid flag.
Thanks,
Emilio
RFC 3/6 cputlb: track TLB use rates
In reply to Emilio G. CotaThis paves the way for implementing a dynamically-sized softmmu.
--- include/exec/cpu-defs.h | 1 + accel/tcg/cputlb.c | 17 ++++++++++++++--- 2 files changed, 15 insertions(+), 3 deletions(-)
include/exec/cpu-defs.h +1 -0
@@ -144,6 +144,7 @@ typedef struct CPUIOTLBEntry {typedef struct CPUTLBDesc {size_t size;size_t mask;/* (.size - 1) << CPU_TLB_ENTRY_BITS for TLB fast path */ +size_t used; }CPUTLBDesc ;#define CPU_COMMON_TLB \
accel/tcg/cputlb.c +14 -3
@@ -84,6 +84,7 @@ void tlb_init(CPUState *cpu) desc->size =CPU_TLB_SIZE ; desc->mask = (desc->size -1 ) <<CPU_TLB_ENTRY_BITS ; + desc->used =0 ; env->tlb_table[i] =g_new (CPUTLBEntry, desc->size); env->iotlb[i] =g_new0 (CPUIOTLBEntry, desc->size); }
@@ -152,6 +153,7 @@ static void tlb_flush_nocheck(CPUState *cpu)for (i =0 ; i <NB_MMU_MODES ; i++) {memset (env->tlb_table[i],-1 , env->tlb_desc[i].size *sizeof (CPUTLBEntry)); + env->tlb_desc[i].used =0 ; }memset (env->tlb_v_table,-1 ,sizeof (env->tlb_v_table));qemu_spin_unlock (&env->tlb_lock);
@@ -216,6 +218,7 @@ static void tlb_flush_by_mmuidx_async_work(CPUState *cpu, run_on_cpu_data data)memset (env->tlb_table[mmu_idx],-1 , env->tlb_desc[mmu_idx].size *sizeof (CPUTLBEntry));memset (env->tlb_v_table[mmu_idx],-1 ,sizeof (env->tlb_v_table[0 ])); + env->tlb_desc[mmu_idx].used =0 ; } }qemu_spin_unlock (&env->tlb_lock);
@@ -276,12 +279,14 @@ static inline bool tlb_hit_page_anyprot(CPUTLBEntry *tlb_entry, }/* Called with tlb_lock held */ -static inline void tlb_flush_entry_locked (CPUTLBEntry *tlb_entry, +static inline bool tlb_flush_entry_locked (CPUTLBEntry *tlb_entry,target_ulong page) {if (tlb_hit_page_anyprot (tlb_entry, page)) {memset (tlb_entry,-1 ,sizeof (*tlb_entry)); +return true; } +return false; }/* Called with tlb_lock held */
@@ -321,7 +326,9 @@ static void tlb_flush_page_async_work(CPUState *cpu, run_on_cpu_data data)for (mmu_idx =0 ; mmu_idx <NB_MMU_MODES ; mmu_idx++) {int i = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 ); -tlb_flush_entry_locked (&env->tlb_table[mmu_idx][i], addr); +if (tlb_flush_entry_locked (&env->tlb_table[mmu_idx][i], addr)) { + env->tlb_desc[mmu_idx].used--; + }tlb_flush_vtlb_page_locked (env, mmu_idx, addr); }qemu_spin_unlock (&env->tlb_lock);
@@ -365,7 +372,9 @@ static void tlb_flush_page_by_mmuidx_async_work(CPUState *cpu, page = (addr >>TARGET_PAGE_BITS ) & (env->tlb_desc[mmu_idx].size -1 );if (test_bit (mmu_idx, &mmu_idx_bitmap)) { -tlb_flush_entry_locked (&env->tlb_table[mmu_idx][page], addr); +if (tlb_flush_entry_locked (&env->tlb_table[mmu_idx][page], addr)) { + env->tlb_desc[mmu_idx].used--; + }tlb_flush_vtlb_page_locked (env, mmu_idx, addr); } }
@@ -702,6 +711,7 @@ void tlb_set_page_with_attrs(CPUState *cpu, target_ulong vaddr,/* Evict the old entry into the victim tlb. */ copy_tlb_helper_locked (tv, te); env->iotlb_v[mmu_idx][vidx] = env->iotlb[mmu_idx][index]; + env->tlb_desc[mmu_idx].used--; }/* refill the tlb */
@@ -753,6 +763,7 @@ void tlb_set_page_with_attrs(CPUState *cpu, target_ulong vaddr, }copy_tlb_helper_locked (te, &tn); + env->tlb_desc[mmu_idx].used++;qemu_spin_unlock (&env->tlb_lock); }
Signature · 1 line
2.17.1
Re: [Qemu-devel] [RFC 3/6] cputlb: track TLB use rates
accel/tcg/cputlb.c void tlb_set_page_with_attrs(CPUState *cpu, target_ulong vaddr, · line 768
Quoted 7 lines · Emilio G. Cota
accel/tcg/cputlb.c +1
-0@@ -753,6 +763,7 @@ void tlb_set_page_with_attrs(CPUState *cpu, target_ulong vaddr, }copy_tlb_helper_locked (te, &tn); + env->tlb_desc[mmu_idx].used++;qemu_spin_unlock (&env->tlb_lock); }
So.. you're computing what? Total TLB occupancy?
Perhaps a better name than "used"?
Otherwise the patch looks plausible.
r~
RFC 4/6 tcg: define TCG_TARGET_TLB_MAX_INDEX_BITS
In reply to Emilio G. CotaFrom: Pranith Kumar <[email protected]>
This paves the way for implementing a dynamically-sized softmmu.
--- tcg/aarch64/tcg-target.h | 1 + tcg/arm/tcg-target.h | 1 + tcg/i386/tcg-target.h | 2 ++ tcg/mips/tcg-target.h | 2 ++ tcg/ppc/tcg-target.h | 1 + tcg/s390/tcg-target.h | 1 + tcg/sparc/tcg-target.h | 1 + tcg/tci/tcg-target.h | 1 + 8 files changed, 10 insertions(+)
tcg/aarch64/tcg-target.h +1 -0
@@ -15,6 +15,7 @@#define TCG_TARGET_INSN_UNIT_SIZE 4#define TCG_TARGET_TLB_DISPLACEMENT_BITS 24 +#define TCG_TARGET_TLB_MAX_INDEX_BITS 32#undef TCG_TARGET_STACK_GROWSUP typedef enum {
tcg/arm/tcg-target.h +1 -0
@@ -60,6 +60,7 @@ extern int arm_arch;#undef TCG_TARGET_STACK_GROWSUP#define TCG_TARGET_INSN_UNIT_SIZE 4#define TCG_TARGET_TLB_DISPLACEMENT_BITS 16 +#define TCG_TARGET_TLB_MAX_INDEX_BITS 8 typedef enum { TCG_REG_R0 = 0,
tcg/i386/tcg-target.h +2 -0
@@ -200,6 +200,8 @@ extern bool have_avx2;# define TCG_AREG0 TCG_REG_EBP#endif +#define TCG_TARGET_TLB_MAX_INDEX_BITS (32 - CPU_TLB_ENTRY_BITS) +static inline void flush_icache_range (uintptr_t start,uintptr_t stop) { }
tcg/mips/tcg-target.h +2 -0
@@ -39,6 +39,8 @@#define TCG_TARGET_TLB_DISPLACEMENT_BITS 16#define TCG_TARGET_NB_REGS 32 +#define TCG_TARGET_TLB_MAX_INDEX_BITS (16 - CPU_TLB_ENTRY_BITS) + typedef enum { TCG_REG_ZERO = 0, TCG_REG_AT,
tcg/ppc/tcg-target.h +1 -0
@@ -34,6 +34,7 @@#define TCG_TARGET_NB_REGS 32#define TCG_TARGET_INSN_UNIT_SIZE 4#define TCG_TARGET_TLB_DISPLACEMENT_BITS 16 +#define TCG_TARGET_TLB_MAX_INDEX_BITS 32 typedef enum { TCG_REG_R0, TCG_REG_R1, TCG_REG_R2, TCG_REG_R3,
tcg/s390/tcg-target.h +1 -0
@@ -27,6 +27,7 @@#define TCG_TARGET_INSN_UNIT_SIZE 2#define TCG_TARGET_TLB_DISPLACEMENT_BITS 19 +#define TCG_TARGET_TLB_MAX_INDEX_BITS 32 typedef enum TCGReg { TCG_REG_R0 = 0,
tcg/sparc/tcg-target.h +1 -0
@@ -29,6 +29,7 @@#define TCG_TARGET_INSN_UNIT_SIZE 4#define TCG_TARGET_TLB_DISPLACEMENT_BITS 32 +#define TCG_TARGET_TLB_MAX_INDEX_BITS 12#define TCG_TARGET_NB_REGS 32 typedef enum {
tcg/tci/tcg-target.h +1 -0
@@ -43,6 +43,7 @@#define TCG_TARGET_INTERPRETER 1#define TCG_TARGET_INSN_UNIT_SIZE 1#define TCG_TARGET_TLB_DISPLACEMENT_BITS 32 +#define TCG_TARGET_TLB_MAX_INDEX_BITS 32#if UINTPTR_MAX ==UINT32_MAX # define TCG_TARGET_REG_BITS 32
Signature · 1 line
2.17.1
Re: [Qemu-devel] [RFC 4/6] tcg: define TCG_TARGET_TLB_MAX_INDEX_BITS
Quoted 7 lines · Emilio G. Cota
From: Pranith Kumar <[email protected]>
This paves the way for implementing a dynamically-sized softmmu.
Signed-off-by Pranith Kumar <[email protected]>Signed-off-by Emilio G. Cota <[email protected]>---
There's no point in this, since the original constraint was due to encoding immediates in the and instruction. Now we're using tlb_mask.
r~
RFC 5/6 cpu-defs: define MIN_CPU_TLB_SIZE
In reply to Emilio G. Cota--- include/exec/cpu-defs.h | 6 +++--- accel/tcg/cputlb.c | 2 +- tcg/i386/tcg-target.inc.c | 3 ++- 3 files changed, 6 insertions(+), 5 deletions(-)
include/exec/cpu-defs.h +3 -3
@@ -67,7 +67,7 @@ typedef uint64_t target_ulong;#define CPU_TLB_ENTRY_BITS 5#endif -/* TCG_TARGET_TLB_DISPLACEMENT_BITS is used in CPU_TLB_BITS to ensure that +/* TCG_TARGET_TLB_DISPLACEMENT_BITS is used in MIN_CPU_TLB_BITS to ensure that * the TLB is not unnecessarily small, but still small enough for the * TLB lookup instruction sequence used by the TCG target. *
@@ -89,7 +89,7 @@ typedef uint64_t target_ulong;* 0x18 (the offset of the addend field in each TLB entry) plus the offset * of tlb_table inside env (which is non-trivial but not huge). */ -#define CPU_TLB_BITS \ +#define MIN_CPU_TLB_BITS \ MIN(8, \ TCG_TARGET_TLB_DISPLACEMENT_BITS - CPU_TLB_ENTRY_BITS - \ (NB_MMU_MODES <= 1 ? 0 : \
@@ -97,7 +97,7 @@ typedef uint64_t target_ulong; NB_MMU_MODES <= 4 ? 2 : \ NB_MMU_MODES <= 8 ? 3 : 4)) -#define CPU_TLB_SIZE (1 << CPU_TLB_BITS) +#define MIN_CPU_TLB_SIZE (1 << MIN_CPU_TLB_BITS) typedef struct CPUTLBEntry { /* bit TARGET_LONG_BITS to TARGET_PAGE_BITS : virtual address
accel/tcg/cputlb.c +1 -1
@@ -82,7 +82,7 @@ void tlb_init(CPUState *cpu)for (i =0 ; i <NB_MMU_MODES ; i++) {CPUTLBDesc *desc = &env->tlb_desc[i]; - desc->size =CPU_TLB_SIZE ; + desc->size =MIN_CPU_TLB_SIZE ; desc->mask = (desc->size -1 ) <<CPU_TLB_ENTRY_BITS ; desc->used =0 ; env->tlb_table[i] =g_new (CPUTLBEntry, desc->size);
tcg/i386/tcg-target.inc.c +2 -1
@@ -1626,7 +1626,8 @@ static inline void tcg_out_tlb_load(TCGContext *s, TCGReg addrlo, TCGReg addrhi, }if (TCG_TYPE_PTR ==TCG_TYPE_I64 ) { hrexw =P_REXW ; -if (TARGET_PAGE_BITS +CPU_TLB_BITS >32 ) { +/* XXX the size here is variable */ +if (TARGET_PAGE_BITS +MIN_CPU_TLB_BITS >32 ) { tlbtype =TCG_TYPE_I64 ; tlbrexw =P_REXW ; }
Signature · 1 line
2.17.1
Re: [Qemu-devel] [RFC 5/6] cpu-defs: define MIN_CPU_TLB_SIZE
include/exec/cpu-defs.h typedef uint64_t target_ulong; · line 95
Quoted 9 lines · Emilio G. Cota
include/exec/cpu-defs.h +1
-1@@ -89,7 +89,7 @@ typedef uint64_t target_ulong;* 0x18 (the offset of the addend field in each TLB entry) plus the offset * of tlb_table inside env (which is non-trivial but not huge). */ -#define CPU_TLB_BITS \ +#define MIN_CPU_TLB_BITS \ MIN(8, \ TCG_TARGET_TLB_DISPLACEMENT_BITS - CPU_TLB_ENTRY_BITS - \ (NB_MMU_MODES <= 1 ? 0 : \
There's no point in this either, since the original constraint was due to the immediate offset into an add instruction. Now we're loading the base address from an array. The actual size of the tlb is immaterial now, since the size of the tlb does not affect the size of CPUArchState.
r~
RFC 6/6 cputlb: dynamically resize TLBs based on use rate
In reply to Emilio G. CotaPerform the resizing only on flushes, otherwise we'd have to take a perf hit by either rehashing the array or unnecessarily flushing it.
We grow the array aggressively, and reduce the size more slowly. This accommodates mixed workloads, where some processes might be memory-heavy while others are not.
As the following experiments show, this a net perf gain, particularly for memory-heavy workloads. Experiments are run on an Intel i7-6700K CPU @ 4.00GHz.
1. System boot + shudown, debian aarch64:
- Before (tb-lock-v3):
Performance counter stats for 'taskset -c 0 ../img/aarch64/die.sh' (10 runs):
7469.363393 task-clock (msec) # 0.998 CPUs utilized ( +- 0.07% )
31,507,707,190 cycles # 4.218 GHz ( +- 0.07% )
57,101,577,452 instructions # 1.81 insns per cycle ( +- 0.08% )
10,265,531,804 branches # 1374.352 M/sec ( +- 0.07% )
173,020,681 branch-misses # 1.69% of all branches ( +- 0.10% )7.483359063 seconds time elapsed ( +- 0.08% )
- After:
Performance counter stats for 'taskset -c 0 ../img/aarch64/die.sh' (10 runs):
7185.036730 task-clock (msec) # 0.999 CPUs utilized ( +- 0.11% )
30,303,501,143 cycles # 4.218 GHz ( +- 0.11% )
54,198,386,487 instructions # 1.79 insns per cycle ( +- 0.08% )
9,726,518,945 branches # 1353.719 M/sec ( +- 0.08% )
167,082,307 branch-misses # 1.72% of all branches ( +- 0.08% )7.195597842 seconds time elapsed ( +- 0.11% )
That is, a 3.8% improvement.
2. System boot + shutdown, ubuntu 18.04 x86_64:
- Before (tb-lock-v3):
Performance counter stats for 'taskset -c 0 ../img/x86_64/ubuntu-die.sh -nographic' (2 runs):
49971.036482 task-clock (msec) # 0.999 CPUs utilized ( +- 1.62% )
210,766,077,140 cycles # 4.218 GHz ( +- 1.63% )
428,829,830,790 instructions # 2.03 insns per cycle ( +- 0.75% )
77,313,384,038 branches # 1547.164 M/sec ( +- 0.54% )
835,610,706 branch-misses # 1.08% of all branches ( +- 2.97% )50.003855102 seconds time elapsed ( +- 1.61% )
- After:
Performance counter stats for 'taskset -c 0 ../img/x86_64/ubuntu-die.sh -nographic' (2 runs):
50118.124477 task-clock (msec) # 0.999 CPUs utilized ( +- 4.30% )
132,396 context-switches # 0.003 M/sec ( +- 1.20% )
0 cpu-migrations # 0.000 K/sec ( +-100.00% )
167,754 page-faults # 0.003 M/sec ( +- 0.06% )
211,414,701,601 cycles # 4.218 GHz ( +- 4.30% )
<not supported> stalled-cycles-frontend
<not supported> stalled-cycles-backend
431,618,818,597 instructions # 2.04 insns per cycle ( +- 6.40% )
80,197,256,524 branches # 1600.165 M/sec ( +- 8.59% )
794,830,352 branch-misses # 0.99% of all branches ( +- 2.05% )50.177077175 seconds time elapsed ( +- 4.23% )
No improvement (within noise range).
3. x86_64 SPEC06int:
SPEC06int (test set)
[ Y axis: speedup over master ]
8 +-+--+----+----+-----+----+----+----+----+----+----+-----+----+----+--+-+
| |
| tlb-lock-v3 |
7 +-+..................$$$...........................+indirection +-+
| $ $ +resizing |
| $ $ |
6 +-+..................$.$..............................................+-+
| $ $ |
| $ $ |
5 +-+..................$.$..............................................+-+
| $ $ |
| $ $ |
4 +-+..................$.$..............................................+-+
| $ $ |
| +++ $ $ |
3 +-+........$$+.......$.$..............................................+-+
| $$ $ $ |
| $$ $ $ $$$ |
2 +-+........$$........$.$.................................$.$..........+-+
| $$ $ $ $ $ +$$ |
| $$ $$+ $ $ $$$ +$$ $ $ $$$ $$ |
1 +-+***#$***#$+**#$+**#+$**#+$**##$**##$***#$***#$+**#$+**#+$**#+$**##$+-+
| * *#$* *#$ **#$ **# $**# $** #$** #$* *#$* *#$ **#$ **# $**# $** #$ |
| * *#$* *#$ **#$ **# $**# $** #$** #$* *#$* *#$ **#$ **# $**# $** #$ |
0 +-+***#$***#$-**#$-**#$$**#$$**##$**##$***#$***#$-**#$-**#$$**#$$**##$+-+
401.bzi403.gc429445.g456.h462.libq464.h471.omne4483.xalancbgeomeanpng: https://imgur.com/a/b1wn3wc
That is, a 1.53x average speedup over master, with a max speedup of 7.13x.
Note that "indirection" (i.e. the first patch in this series) incurs no overhead, on average.
--- include/exec/cpu-defs.h | 1 + accel/tcg/cputlb.c | 36 ++++++++++++++++++++++++++++++++++++ 2 files changed, 37 insertions(+)
include/exec/cpu-defs.h +1 -0
@@ -145,6 +145,7 @@ typedef struct CPUTLBDesc {size_t size;size_t mask;/* (.size - 1) << CPU_TLB_ENTRY_BITS for TLB fast path */ size_t used; +size_t n_flushes_low_rate; } CPUTLBDesc;#define CPU_COMMON_TLB \
accel/tcg/cputlb.c +36 -0
@@ -85,6 +85,7 @@ void tlb_init(CPUState *cpu) desc->size =MIN_CPU_TLB_SIZE ; desc->mask = (desc->size -1 ) <<CPU_TLB_ENTRY_BITS ; desc->used =0 ; + desc->n_flushes_low_rate =0 ; env->tlb_table[i] =g_new (CPUTLBEntry, desc->size); env->iotlb[i] =g_new0 (CPUIOTLBEntry, desc->size); }
@@ -122,6 +123,39 @@ size_t tlb_flush_count(void)return count; } +/* Call with tlb_lock held */ +static void tlb_mmu_resize_locked (CPUArchState *env,int mmu_idx) +{ +CPUTLBDesc *desc = &env->tlb_desc[mmu_idx]; +size_t rate = desc->used *100 / desc->size; +size_t new_size = desc->size; + +if (rate ==100 ) { + new_size =MIN (desc->size <<2 ,1 <<TCG_TARGET_TLB_MAX_INDEX_BITS ); + }else if (rate >70 ) { + new_size =MIN (desc->size <<1 ,1 <<TCG_TARGET_TLB_MAX_INDEX_BITS ); + }else if (rate <30 ) { + desc->n_flushes_low_rate++; +if (desc->n_flushes_low_rate ==100 ) { + new_size =MAX (desc->size >>1 ,1 <<MIN_CPU_TLB_BITS ); + desc->n_flushes_low_rate =0 ; + } + } + +if (new_size == desc->size) { +return ; + } + +g_free (env->tlb_table[mmu_idx]); +g_free (env->iotlb[mmu_idx]); + + desc->size = new_size; + desc->mask = (desc->size -1 ) <<CPU_TLB_ENTRY_BITS ; + desc->n_flushes_low_rate =0 ; + env->tlb_table[mmu_idx] =g_new (CPUTLBEntry, desc->size); + env->iotlb[mmu_idx] =g_new0 (CPUIOTLBEntry, desc->size); +} +/* This is OK because CPU architectures generally permit an * implementation to drop entries from the TLB at any time, so * flushing more entries than required is only an efficiency issue,
@@ -151,6 +185,7 @@ static void tlb_flush_nocheck(CPUState *cpu)*/ qemu_spin_lock (&env->tlb_lock);for (i =0 ; i <NB_MMU_MODES ; i++) { +tlb_mmu_resize_locked (env, i);memset (env->tlb_table[i],-1 , env->tlb_desc[i].size *sizeof (CPUTLBEntry)); env->tlb_desc[i].used =0 ;
@@ -215,6 +250,7 @@ static void tlb_flush_by_mmuidx_async_work(CPUState *cpu, run_on_cpu_data data)if (test_bit (mmu_idx, &mmu_idx_bitmask)) {tlb_debug ("%d\n" , mmu_idx); +tlb_mmu_resize_locked (env, mmu_idx);memset (env->tlb_table[mmu_idx],-1 , env->tlb_desc[mmu_idx].size *sizeof (CPUTLBEntry));memset (env->tlb_v_table[mmu_idx],-1 ,sizeof (env->tlb_v_table[0 ]));
Signature · 1 line
2.17.1
Re: [Qemu-devel] [RFC 6/6] cputlb: dynamically resize TLBs based on use rate
Hi Emilio,
Quoted 34 lines · Emilio G. Cota
Perform the resizing only on flushes, otherwise we'd have to take a perf hit by either rehashing the array or unnecessarily flushing it.
We grow the array aggressively, and reduce the size more slowly. This accommodates mixed workloads, where some processes might be memory-heavy while others are not.
As the following experiments show, this a net perf gain, particularly for memory-heavy workloads. Experiments are run on an Intel i7-6700K CPU @ 4.00GHz.
1. System boot + shudown, debian aarch64:
- Before (tb-lock-v3):
Performance counter stats for 'taskset -c 0../img/aarch64/die.sh' (10 runs):7469.363393 task-clock (msec) # 0.998 CPUs utilized ( +- 0.07% ) 31,507,707,190 cycles # 4.218 GHz ( +- 0.07% ) 57,101,577,452 instructions # 1.81 insns per cycle ( +- 0.08% ) 10,265,531,804 branches # 1374.352 M/sec ( +- 0.07% ) 173,020,681 branch-misses # 1.69% of all branches ( +- 0.10% )7.483359063 seconds time elapsed ( +- 0.08% )
- After:
Performance counter stats for 'taskset -c 0../img/aarch64/die.sh' (10 runs):7185.036730 task-clock (msec) # 0.999 CPUs utilized ( +- 0.11% ) 30,303,501,143 cycles # 4.218 GHz ( +- 0.11% ) 54,198,386,487 instructions # 1.79 insns per cycle ( +- 0.08% ) 9,726,518,945 branches # 1353.719 M/sec ( +- 0.08% ) 167,082,307 branch-misses # 1.72% of all branches ( +- 0.08% )
Quoted 5 lines
7.195597842 seconds time elapsed ( +- 0.11% )
That is, a 3.8% improvement.
2. System boot + shutdown, ubuntu 18.04
x86_64:
You can also run the VM tests to build QEMU:
$ make vm-test vm-test: Test QEMU in preconfigured virtual machines
vm-build-ubuntu.i386 - Build QEMU in ubuntu i386 VM vm-build-freebsd - Build QEMU in FreeBSD VM vm-build-netbsd - Build QEMU in NetBSD VM vm-build-openbsd - Build QEMU in OpenBSD VM vm-build-centos - Build QEMU in CentOS VM, with Docker
Quoted 51 lines
- Before (tb-lock-v3):
Performance counter stats for 'taskset -c 0../img/x86_64/ubuntu-die.sh-nographic' (2 runs):49971.036482 task-clock (msec) # 0.999 CPUs utilized ( +- 1.62% ) 210,766,077,140 cycles # 4.218 GHz ( +- 1.63% ) 428,829,830,790 instructions # 2.03 insns per cycle ( +- 0.75% ) 77,313,384,038 branches # 1547.164 M/sec ( +- 0.54% ) 835,610,706 branch-misses # 1.08% of all branches ( +- 2.97% )50.003855102 seconds time elapsed ( +- 1.61% )
- After:
Performance counter stats for 'taskset -c 0../img/x86_64/ubuntu-die.sh-nographic' (2 runs):50118.124477 task-clock (msec) # 0.999 CPUs utilized ( +- 4.30% ) 132,396 context-switches # 0.003 M/sec ( +- 1.20% ) 0 cpu-migrations # 0.000 K/sec ( +-100.00% ) 167,754 page-faults # 0.003 M/sec ( +- 0.06% ) 211,414,701,601 cycles # 4.218 GHz ( +- 4.30% ) <not supported> stalled-cycles-frontend <not supported> stalled-cycles-backend 431,618,818,597 instructions # 2.04 insns per cycle ( +- 6.40% ) 80,197,256,524 branches # 1600.165 M/sec ( +- 8.59% ) 794,830,352 branch-misses # 0.99% of all branches ( +- 2.05% )50.177077175 seconds time elapsed ( +- 4.23% )
No improvement (within noise range).
3.
x86_64SPEC06int:
SPEC06int (test set)
[ Y axis: speedup over master ]
8 +-+--+----+----+-----+----+----+----+----+----+----+-----+----+----+--+-+| | | tlb-lock-v3 | 7 +-+..................$$$...........................+indirection +-+ | $ $ +resizing | | $ $ | 6 +-+..................$.$..............................................+-+ | $ $ | | $ $ | 5 +-+..................$.$..............................................+-+ | $ $ | | $ $ | 4 +-+..................$.$..............................................+-+ | $ $ | | +++ $ $ | 3 +-+........$$+.......$.$..............................................+-+ | $$ $ $ | | $$ $ $ $$$ |
Quoted 8 lines
2 +-+........$$........$.$.................................$.$..........+-+
| $$ $ $ $ $ +$$ | | $$ $$+ $ $ $$$ +$$ $ $ $$$ $$ | 1 +-+***#$***#$+**#$+**#+$**#+$**##$**##$***#$***#$+**#$+**#+$**#+$**##$+-+ | * *#$* *#$ **#$ **# $**# $** #$** #$* *#$* *#$ **#$ **# $**# $** #$ | | * *#$* *#$ **#$ **# $**# $** #$** #$* *#$* *#$ **#$ **# $**# $** #$ | 0 +-+***#$***#$-**#$-**#$$**#$$**##$**##$***#$***#$-**#$-**#$$**#$$**##$+-+ 401.bzi403.gc429445.g456.h462.libq464.h471.omne4483.xalancbgeomean
This description line is hard to read ;)
Quoted 43 lines
png: https://imgur.com/a/b1wn3wc
That is, a 1.53x average speedup over master, with a max speedup of 7.13x.
Note that "indirection" (i.e. the first patch in this series) incurs no overhead, on average.
Signed-off-by Emilio G. Cota <[email protected]>--- include/exec/cpu-defs.h | 1 + accel/tcg/cputlb.c | 36 ++++++++++++++++++++++++++++++++++++ 2 files changed, 37 insertions(+)include/exec/cpu-defs.h +1
-0@@ -145,6 +145,7 @@ typedef struct CPUTLBDesc {size_t size;size_t mask;/* (.size - 1) << CPU_TLB_ENTRY_BITS for TLB fast path */ size_t used; +size_t n_flushes_low_rate; } CPUTLBDesc;#define CPU_COMMON_TLB \accel/tcg/cputlb.c +3
-0@@ -85,6 +85,7 @@ void tlb_init(CPUState *cpu) desc->size =MIN_CPU_TLB_SIZE ; desc->mask = (desc->size -1 ) <<CPU_TLB_ENTRY_BITS ; desc->used =0 ; + desc->n_flushes_low_rate =0 ; env->tlb_table[i] =g_new (CPUTLBEntry, desc->size); env->iotlb[i] =g_new0 (CPUIOTLBEntry, desc->size); }@@ -122,6 +123,39 @@ size_t tlb_flush_count(void)return count; } +/* Call with tlb_lock held */ +static void tlb_mmu_resize_locked (CPUArchState *env,int mmu_idx)
accel/tcg/cputlb.c size_t tlb_flush_count(void) · line 137
Quoted 10 lines
accel/tcg/cputlb.c +10
-0+{ +CPUTLBDesc *desc = &env->tlb_desc[mmu_idx]; +size_t rate = desc->used *100 / desc->size; +size_t new_size = desc->size; + +if (rate ==100 ) { + new_size =MIN (desc->size <<2 ,1 <<TCG_TARGET_TLB_MAX_INDEX_BITS ); + }else if (rate >70 ) { + new_size =MIN (desc->size <<1 ,1 <<TCG_TARGET_TLB_MAX_INDEX_BITS ); + }else if (rate <30 ) {
I wonder if those thresholds might be per TCG_TARGET.
Btw the paper used 40% here, did you tried it too?
Regards,
Phil.
Quoted 41 lines
accel/tcg/cputlb.c +23
-0+ desc->n_flushes_low_rate++; +if (desc->n_flushes_low_rate ==100 ) { + new_size =MAX (desc->size >>1 ,1 <<MIN_CPU_TLB_BITS ); + desc->n_flushes_low_rate =0 ; + } + } + +if (new_size == desc->size) { +return ; + } + +g_free (env->tlb_table[mmu_idx]); +g_free (env->iotlb[mmu_idx]); + + desc->size = new_size; + desc->mask = (desc->size -1 ) <<CPU_TLB_ENTRY_BITS ; + desc->n_flushes_low_rate =0 ; + env->tlb_table[mmu_idx] =g_new (CPUTLBEntry, desc->size); + env->iotlb[mmu_idx] =g_new0 (CPUIOTLBEntry, desc->size); +} +/* This is OK because CPU architectures generally permit an * implementation to drop entries from the TLB at any time, so * flushing more entries than required is only an efficiency issue, @@ -151,6 +185,7 @@ static void tlb_flush_nocheck(CPUState *cpu)*/ qemu_spin_lock (&env->tlb_lock);for (i =0 ; i <NB_MMU_MODES ; i++) { +tlb_mmu_resize_locked (env, i);memset (env->tlb_table[i],-1 , env->tlb_desc[i].size *sizeof (CPUTLBEntry)); env->tlb_desc[i].used =0 ;@@ -215,6 +250,7 @@ static void tlb_flush_by_mmuidx_async_work(CPUState *cpu, run_on_cpu_data data)if (test_bit (mmu_idx, &mmu_idx_bitmask)) {tlb_debug ("%d\n" , mmu_idx); +tlb_mmu_resize_locked (env, mmu_idx);memset (env->tlb_table[mmu_idx],-1 , env->tlb_desc[mmu_idx].size *sizeof (CPUTLBEntry));memset (env->tlb_v_table[mmu_idx],-1 ,sizeof (env->tlb_v_table[0 ]));
Re: [Qemu-devel] [RFC 6/6] cputlb: dynamically resize TLBs based on use rate
Quoted 6 lines · Philippe Mathieu-Daudé
Quoted 1 line · Emilio G. Cota
2. System boot + shutdown, ubuntu 18.04
x86_64:You can also run the VM tests to build QEMU:
$ make vm-test
Thanks, will give that a look.
Quoted 7 lines
accel/tcg/cputlb.c size_t tlb_flush_count(void) · line 137
Quoted 5 lines
accel/tcg/cputlb.c +5
-0+if (rate ==100 ) { + new_size =MIN (desc->size <<2 ,1 <<TCG_TARGET_TLB_MAX_INDEX_BITS ); + }else if (rate >70 ) { + new_size =MIN (desc->size <<1 ,1 <<TCG_TARGET_TLB_MAX_INDEX_BITS ); + }else if (rate <30 ) {I wonder if those thresholds might be per
TCG_TARGET.
Do you mean to tune the growth rate based on each TCG target? (max and min are already determined by the TCG target). The optimal growth rate is mostly dependent on the guest workload, so I wouldn't expect the TCG target to matter much.
That said, we could spend quite some time tweaking the TLB sizing algorithm. But with this RFC I wanted to see
(a) whether this approach is a good idea at all, and (b) show what 'easy' speedups might look like (because converting all TCG targets is a pain, so it better be justified).
Quoted 1 line
Btw the paper used 40% here, did you tried it too?
Yes, I tried several alternatives including what the paper describes, i.e. (skipping the min/max checks for simplicity):
if (rate > 70) {
new_size = 2 * old_size;
} else if (rate < 40) {
new_size = old_size / 2;
}But that didn't give great speedups (see "resizing-paper" set):
https://imgur.com/a/w3AqHP7
A few points stand out to me:
- We get very different speedups even if we implement the algorithm they describe (not sure that's exactly what they implemented though). But there are many variables that could explain that, e.g. different guest images (and therefore different TLB flush rates) and different QEMU baselines (ours is faster than the paper's, so getting speedups is harder).
- 70/40% use rate for growing/shrinking the TLB does not seem a great choice, if one wants to avoid a pathological case that can induce constant resizing. Imagine we got exactly 70% use rate, and all TLB misses were compulsory (i.e. a direct-mapped TLB would have not prevented a single miss). We'd then double the TLB size:
size_new = 2*size_old
But then the use rate will halve:
use_new = 0.7/2 = 0.35
So we'd then end up in a grow-shrink loop! Picking a "shrink threshold" below 0.70/2=0.35 avoids this.
- Aggressively increasing the TLB size when usage is high makes sense. However, reducing the size at the same rate does not make much sense. Imagine the following scenario with two processes being scheduled: one process uses a lot of memory, and the other one uses little, but both are CPU-intensive and therefore being assigned similar time slices by the scheduler. Ideally you'd resize the TLB to meet each process' memory demands. However, at flush time we don't even know what process is running or about to run, so we have to size the TLB exclusively based on recent use rates. In this scenario you're probably close to optimal if you size the TLB to meet the demands of the most memory-hungry process. You'll lose some extra time flushing the (now larger) TLB, but your net gain is likely to be positive given the TLB fills you won't have to do when the memory-heavy process is scheduled in.
So to me it's quite likely that in the paper they could have gotten even better results by reducing the shrink rate, like we did.
Thanks,
Emilio
Re: [Qemu-devel] [RFC 6/6] cputlb: dynamically resize TLBs based on use rate
Quoted 5 lines · Emilio G. Cota
- 70/40% use rate for growing/shrinking the TLB does not seem a great choice, if one wants to avoid a pathological case that can induce constant resizing. Imagine we got exactly 70% use rate, and all TLB misses were compulsory (i.e. a direct-mapped TLB would have not prevented a
^^^
Quoted 1 line
single miss). We'd then double the TLB size:
I meant fully associative.
E.
Re: [Qemu-devel] [RFC 6/6] cputlb: dynamically resize TLBs based on use rate
In reply to Emilio G. CotaQuoted 14 lines · Emilio G. Cota
accel/tcg/cputlb.c +10
-0@@ -122,6 +123,39 @@ size_t tlb_flush_count(void)return count; } +/* Call with tlb_lock held */ +static void tlb_mmu_resize_locked (CPUArchState *env,int mmu_idx) +{ +CPUTLBDesc *desc = &env->tlb_desc[mmu_idx]; +size_t rate = desc->used *100 / desc->size; +size_t new_size = desc->size; + +if (rate ==100 ) { + new_size =MIN (desc->size <<2 ,1 <<TCG_TARGET_TLB_MAX_INDEX_BITS ); + }else if (rate >70 ) {
accel/tcg/cputlb.c size_t tlb_flush_count(void) · line 145
Quoted 10 lines
accel/tcg/cputlb.c +10
-0+ new_size =MIN (desc->size <<1 ,1 <<TCG_TARGET_TLB_MAX_INDEX_BITS ); + }else if (rate <30 ) { + desc->n_flushes_low_rate++; +if (desc->n_flushes_low_rate ==100 ) { + new_size =MAX (desc->size >>1 ,1 <<MIN_CPU_TLB_BITS ); + desc->n_flushes_low_rate =0 ; + } + } + +if (new_size == desc->size) {
s/desc->size/old_size/g
Otherwise it looks plausible as a first cut.
r~