From patchwork Fri Jun 10 14:26:45 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 9169947 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id CE2FF604DB for ; Fri, 10 Jun 2016 14:37:22 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B9A4D28210 for ; Fri, 10 Jun 2016 14:37:22 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id ABDF528366; Fri, 10 Jun 2016 14:37:22 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 189FA28210 for ; Fri, 10 Jun 2016 14:37:20 +0000 (UTC) Received: from localhost ([::1]:41451 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bBNYl-0003b4-Ov for patchwork-qemu-devel@patchwork.kernel.org; Fri, 10 Jun 2016 10:37:19 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:46310) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bBNOq-0003ee-5S for qemu-devel@nongnu.org; Fri, 10 Jun 2016 10:27:06 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bBNOn-0005ha-IJ for qemu-devel@nongnu.org; Fri, 10 Jun 2016 10:27:03 -0400 Received: from mail-pf0-x244.google.com ([2607:f8b0:400e:c00::244]:34851) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bBNOn-0005hJ-8J for qemu-devel@nongnu.org; Fri, 10 Jun 2016 10:27:01 -0400 Received: by mail-pf0-x244.google.com with SMTP id t190so5238324pfb.2 for ; Fri, 10 Jun 2016 07:27:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=QkLjRJUk2te6TF+7Gx3DLxISTNI+86RkoSrIcxynvsY=; b=ePdKlB5EQkVHT4iO6xE1ozJ1oIK0hQZKIeLfPGuugBDS7oNt5szMTc2rnFspFaJFFw K3F79avRP5M91hxPMjbaS4jCA4Ql6948BSOzWfmssY9QgVs4jq+jl7lol8DPDKzxXe+L hITnmo1TndOLZYAAN/uyBZpx+IondgDwL0MRto05CiuUzgChPDsmiEJDAFCWMA2Z71TC zIod/33F2C0pRR4uoFENZbF9P+WiL7rhZ55CwsuSuq8OA683+Itw6IO/ZRKWquhk55N0 E0JmJIrPPdhDzJPFgmLjZZicVDec+N5a+8GJUi8IsP4oagI8nYImeNbj2raa5tBnZR6O to4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :in-reply-to:references:mime-version:content-transfer-encoding; bh=QkLjRJUk2te6TF+7Gx3DLxISTNI+86RkoSrIcxynvsY=; b=UNQll1L4ZoWwX2ZjnK55aGHqVsEumL6iTmEw9kkOBC2URvr2OemVWEAJi4FYrhpigs 0iTN4jmz1f+bT5nM4RUzvlTaUqP7T1ZoB7NmF1kLc397q2Jc/3l7OZrX7NainPrBx2oQ SfZ48KSOdIlcxY72m6CQM9KkuMs5NMGGp6y0QSLsT8tbcX21eYtGU6xpsCiE+gfdGklK SVOmuqhfjR72qDFFDUf0h3ExGCoQMuWSBTaDKsWzph/nmLU0Fsvc6QMF6gWP18tvPHuY lMD9aEXWbz4YG+niYSOUFdgZXn9gbV4+wD9LNRGEGVeauZOpGmTuLbVPaj7mSev9vna6 St4A== X-Gm-Message-State: ALyK8tKsj3vXrshflARr44U8t+Qw3opsmgR75gRw4PALuMlTxMSEJOTr5HkuK06Lv7M8rw== X-Received: by 10.98.90.67 with SMTP id o64mr2629251pfb.150.1465568819528; Fri, 10 Jun 2016 07:26:59 -0700 (PDT) Received: from anchor.twiddle.net (71-37-54-227.tukw.qwest.net. [71.37.54.227]) by smtp.gmail.com with ESMTPSA id vy8sm18227219pab.22.2016.06.10.07.26.58 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 10 Jun 2016 07:26:58 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Date: Fri, 10 Jun 2016 07:26:45 -0700 Message-Id: <1465568813-19771-8-git-send-email-rth@twiddle.net> X-Mailer: git-send-email 2.5.5 In-Reply-To: <1465568813-19771-1-git-send-email-rth@twiddle.net> References: <1465568813-19771-1-git-send-email-rth@twiddle.net> MIME-Version: 1.0 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2607:f8b0:400e:c00::244 Subject: [Qemu-devel] [PULL 07/15] tb hash: hash phys_pc, pc, and flags with xxhash X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: peter.maydell@linaro.org, "Emilio G. Cota" Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" X-Virus-Scanned: ClamAV using ClamSMTP From: "Emilio G. Cota" For some workloads such as arm bootup, tb_phys_hash is performance-critical. The is due to the high frequency of accesses to the hash table, originated by (frequent) TLB flushes that wipe out the cpu-private tb_jmp_cache's. More info: https://lists.nongnu.org/archive/html/qemu-devel/2016-03/msg05098.html To dig further into this I modified an arm image booting debian jessie to immediately shut down after boot. Analysis revealed that quite a bit of time is unnecessarily spent in tb_phys_hash: the cause is poor hashing that results in very uneven loading of chains in the hash table's buckets; the longest observed chain had ~550 elements. The appended addresses this with two changes: 1) Use xxhash as the hash table's hash function. xxhash is a fast, high-quality hashing function. 2) Feed the hashing function with not just tb_phys, but also pc and flags. This improves performance over using just tb_phys for hashing, since that resulted in some hash buckets having many TB's, while others getting very few; with these changes, the longest observed chain on a single hash bucket is brought down from ~550 to ~40. Tests show that the other element checked for in tb_find_physical, cs_base, is always a match when tb_phys+pc+flags are a match, so hashing cs_base is wasteful. It could be that this is an ARM-only thing, though. UPDATE: On Tue, Apr 05, 2016 at 08:41:43 -0700, Richard Henderson wrote: > The cs_base field is only used by i386 (in 16-bit modes), and sparc (for a TB > consisting of only a delay slot). > It may well still turn out to be reasonable to ignore cs_base for hashing. BTW, after this change the hash table should not be called "tb_hash_phys" anymore; this is addressed later in this series. This change gives consistent bootup time improvements. I tested two host machines: - Intel Xeon E5-2690: 11.6% less time - Intel i7-4790K: 19.2% less time Increasing the number of hash buckets yields further improvements. However, using a larger, fixed number of buckets can degrade performance for other workloads that do not translate as many blocks (600K+ for debian-jessie arm bootup). This is dealt with later in this series. Reviewed-by: Sergey Fedorov Reviewed-by: Richard Henderson Reviewed-by: Alex Bennée Signed-off-by: Emilio G. Cota Message-Id: <1465412133-3029-8-git-send-email-cota@braap.org> Signed-off-by: Richard Henderson --- cpu-exec.c | 4 ++-- include/exec/tb-hash.h | 8 ++++++-- translate-all.c | 10 +++++----- 3 files changed, 13 insertions(+), 9 deletions(-) diff --git a/cpu-exec.c b/cpu-exec.c index f7c642f..b9e294c 100644 --- a/cpu-exec.c +++ b/cpu-exec.c @@ -232,13 +232,13 @@ static TranslationBlock *tb_find_physical(CPUState *cpu, { CPUArchState *env = (CPUArchState *)cpu->env_ptr; TranslationBlock *tb, **tb_hash_head, **ptb1; - unsigned int h; + uint32_t h; tb_page_addr_t phys_pc, phys_page1; /* find translated block using physical mappings */ phys_pc = get_page_addr_code(env, pc); phys_page1 = phys_pc & TARGET_PAGE_MASK; - h = tb_phys_hash_func(phys_pc); + h = tb_hash_func(phys_pc, pc, flags); /* Start at head of the hash entry */ ptb1 = tb_hash_head = &tcg_ctx.tb_ctx.tb_phys_hash[h]; diff --git a/include/exec/tb-hash.h b/include/exec/tb-hash.h index 0f4e8a0..88ccfd1 100644 --- a/include/exec/tb-hash.h +++ b/include/exec/tb-hash.h @@ -20,6 +20,9 @@ #ifndef EXEC_TB_HASH #define EXEC_TB_HASH +#include "exec/exec-all.h" +#include "exec/tb-hash-xx.h" + /* Only the bottom TB_JMP_PAGE_BITS of the jump cache hash bits vary for addresses on the same page. The top bits are the same. This allows TLB invalidation to quickly clear a subset of the hash table. */ @@ -43,9 +46,10 @@ static inline unsigned int tb_jmp_cache_hash_func(target_ulong pc) | (tmp & TB_JMP_ADDR_MASK)); } -static inline unsigned int tb_phys_hash_func(tb_page_addr_t pc) +static inline +uint32_t tb_hash_func(tb_page_addr_t phys_pc, target_ulong pc, uint32_t flags) { - return (pc >> 2) & (CODE_GEN_PHYS_HASH_SIZE - 1); + return tb_hash_func5(phys_pc, pc, flags) & (CODE_GEN_PHYS_HASH_SIZE - 1); } #endif diff --git a/translate-all.c b/translate-all.c index 118e7d3..d75737c 100644 --- a/translate-all.c +++ b/translate-all.c @@ -992,12 +992,12 @@ void tb_phys_invalidate(TranslationBlock *tb, tb_page_addr_t page_addr) { CPUState *cpu; PageDesc *p; - unsigned int h; + uint32_t h; tb_page_addr_t phys_pc; /* remove the TB from the hash list */ phys_pc = tb->page_addr[0] + (tb->pc & ~TARGET_PAGE_MASK); - h = tb_phys_hash_func(phys_pc); + h = tb_hash_func(phys_pc, tb->pc, tb->flags); tb_hash_remove(&tcg_ctx.tb_ctx.tb_phys_hash[h], tb); /* remove the TB from the page list */ @@ -1127,11 +1127,11 @@ static inline void tb_alloc_page(TranslationBlock *tb, static void tb_link_page(TranslationBlock *tb, tb_page_addr_t phys_pc, tb_page_addr_t phys_page2) { - unsigned int h; + uint32_t h; TranslationBlock **ptb; - /* add in the physical hash table */ - h = tb_phys_hash_func(phys_pc); + /* 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;