Dynamic TLB sizing
v4 cover Dynamic TLB sizing
RFC v3: https://lists.gnu.org/archive/html/qemu-devel/2018-10/msg01753.html
Changes since RFC v3:
- This is now a proper patch series, since it should not (knowingly) break anything.
- Rebase on top of rth's tcg-next (ffd8994b90f5), which includes patch 1 from RFC v3.
- Make the feature optional, so that we don't need to change all TCG backends right now. For this, define TCG_TARGET_IMPLEMENTS_DYN_TLB, which follows a similar approach to what we do with TCG instructions with TCG_TARGET_HAS_foo.
- Merge most changes into a single patch to ease review.
Alex: as a result I dropped two of your R-b's, but note that the only change is the addition of inline helpers to hide whether the TCG backend implements the feature.
The series is checkpatch-clean. You can fetch it from:
https://github.com/cota/qemu/tree/tlb-dyn-v4
Thanks,
Emilio
PATCH v4 1/3 cputlb: do not evict empty entries to the vtlb
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 empty (i.e. all -1's, for instance via tlb_flush). Do not evict the entry to the vtlb in that case.
This change will help us keep track of the TLB's use rate, which we'll use to implement a policy for dynamic TLB sizing.
--- include/exec/cpu-all.h | 9 +++++++++ accel/tcg/cputlb.c | 2 +- 2 files changed, 10 insertions(+), 1 deletion(-)
include/exec/cpu-all.h +9 -0
@@ -362,6 +362,15 @@ static inline bool tlb_hit(target_ulong tlb_addr, target_ulong addr) return tlb_hit_page(tlb_addr, addr & TARGET_PAGE_MASK); } +/** +* tlb_entry_is_empty - return true if the entry is not in use +* @te: pointer to CPUTLBEntry +*/ +static inline bool tlb_entry_is_empty (const CPUTLBEntry *te) +{ +return te->addr_read ==-1 && te->addr_write ==-1 && te->addr_code ==-1 ; +} +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
@@ -678,7 +678,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_entry_is_empty (te)) {unsigned vidx = env->vtlb_index++ %CPU_VTLB_SIZE ;CPUTLBEntry *tv = &env->tlb_v_table[mmu_idx][vidx];
Signature · 1 line
2.17.1
PATCH v4 2/3 tcg: introduce dynamic TLB sizing
In reply to Emilio G. CotaDisable for all TCG backends for now.
--- include/exec/cpu-defs.h | 43 +++++++++++- include/exec/cpu_ldst.h | 21 ++++++ tcg/aarch64/tcg-target.h | 1 + tcg/arm/tcg-target.h | 1 + tcg/i386/tcg-target.h | 1 + tcg/mips/tcg-target.h | 1 + tcg/ppc/tcg-target.h | 1 + tcg/s390/tcg-target.h | 1 + tcg/sparc/tcg-target.h | 1 + tcg/tci/tcg-target.h | 1 + accel/tcg/cputlb.c | 138 +++++++++++++++++++++++++++++++++++++-- 11 files changed, 201 insertions(+), 9 deletions(-)
include/exec/cpu-defs.h +40 -3
@@ -67,6 +67,19 @@ typedef uint64_t target_ulong;#define CPU_TLB_ENTRY_BITS 5#endif +#if TCG_TARGET_IMPLEMENTS_DYN_TLB +#define CPU_TLB_DYN_MIN_BITS 6 +#define CPU_TLB_DYN_DEFAULT_BITS 8 +/* +* Assuming TARGET_PAGE_BITS==12, with 2**22 entries we can cover 2**(22+12) == +* 2**34 == 16G of address space. This is roughly what one would expect a +* TLB to cover in a modern (as of 2018) x86_64 CPU. For instance, Intel +* Skylake's Level-2 STLB has 16 1G entries. +*/ +#define CPU_TLB_DYN_MAX_BITS 22 + +#else /* !TCG_TARGET_IMPLEMENTS_DYN_TLB */ +/* TCG_TARGET_TLB_DISPLACEMENT_BITS is used in 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.
@@ -98,6 +111,7 @@ typedef uint64_t target_ulong; NB_MMU_MODES <= 8 ? 3 : 4))#define CPU_TLB_SIZE (1 << CPU_TLB_BITS) +#endif /* TCG_TARGET_IMPLEMENTS_DYN_TLB */ typedef struct CPUTLBEntry { /* bit TARGET_LONG_BITS to TARGET_PAGE_BITS : virtual address
@@ -141,13 +155,36 @@ typedef struct CPUIOTLBEntry {MemTxAttrs attrs; } CPUIOTLBEntry; -#define CPU_COMMON_TLB \ +#if TCG_TARGET_IMPLEMENTS_DYN_TLB + +typedef struct CPUTLBDesc { +size_t n_used_entries; +size_t n_flushes_low_rate; +}CPUTLBDesc ; + +#define CPU_TLB \ + CPUTLBDesc tlb_desc[NB_MMU_MODES]; \ +/* tlb_mask[i] contains (n_entries - 1) << CPU_TLB_ENTRY_BITS */ \ +uintptr_t tlb_mask[NB_MMU_MODES ]; \ +CPUTLBEntry *tlb_table[NB_MMU_MODES ]; + +#define CPU_IOTLB \ + CPUIOTLBEntry *iotlb[NB_MMU_MODES]; +#else +#define CPU_TLB \ + CPUTLBEntry tlb_table[NB_MMU_MODES][CPU_TLB_SIZE]; + +#define CPU_IOTLB \ + CPUIOTLBEntry iotlb[NB_MMU_MODES][CPU_TLB_SIZE]; +#endif /* TCG_TARGET_IMPLEMENTS_DYN_TLB */ + +#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 */ \ QemuSpin tlb_lock; \ - CPUTLBEntry tlb_table[NB_MMU_MODES][CPU_TLB_SIZE]; \ + CPU_TLB \ CPUTLBEntry tlb_v_table[NB_MMU_MODES][CPU_VTLB_SIZE]; \ - CPUIOTLBEntry iotlb[NB_MMU_MODES][CPU_TLB_SIZE]; \ + CPU_IOTLB \ CPUIOTLBEntry iotlb_v[NB_MMU_MODES][CPU_VTLB_SIZE]; \ size_t tlb_flush_count; \ target_ulong tlb_flush_addr; \
include/exec/cpu_ldst.h +21 -0
@@ -126,6 +126,21 @@ extern __thread uintptr_t helper_retaddr;/* The memory helpers for tcg-generated code need tcg_target_long etc. */ #include "tcg.h" +#if TCG_TARGET_IMPLEMENTS_DYN_TLB +/* Find the TLB index corresponding to the mmu_idx + address pair. */ +static inline uintptr_t tlb_index (CPUArchState *env,uintptr_t mmu_idx, +target_ulong addr) +{ +uintptr_t size_mask = env->tlb_mask[mmu_idx] >>CPU_TLB_ENTRY_BITS ; + +return (addr >>TARGET_PAGE_BITS ) & size_mask; +} + +static inline size_t tlb_n_entries (CPUArchState *env,uintptr_t mmu_idx) +{ +return (env->tlb_mask[mmu_idx] >>CPU_TLB_ENTRY_BITS ) +1 ; +} +#else /* Find the TLB index corresponding to the mmu_idx + address pair. */ static inline uintptr_t tlb_index (CPUArchState *env,uintptr_t mmu_idx,target_ulong addr)
@@ -133,6 +148,12 @@ static inline uintptr_t tlb_index(CPUArchState *env, uintptr_t mmu_idx, return (addr >> TARGET_PAGE_BITS) & (CPU_TLB_SIZE - 1); } +static inline size_t tlb_n_entries (CPUArchState *env,uintptr_t mmu_idx) +{ +return CPU_TLB_SIZE ; +} +#endif /* TCG_TARGET_IMPLEMENTS_DYN_TLB */ +/* Find the TLB entry corresponding to the mmu_idx + address pair. */ static inline CPUTLBEntry *tlb_entry (CPUArchState *env,uintptr_t mmu_idx,target_ulong addr)
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_IMPLEMENTS_DYN_TLB 0#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_IMPLEMENTS_DYN_TLB 0 typedef enum { TCG_REG_R0 = 0,
tcg/i386/tcg-target.h +1 -0
@@ -27,6 +27,7 @@#define TCG_TARGET_INSN_UNIT_SIZE 1#define TCG_TARGET_TLB_DISPLACEMENT_BITS 31 +#define TCG_TARGET_IMPLEMENTS_DYN_TLB 0#ifdef __x86_64__# define TCG_TARGET_REG_BITS 64
tcg/mips/tcg-target.h +1 -0
@@ -37,6 +37,7 @@#define TCG_TARGET_INSN_UNIT_SIZE 4#define TCG_TARGET_TLB_DISPLACEMENT_BITS 16 +#define TCG_TARGET_IMPLEMENTS_DYN_TLB 0#define TCG_TARGET_NB_REGS 32 typedef enum {
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_IMPLEMENTS_DYN_TLB 0 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_IMPLEMENTS_DYN_TLB 0 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_IMPLEMENTS_DYN_TLB 0#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_IMPLEMENTS_DYN_TLB 0#if UINTPTR_MAX ==UINT32_MAX # define TCG_TARGET_REG_BITS 32
accel/tcg/cputlb.c +132 -6
203 lines not on this page · raw message
Signature · 1 line
2.17.1
PATCH v4 3/3 tcg/i386: enable dynamic TLB sizing
In reply to Emilio G. CotaAs 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 "cputlb: introduce indirection for TLB size" patch in this series) incurs no overhead, on average.
To conclude, here is a different look at the SPEC06int results, using linux-user as the baseline and comparing master and this series ("tlb-dyn"):
Softmmu slowdown vs. linux-user for SPEC06int (test set)
[ Y axis: slowdown over linux-user ]
14 +-+--+----+----+----+----+----+-----+----+----+----+----+----+----+--+-+
| |
| master |
12 +-+...............+**..................................tlb-dyn.......+-+
| ** |
| ** |
| ** |
10 +-+................**................................................+-+
| ** |
| ** |
8 +-+................**................................................+-+
| ** |
| ** |
| ** |
6 +-+................**................................................+-+
| *** ** |
| * * ** |
4 +-+.....*.*........**.................................***............+-+
| * * ** * * |
| * * +++ ** *** *** * * *** *** |
| * * +**++ ** **## *+*# *** * *#+* * * *##* * |
2 +-+.....*.*##.**##.**##.**.#.**##.*+*#.***#.*+*#.*.*#.*.*#+*.*.#*.*##+-+
|++***##*+*+#+**+#+**+#+**+#+**+#+*+*#+*+*#+*+*#+*+*#+*+*#+*+*+#*+*+#++|
| * * #* * # ** # ** # ** # ** # * *# * *# * *# * *# * *# * * #* * # |
0 +-+***##***##-**##-**##-**##-**##-***#-***#-***#-***#-***#-***##***##+-+
401.bzi403.g429445.g456.hm462.libq464.h471.omn4483.xalancbgeomeanpng: https://imgur.com/a/eXkjMCE
After this series, we bring down the average softmmu overhead from 2.77x to 1.80x, with a maximum slowdown of 2.48x (omnetpp).
--- tcg/i386/tcg-target.h | 2 +- tcg/i386/tcg-target.inc.c | 28 ++++++++++++++-------------- 2 files changed, 15 insertions(+), 15 deletions(-)
tcg/i386/tcg-target.h +1 -1
@@ -27,7 +27,7 @@#define TCG_TARGET_INSN_UNIT_SIZE 1#define TCG_TARGET_TLB_DISPLACEMENT_BITS 31 -#define TCG_TARGET_IMPLEMENTS_DYN_TLB 0 +#define TCG_TARGET_IMPLEMENTS_DYN_TLB 1#ifdef __x86_64__# define TCG_TARGET_REG_BITS 64
tcg/i386/tcg-target.inc.c +14 -14
@@ -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)
@@ -1625,7 +1626,7 @@ 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 ) { +if (TARGET_PAGE_BITS +CPU_TLB_DYN_MAX_BITS >32 ) { tlbtype =TCG_TYPE_I64 ; tlbrexw =P_REXW ; }
@@ -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_mask[mem_index])); + +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