From patchwork Thu Jun 14 19:31:36 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 138619 Delivered-To: patch@linaro.org Received: by 2002:a2e:970d:0:0:0:0:0 with SMTP id r13-v6csp2528480lji; Thu, 14 Jun 2018 12:40:43 -0700 (PDT) X-Google-Smtp-Source: ADUXVKLmtUfrbd0ZBivEZVOeVCQg8D6EatXhADUTEEuUP8s5Xl9cmadqMUhub43cIdBUm09N6y2f X-Received: by 2002:a0c:b297:: with SMTP id r23-v6mr3708775qve.74.1529005243655; Thu, 14 Jun 2018 12:40:43 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1529005243; cv=none; d=google.com; s=arc-20160816; b=nrC5CYPLTJD3Zn+r2gt+khnzEuXpnHdLNP3h0UWqDW3diNXvv6Fg9jlcCjxIMNvJ9g EsBr9vZFV9tCEAnit19hpsORQGJB6/+p3W+bPuqhw0VOdl0Xm0sWb8iNXT6PEBR9SXOx ytknDhGjxpcq/vL9kPBJchIq+tLOYuKnw+c8VniOdNkl+DiDeRZlHeTqiqU7wjAhHqri IUQkWG36ayOnAUHU0v0pvYpEvEo5lMPP1lgksOxFw2ye9v3ihd6KsBK6EYLEQUHrEv0W /CpF8m3TB4vfnGM5FNsJw5Qg6g8DReZ+AwqT0JuVYQ8N4gsK2C4ws78uTKAZ/0wDM3tz 2H7A== 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=ysyFJl0D3R0Ia8FUeXmF+dWhVqMK5ODQjJpUGWYpfZORnkssbqSuTb85n6MbflveWw 0c5EXxGUE8kpQxP575Ch/Jptv9pjGevxf6WEOFzBgd0gY0gDdbEjO8Q3Qureoja8WrRY ce5Nqdsom0MoO3Yj5LTG3mwMmn2ZQoTClbc5coS4BawhkF4ekOJWB9dmxoT97TYn2hnX hyhNhafq9hy+gCAdDuWasELxE0KVTdLcsqmHcSgh1zzg0YYUp3yddFF1Esp0sL+yLkDe 223ePtYA23yLZAXstGJRXYrdj6DdRmFMhzHaMnlrxlER33Z6mQS8mQjglNq/UzSZ+LWz aafg== ARC-Authentication-Results: i=1; mx.google.com; dkim=fail header.i=@linaro.org header.s=google header.b=buHVfDEC; 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 t67-v6si1202936qkd.147.2018.06.14.12.40.43 for (version=TLS1 cipher=AES128-SHA bits=128/128); Thu, 14 Jun 2018 12:40:43 -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=buHVfDEC; 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]:42373 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fTY6s-0005FC-Uc for patch@linaro.org; Thu, 14 Jun 2018 15:40:43 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:36934) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fTXyZ-0006wl-OO for qemu-devel@nongnu.org; Thu, 14 Jun 2018 15:32:08 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fTXyY-0005n5-4U for qemu-devel@nongnu.org; Thu, 14 Jun 2018 15:32:07 -0400 Received: from mail-pf0-x242.google.com ([2607:f8b0:400e:c00::242]:41796) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1fTXyX-0005lj-VA for qemu-devel@nongnu.org; Thu, 14 Jun 2018 15:32:06 -0400 Received: by mail-pf0-x242.google.com with SMTP id a11-v6so3706183pff.8 for ; Thu, 14 Jun 2018 12:32:05 -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=buHVfDECFOZOri8UOzBkKinkOOgjycG79VfIiaQQezinfx69+t7nLKpj4MmBJUcrzl rngYq16uVzhK3ykJ1171SGp+T3R8htTIrvC1ILXPLI+vgTwu0ke0vVM37mciM1H9BbYs BRVtuxObQVwmY80MTEXq+/AQIQrH/YzC4HcMM= 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=LZH0ijmOhHQdbeQ/BP2UVwjC5oX3M/EbUNeD6RPaTIz9w9MwGzYzKqyfYNGt/EgJQb a9aQggYkHu1oNqgtZ4t3W9nYnirbuF4FxhMCqf9YcK3CTy3X3jG1y5VM8/QgjnKkINls Ebwt6H50sWJWBCuZzG3z4f794msRaF1iEM1/0PT6qr9GuyEnltsahuRuOYBsa7OR+hTK 2QS/renRd4OQ5M0E00HKK9ZDdDLbLT15ryPhZ9eQ65Ni2olViigGHAOuNs7MAJV0CHHc dV+KZKOtngGVGWbxjiGphFyVn0TuH/I40dUvGqMrsO1uaQR7IW9y1QZA+wdq+2A5HLTc ouug== X-Gm-Message-State: APt69E0unp1M5Y/W95fIXcMMpXpFMHPq0CK96a0AO3mYBR1Xxy9uf8JA oxvOwwJ8/hcjro3uAK7ToZEQ0f95M6A= X-Received: by 2002:a63:a44a:: with SMTP id c10-v6mr3378721pgp.198.1529004724721; Thu, 14 Jun 2018 12:32:04 -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 x24-v6sm11532184pfj.104.2018.06.14.12.32.03 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Thu, 14 Jun 2018 12:32:03 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Date: Thu, 14 Jun 2018 09:31:36 -1000 Message-Id: <20180614193147.29680-8-richard.henderson@linaro.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180614193147.29680-1-richard.henderson@linaro.org> References: <20180614193147.29680-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:c00::242 Subject: [Qemu-devel] [PULL 07/18] 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.