From patchwork Fri Jun 15 19:43:42 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 138753 Delivered-To: patch@linaro.org Received: by 2002:a2e:970d:0:0:0:0:0 with SMTP id r13-v6csp1245949lji; Fri, 15 Jun 2018 12:45:49 -0700 (PDT) X-Google-Smtp-Source: ADUXVKLwt1beHYIw3sJuH7vtdh3PGTHjsMemioxvDVPoeV98HVS6nAUI8AEZQ6DUeFdkKOIF6SKp X-Received: by 2002:a37:660f:: with SMTP id a15-v6mr2596919qkc.440.1529091949725; Fri, 15 Jun 2018 12:45:49 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1529091949; cv=none; d=google.com; s=arc-20160816; b=ppktLa9pwyjHdnjEaH8VF8gcMh4E1IUtErjlLfplSgUtK1aMxjPdOmK9j4YGfEMSO8 uA4l70fwFhk3/amABenhgID5A57ByXMNnoQNLxKIfP51Kn+/HLIyJ+xMEES2wi7IJQdH qgACcYUeMpFdwljNkAHhbkfAlDzXEJ5yXo+r0HwxvYLu802+9RfzVweVGGYBEMpGl32j pMBhHMzFgQjZ4+6HV/CtXzKRS8RqSASgeCVz8Vd6eX0VQ3eAq8TgjS3HS7RrjKaBNtEQ tvGNFeq3aAlFDzBjvGc+bncBdhNuwh65nv2jfxP7o3QD4eNsVonwq+8AVZHa4gfc5ZsQ QMyA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject :content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:to:from:dkim-signature:arc-authentication-results; bh=+wmxg/OG714qNbfIRNlSF9jWomNEICTIUlUkDChX+hI=; b=YKoO/hJUWSjbYtPTEGVJS/xasCVrsI/qboS789mNMGQ5gOPN2r6kCG27L5eHfXdvbd 4NOqaANcdUsdP6RhsK8n9i4xxidkn0LudQsWteBl1zbf6ghqJxXnwG89jYXgrS6Z1/02 54GaBT57m1jy7mrslrDWWqLgihIE/+EPazdox8YpdJil1UV6xyQ8r+98fW+pGFHrxBSP wlDwssRQPycbxTJfmQ9Cc/sGrnMCb69OnbFalHX5j8r7NvFA4PtqnqiJbMh67la89pei ppAB2v4aP1uMEHtPmLrJxc7tKXGBwBUlmuoLq53fRngrSWHTzMiJtq1sSNux/0D0FVHF Br0w== ARC-Authentication-Results: i=1; mx.google.com; dkim=fail header.i=@linaro.org header.s=google header.b=GxNYARp6; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 2001:4830:134:3::11 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [2001:4830:134:3::11]) by mx.google.com with ESMTPS id e187-v6si948180qkc.193.2018.06.15.12.45.49 for (version=TLS1 cipher=AES128-SHA bits=128/128); Fri, 15 Jun 2018 12:45:49 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 2001:4830:134:3::11 as permitted sender) client-ip=2001:4830:134:3::11; Authentication-Results: mx.google.com; dkim=fail header.i=@linaro.org header.s=google header.b=GxNYARp6; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 2001:4830:134:3::11 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1]:48959 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fTufN-00019d-4W for patch@linaro.org; Fri, 15 Jun 2018 15:45:49 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:51556) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fTudt-0000NT-KX for qemu-devel@nongnu.org; Fri, 15 Jun 2018 15:44:19 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fTudq-0002Uk-9C for qemu-devel@nongnu.org; Fri, 15 Jun 2018 15:44:17 -0400 Received: from mail-pg0-x241.google.com ([2607:f8b0:400e:c05::241]:33039) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1fTudq-0002UR-1m for qemu-devel@nongnu.org; Fri, 15 Jun 2018 15:44:14 -0400 Received: by mail-pg0-x241.google.com with SMTP id e11-v6so4860360pgq.0 for ; Fri, 15 Jun 2018 12:44:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=+wmxg/OG714qNbfIRNlSF9jWomNEICTIUlUkDChX+hI=; b=GxNYARp6istrOzdiCpiy+RtjcQ0v41KsbIXBK/ErHeuDSbE+8uV9TxWksl4gnKq67P 744PSFgWhQE5nXLWfvqMtDvUoKywJZl8eimc4DqZPi77su7dCEri753B/2jMwiRBKDkM JD8y8iMHWn7N9CxCKB39iFQ36qIdpvyvQ9t30= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=+wmxg/OG714qNbfIRNlSF9jWomNEICTIUlUkDChX+hI=; b=KF3slaaf7ic5Pw/tHrSWvv2CaP2yShbiwp0oLePSkSPW5/tvB9czTzvGbcgTfmfWRB pqU81g+MtyfG4MWbKCT0bNUm6rgH7u12I/K3QSV+GYXZ3cKDHQsHO8v49VePtBnEk9Id seCfHDNQ4dC6m/zoDqEuse4FBg2slZ8f/HW59I/TjiwC7ajVwuHGKOy0DawzW1nR6Jsz r/+5HblH6Nc0bxGJ70gP+cGJuuMHTkx2HlsBsXPiyzXOYqQK9nFbykWK4vzk7dQufirk YMYibcg6l1c5+QTyxLXR8E9JN78rfY3q0kxAUX06qwPpbItRBZDJRE3LUGbEEFliXW4w zwjg== X-Gm-Message-State: APt69E1N35vOgRB3iu7GmGEDpx/t76AwgYIT/v3O7McqSWaxE51r/O/V 9CSKW/+dZNOFzdZQ7lNwLMPXnWRFGKQ= X-Received: by 2002:a63:85c8:: with SMTP id u191-v6mr2678283pgd.300.1529091852810; Fri, 15 Jun 2018 12:44:12 -0700 (PDT) Received: from cloudburst.twiddle.net (rrcs-173-198-77-219.west.biz.rr.com. [173.198.77.219]) by smtp.gmail.com with ESMTPSA id 29-v6sm14038360pfj.14.2018.06.15.12.44.11 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 15 Jun 2018 12:44:11 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Date: Fri, 15 Jun 2018 09:43:42 -1000 Message-Id: <20180615194354.12489-8-richard.henderson@linaro.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180615194354.12489-1-richard.henderson@linaro.org> References: <20180615194354.12489-1-richard.henderson@linaro.org> MIME-Version: 1.0 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:400e:c05::241 Subject: [Qemu-devel] [PULL v2 07/19] translate-all: make l1_map lockless 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+patch=linaro.org@nongnu.org Sender: "Qemu-devel" From: "Emilio G. Cota" Groundwork for supporting parallel TCG generation. We never remove entries from the radix tree, so we can use cmpxchg to implement lockless insertions. Reviewed-by: Richard Henderson Reviewed-by: Alex Bennée Signed-off-by: Emilio G. Cota Signed-off-by: Richard Henderson --- accel/tcg/translate-all.c | 24 ++++++++++++++---------- docs/devel/multi-thread-tcg.txt | 4 ++-- 2 files changed, 16 insertions(+), 12 deletions(-) -- 2.17.1 diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c index 52e62125ed..52273e5846 100644 --- a/accel/tcg/translate-all.c +++ b/accel/tcg/translate-all.c @@ -469,20 +469,12 @@ static void page_init(void) #endif } -/* If alloc=1: - * Called with tb_lock held for system emulation. - * Called with mmap_lock held for user-mode emulation. - */ static PageDesc *page_find_alloc(tb_page_addr_t index, int alloc) { PageDesc *pd; void **lp; int i; - if (alloc) { - assert_memory_lock(); - } - /* Level 1. Always allocated. */ lp = l1_map + ((index >> v_l1_shift) & (v_l1_size - 1)); @@ -491,11 +483,17 @@ static PageDesc *page_find_alloc(tb_page_addr_t index, int alloc) void **p = atomic_rcu_read(lp); if (p == NULL) { + void *existing; + if (!alloc) { return NULL; } p = g_new0(void *, V_L2_SIZE); - atomic_rcu_set(lp, p); + existing = atomic_cmpxchg(lp, NULL, p); + if (unlikely(existing)) { + g_free(p); + p = existing; + } } lp = p + ((index >> (i * V_L2_BITS)) & (V_L2_SIZE - 1)); @@ -503,11 +501,17 @@ static PageDesc *page_find_alloc(tb_page_addr_t index, int alloc) pd = atomic_rcu_read(lp); if (pd == NULL) { + void *existing; + if (!alloc) { return NULL; } pd = g_new0(PageDesc, V_L2_SIZE); - atomic_rcu_set(lp, pd); + existing = atomic_cmpxchg(lp, NULL, pd); + if (unlikely(existing)) { + g_free(pd); + pd = existing; + } } return pd + (index & (V_L2_SIZE - 1)); diff --git a/docs/devel/multi-thread-tcg.txt b/docs/devel/multi-thread-tcg.txt index a99b4564c6..faf8918b23 100644 --- a/docs/devel/multi-thread-tcg.txt +++ b/docs/devel/multi-thread-tcg.txt @@ -134,8 +134,8 @@ tb_set_jmp_target() code. Modification to the linked lists that allow searching for linked pages are done under the protect of the tb_lock(). -The global page table is protected by the tb_lock() in system-mode and -mmap_lock() in linux-user mode. +The global page table is a lockless radix tree; cmpxchg is used +to atomically insert new elements. The lookup caches are updated atomically and the lookup hash uses QHT which is designed for concurrent safe lookup.