Emilio G. Cota <c...@braap.org> writes: > Having a fixed-size hash table for keeping track of all translation blocks > is suboptimal: some workloads are just too big or too small to get maximum > performance from the hash table. The MRU promotion policy helps improve > performance when the hash table is a little undersized, but it cannot > make up for severely undersized hash tables. > > Furthermore, frequent MRU promotions result in writes that are a scalability > bottleneck. For scalability, lookups should only perform reads, not writes. > This is not a big deal for now, but it will become one once MTTCG matures. > > The appended fixes these issues by using qht as the implementation of > the TB hash table. This solution is superior to other alternatives considered, > namely: > > - master: implementation in QEMU before this patchset > - xxhash: before this patch, i.e. fixed buckets + xxhash hashing + MRU. > - xxhash-rcu: fixed buckets + xxhash + RCU list + MRU. > MRU is implemented here by adding an intermediate struct > that contains the u32 hash and a pointer to the TB; this > allows us, on an MRU promotion, to copy said struct (that is not > at the head), and put this new copy at the head. After a grace > period, the original non-head struct can be eliminated, and > after another grace period, freed. > - qht-fixed-nomru: fixed buckets + xxhash + qht without auto-resize + > no MRU for lookups; MRU for inserts. > The appended solution is the following: > - qht-dyn-nomru: dynamic number of buckets + xxhash + qht w/ auto-resize + > no MRU for lookups; MRU for inserts. > > The plots below compare the considered solutions. The Y axis shows the > boot time (in seconds) of a debian jessie image with arm-softmmu; the X axis > sweeps the number of buckets (or initial number of buckets for > qht-autoresize). > The plots in PNG format (and with errorbars) can be seen here: > http://imgur.com/a/Awgnq > > Each test runs 5 times, and the entire QEMU process is pinned to a > single core for repeatability of results. > > Host: Intel Xeon E5-2690 > > 28 ++------------+-------------+-------------+-------------+------------++ > A***** + + + master **A*** + > 27 ++ * xxhash ##B###++ > | A******A****** xxhash-rcu $$C$$$ | > 26 C$$ A******A****** qht-fixed-nomru*%%D%%%++ > D%%$$ A******A******A*qht-dyn-mru A*E****A > 25 ++ %%$$ qht-dyn-nomru &&F&&&++ > B#####% | > 24 ++ #C$$$$$ ++ > | B### $ | > | ## C$$$$$$ | > 23 ++ # C$$$$$$ ++ > | B###### C$$$$$$ %%%D > 22 ++ %B###### C$$$$$$C$$$$$$C$$$$$$C$$$$$$C$$$$$$C > | D%%%%%%B###### @E@@@@@@ %%%D%%%@@@E@@@@@@E > 21 E@@@@@@E@@@@@@F&&&@@@E@@@&&&D%%%%%%B######B######B######B######B######B > + E@@@ F&&& + E@ + F&&& + + > 20 ++------------+-------------+-------------+-------------+------------++ > 14 16 18 20 22 24 > log2 number of buckets > > Host: Intel i7-4790K > > 14.5 ++------------+------------+-------------+------------+------------++ > A** + + + master **A*** + > 14 ++ ** xxhash ##B###++ > 13.5 ++ ** xxhash-rcu $$C$$$++ > | qht-fixed-nomru %%D%%% | > 13 ++ A****** qht-dyn-mru @@E@@@++ > | A*****A******A****** qht-dyn-nomru &&F&&& | > 12.5 C$$ A******A******A*****A****** ***A > 12 ++ $$ A*** ++ > D%%% $$ | > 11.5 ++ %% ++ > B### %C$$$$$$ | > 11 ++ ## D%%%%% C$$$$$ ++ > | # % C$$$$$$ | > 10.5 F&&&&&&B######D%%%%% C$$$$$$C$$$$$$C$$$$$$C$$$$$C$$$$$$ $$$C > 10 E@@@@@@E@@@@@@B#####B######B######E@@@@@@E@@@%%%D%%%%%D%%%###B######B > + F&& D%%%%%%B######B######B#####B###@@@D%%% + > 9.5 ++------------+------------+-------------+------------+------------++ > 14 16 18 20 22 24 > log2 number of buckets > > Note that the original point before this patch series is X=15 for "master"; > the little sensitivity to the increased number of buckets is due to the > poor hashing function in master. > > xxhash-rcu has significant overhead due to the constant churn of allocating > and deallocating intermediate structs for implementing MRU. An alternative > would be do consider failed lookups as "maybe not there", and then > acquire the external lock (tb_lock in this case) to really confirm that > there was indeed a failed lookup. This, however, would not be enough > to implement dynamic resizing--this is more complex: see > "Resizable, Scalable, Concurrent Hash Tables via Relativistic > Programming" by Triplett, McKenney and Walpole. This solution was > discarded due to the very coarse RCU read critical sections that we have > in MTTCG; resizing requires waiting for readers after every pointer update, > and resizes require many pointer updates, so this would quickly become > prohibitive. > > qht-fixed-nomru shows that MRU promotion is advisable for undersized > hash tables. > > However, qht-dyn-mru shows that MRU promotion is not important if the > hash table is properly sized: there is virtually no difference in > performance between qht-dyn-nomru and qht-dyn-mru. > > Before this patch, we're at X=15 on "xxhash"; after this patch, we're at > X=15 @ qht-dyn-nomru. This patch thus matches the best performance that we > can achieve with optimum sizing of the hash table, while keeping the hash > table scalable for readers. > > The improvement we get before and after this patch for booting debian jessie > with arm-softmmu is: > > - Intel Xeon E5-2690: 10.5% less time > - Intel i7-4790K: 5.2% less time > > We could get this same improvement _for this particular workload_ by > statically increasing the size of the hash table. But this would hurt > workloads that do not need a large hash table. The dynamic (upward) > resizing allows us to start small and enlarge the hash table as needed. > > A quick note on downsizing: the table is resized back to 2**15 buckets > on every tb_flush; this makes sense because it is not guaranteed that the > table will reach the same number of TBs later on (e.g. most bootup code is > thrown away after boot); it makes sense to grow the hash table as > more code blocks are translated. This also avoids the complication of > having to build downsizing hysteresis logic into qht. > > Signed-off-by: Emilio G. Cota <c...@braap.org> > --- > cpu-exec.c | 82 ++++++++++++++++++++++++----------------------- > include/exec/exec-all.h | 9 +++--- > include/exec/tb-hash.h | 5 +-- > translate-all.c | 84 > ++++++++++++++++++++++--------------------------- > 4 files changed, 85 insertions(+), 95 deletions(-) > > diff --git a/cpu-exec.c b/cpu-exec.c > index 4194a4a..e948ffd 100644 > --- a/cpu-exec.c > +++ b/cpu-exec.c > @@ -217,55 +217,59 @@ static void cpu_exec_nocache(CPUState *cpu, int > max_cycles, > tb_free(tb); > } > > +struct tb_desc { > + target_ulong pc; > + target_ulong cs_base; > + uint64_t flags; > + tb_page_addr_t phys_page1; > + CPUArchState *env; > +}; > + > +static bool tb_cmp(const void *p, const void *d) > +{ > + const TranslationBlock *tb = p; > + const struct tb_desc *desc = d; > + > + if (tb->pc == desc->pc && > + tb->page_addr[0] == desc->phys_page1 && > + tb->cs_base == desc->cs_base && > + tb->flags == desc->flags) { > + /* check next page if needed */ > + if (tb->page_addr[1] == -1) { > + return true; > + } else { > + tb_page_addr_t phys_page2; > + target_ulong virt_page2; > + > + virt_page2 = (desc->pc & TARGET_PAGE_MASK) + TARGET_PAGE_SIZE; > + phys_page2 = get_page_addr_code(desc->env, virt_page2); > + if (tb->page_addr[1] == phys_page2) { > + return true; > + } > + } > + } > + return false; > +} > + > static TranslationBlock *tb_find_physical(CPUState *cpu, > target_ulong pc, > target_ulong cs_base, > uint64_t flags) > { > - CPUArchState *env = (CPUArchState *)cpu->env_ptr; > - TranslationBlock *tb, **ptb1; > unsigned int h; > - tb_page_addr_t phys_pc, phys_page1; > - target_ulong virt_page2; > + tb_page_addr_t phys_pc; > + struct tb_desc desc; > > tcg_ctx.tb_ctx.tb_invalidated_flag = 0; > > - /* find translated block using physical mappings */ > - phys_pc = get_page_addr_code(env, pc); > - phys_page1 = phys_pc & TARGET_PAGE_MASK; > + desc.env = (CPUArchState *)cpu->env_ptr; > + desc.cs_base = cs_base; > + desc.flags = flags; > + desc.pc = pc; > + phys_pc = get_page_addr_code(desc.env, pc); > + desc.phys_page1 = phys_pc & TARGET_PAGE_MASK; > h = tb_hash_func(phys_pc, pc, flags); > - ptb1 = &tcg_ctx.tb_ctx.tb_phys_hash[h]; > - for(;;) { > - tb = *ptb1; > - if (!tb) { > - return NULL; > - } > - if (tb->pc == pc && > - tb->page_addr[0] == phys_page1 && > - tb->cs_base == cs_base && > - tb->flags == flags) { > - /* check next page if needed */ > - if (tb->page_addr[1] != -1) { > - tb_page_addr_t phys_page2; > - > - virt_page2 = (pc & TARGET_PAGE_MASK) + > - TARGET_PAGE_SIZE; > - phys_page2 = get_page_addr_code(env, virt_page2); > - if (tb->page_addr[1] == phys_page2) { > - break; > - } > - } else { > - break; > - } > - } > - ptb1 = &tb->phys_hash_next; > - } > - > - /* Move the TB to the head of the list */ > - *ptb1 = tb->phys_hash_next; > - tb->phys_hash_next = tcg_ctx.tb_ctx.tb_phys_hash[h]; > - tcg_ctx.tb_ctx.tb_phys_hash[h] = tb; > - return tb; > + return qht_lookup(&tcg_ctx.tb_ctx.htable, tb_cmp, &desc, h); > } > > static TranslationBlock *tb_find_slow(CPUState *cpu, > diff --git a/include/exec/exec-all.h b/include/exec/exec-all.h > index 7362095..a894817 100644 > --- a/include/exec/exec-all.h > +++ b/include/exec/exec-all.h > @@ -21,6 +21,7 @@ > #define _EXEC_ALL_H_ > > #include "qemu-common.h" > +#include "qemu/qht.h" > > /* allow to see translation results - the slowdown should be negligible, so > we leave it */ > #define DEBUG_DISAS > @@ -211,8 +212,8 @@ static inline void tlb_flush_by_mmuidx(CPUState *cpu, ...) > > #define CODE_GEN_ALIGN 16 /* must be >= of the size of a icache > line */ > > -#define CODE_GEN_PHYS_HASH_BITS 15 > -#define CODE_GEN_PHYS_HASH_SIZE (1 << CODE_GEN_PHYS_HASH_BITS) > +#define CODE_GEN_HTABLE_BITS 15 > +#define CODE_GEN_HTABLE_SIZE (1 << CODE_GEN_HTABLE_BITS) > > /* Estimated block size for TB allocation. */ > /* ??? The following is based on a 2015 survey of x86_64 host output. > @@ -248,8 +249,6 @@ struct TranslationBlock { > > void *tc_ptr; /* pointer to the translated code */ > uint8_t *tc_search; /* pointer to search data */ > - /* next matching tb for physical address. */ > - struct TranslationBlock *phys_hash_next; > /* original tb when cflags has CF_NOCACHE */ > struct TranslationBlock *orig_tb; > /* first and second physical page containing code. The lower bit > @@ -280,7 +279,7 @@ typedef struct TBContext TBContext; > struct TBContext { > > TranslationBlock *tbs; > - TranslationBlock *tb_phys_hash[CODE_GEN_PHYS_HASH_SIZE]; > + struct qht htable; > int nb_tbs; > /* any access to the tbs or the page table must use this lock */ > QemuMutex tb_lock; > diff --git a/include/exec/tb-hash.h b/include/exec/tb-hash.h > index c4942e1..fabc936 100644 > --- a/include/exec/tb-hash.h > +++ b/include/exec/tb-hash.h > @@ -20,7 +20,6 @@ > #ifndef EXEC_TB_HASH > #define EXEC_TB_HASH > > -#include "exec/exec-all.h" > #include "qemu/xxhash.h" > > /* Only the bottom TB_JMP_PAGE_BITS of the jump cache hash bits vary for > @@ -54,13 +53,11 @@ uint32_t tb_hash_func(tb_page_addr_t phys_pc, > target_ulong pc, uint64_t flags) > target_ulong pc; > uint64_t flags; > } QEMU_PACKED k; > - unsigned int hash; > > k.phys_pc = phys_pc; > k.pc = pc; > k.flags = flags; > - hash = qemu_xxh32((uint32_t *)&k, sizeof(k) / sizeof(uint32_t), 1); > - return hash & (CODE_GEN_PHYS_HASH_SIZE - 1); > + return qemu_xxh32((uint32_t *)&k, sizeof(k) / sizeof(uint32_t), 1); > } > > #endif > diff --git a/translate-all.c b/translate-all.c > index 8e7f9a7..f0d7f1a 100644 > --- a/translate-all.c > +++ b/translate-all.c > @@ -735,6 +735,13 @@ static inline void code_gen_alloc(size_t tb_size) > qemu_mutex_init(&tcg_ctx.tb_ctx.tb_lock); > } > > +static void tb_htable_init(void) > +{ > + unsigned int mode = QHT_MODE_AUTO_RESIZE | QHT_MODE_MRU_INSERT; > + > + qht_init(&tcg_ctx.tb_ctx.htable, CODE_GEN_HTABLE_SIZE, mode); > +} > + > /* Must be called before using the QEMU cpus. 'tb_size' is the size > (in bytes) allocated to the translation buffer. Zero means default > size. */ > @@ -742,6 +749,7 @@ void tcg_exec_init(unsigned long tb_size) > { > cpu_gen_init(); > page_init(); > + tb_htable_init(); > code_gen_alloc(tb_size); > #if defined(CONFIG_SOFTMMU) > /* There's no guest base to take into account, so go ahead and > @@ -843,7 +851,7 @@ void tb_flush(CPUState *cpu) > memset(cpu->tb_jmp_cache, 0, sizeof(cpu->tb_jmp_cache)); > } > > - memset(tcg_ctx.tb_ctx.tb_phys_hash, 0, > sizeof(tcg_ctx.tb_ctx.tb_phys_hash)); > + qht_reset_size(&tcg_ctx.tb_ctx.htable, CODE_GEN_HTABLE_SIZE); > page_flush_tb(); > > tcg_ctx.code_gen_ptr = tcg_ctx.code_gen_buffer; > @@ -854,60 +862,45 @@ void tb_flush(CPUState *cpu) > > #ifdef DEBUG_TB_CHECK > > -static void tb_invalidate_check(target_ulong address) > +static void > +__tb_invalidate_check(struct qht *ht, void *p, uint32_t hash, void > *userp)
No __ functions please. > { > - TranslationBlock *tb; > - int i; > + TranslationBlock *tb = p; > + target_ulong addr = *(target_ulong *)userp; > > - address &= TARGET_PAGE_MASK; > - for (i = 0; i < CODE_GEN_PHYS_HASH_SIZE; i++) { > - for (tb = tcg_ctx.tb_ctx.tb_phys_hash[i]; tb != NULL; > - tb = tb->phys_hash_next) { > - if (!(address + TARGET_PAGE_SIZE <= tb->pc || > - address >= tb->pc + tb->size)) { > - printf("ERROR invalidate: address=" TARGET_FMT_lx > - " PC=%08lx size=%04x\n", > - address, (long)tb->pc, tb->size); > - } > - } > + if (!(addr + TARGET_PAGE_SIZE <= tb->pc || addr >= tb->pc + tb->size)) { > + printf("ERROR invalidate: address=" TARGET_FMT_lx > + " PC=%08lx size=%04x\n", addr, (long)tb->pc, tb->size); > } > } > > -/* verify that all the pages have correct rights for code */ > -static void tb_page_check(void) > +static void tb_invalidate_check(target_ulong address) > { > - TranslationBlock *tb; > - int i, flags1, flags2; > - > - for (i = 0; i < CODE_GEN_PHYS_HASH_SIZE; i++) { > - for (tb = tcg_ctx.tb_ctx.tb_phys_hash[i]; tb != NULL; > - tb = tb->phys_hash_next) { > - flags1 = page_get_flags(tb->pc); > - flags2 = page_get_flags(tb->pc + tb->size - 1); > - if ((flags1 & PAGE_WRITE) || (flags2 & PAGE_WRITE)) { > - printf("ERROR page flags: PC=%08lx size=%04x f1=%x f2=%x\n", > - (long)tb->pc, tb->size, flags1, flags2); > - } > - } > - } > + address &= TARGET_PAGE_MASK; > + qht_iter(&tcg_ctx.tb_ctx.htable, __tb_invalidate_check, &address); > } > > -#endif > - > -static inline void tb_hash_remove(TranslationBlock **ptb, TranslationBlock > *tb) > +static void __tb_page_check(struct qht *ht, void *p, uint32_t hash, > void *userp) And here. > { > - TranslationBlock *tb1; > + TranslationBlock *tb = p; > + int flags1, flags2; > > - for (;;) { > - tb1 = *ptb; > - if (tb1 == tb) { > - *ptb = tb1->phys_hash_next; > - break; > - } > - ptb = &tb1->phys_hash_next; > + flags1 = page_get_flags(tb->pc); > + flags2 = page_get_flags(tb->pc + tb->size - 1); > + if ((flags1 & PAGE_WRITE) || (flags2 & PAGE_WRITE)) { > + printf("ERROR page flags: PC=%08lx size=%04x f1=%x f2=%x\n", > + (long)tb->pc, tb->size, flags1, flags2); > } > } > > +/* verify that all the pages have correct rights for code */ > +static void tb_page_check(void) > +{ > + qht_iter(&tcg_ctx.tb_ctx.htable, __tb_page_check, NULL); > +} > + > +#endif > + > static inline void tb_page_remove(TranslationBlock **ptb, TranslationBlock > *tb) > { > TranslationBlock *tb1; > @@ -973,7 +966,7 @@ void tb_phys_invalidate(TranslationBlock *tb, > tb_page_addr_t page_addr) > /* remove the TB from the hash list */ > phys_pc = tb->page_addr[0] + (tb->pc & ~TARGET_PAGE_MASK); > h = tb_hash_func(phys_pc, tb->pc, tb->flags); > - tb_hash_remove(&tcg_ctx.tb_ctx.tb_phys_hash[h], tb); > + qht_remove(&tcg_ctx.tb_ctx.htable, tb, h); > > /* remove the TB from the page list */ > if (tb->page_addr[0] != page_addr) { > @@ -1472,13 +1465,10 @@ static void tb_link_page(TranslationBlock *tb, > tb_page_addr_t phys_pc, > tb_page_addr_t phys_page2) > { > unsigned int h; > - TranslationBlock **ptb; > > /* add in the hash table */ > h = tb_hash_func(phys_pc, tb->pc, tb->flags); > - ptb = &tcg_ctx.tb_ctx.tb_phys_hash[h]; > - tb->phys_hash_next = *ptb; > - *ptb = tb; > + qht_insert(&tcg_ctx.tb_ctx.htable, tb, h); > > /* add in the page list */ > tb_alloc_page(tb, 0, phys_pc & TARGET_PAGE_MASK); Apart from the static function names it looks good. I particularly like the net loss of code thanks to using utility code ;-) Reviewed-by: Alex Bennée <alex.ben...@linaro.org> -- Alex Bennée