From nobody Fri Oct 24 20:04:04 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) client-ip=208.118.235.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; spf=pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org Return-Path: Received: from lists.gnu.org (208.118.235.17 [208.118.235.17]) by mx.zohomail.com with SMTPS id 1519710432169130.07380208603; Mon, 26 Feb 2018 21:47:12 -0800 (PST) Received: from localhost ([::1]:34957 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eqY6T-0001rz-Jg for importer@patchew.org; Tue, 27 Feb 2018 00:47:05 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:50939) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eqXzG-0004ab-Am for qemu-devel@nongnu.org; Tue, 27 Feb 2018 00:39:41 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eqXzC-0000QG-Lm for qemu-devel@nongnu.org; Tue, 27 Feb 2018 00:39:38 -0500 Received: from out2-smtp.messagingengine.com ([66.111.4.26]:35971) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eqXzC-0000PT-Gk for qemu-devel@nongnu.org; Tue, 27 Feb 2018 00:39:34 -0500 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 9171820C91; Tue, 27 Feb 2018 00:39:33 -0500 (EST) Received: from frontend2 ([10.202.2.161]) by compute4.internal (MEProxy); Tue, 27 Feb 2018 00:39:33 -0500 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 4D2CC24575; Tue, 27 Feb 2018 00:39:33 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :date:from:in-reply-to:message-id:references:subject:to :x-me-sender:x-me-sender:x-sasl-enc; s=mesmtp; bh=rD1LtsDhTsRmKM 1GJAsN6ZZ5CUl4Kk4YueIHszPzq/4=; b=omL+1QuwwNOv01IT0LWtR/oEX2UrxW hFbeHILzqTd4BuknndAKF91kjc7ionbeNI9Sm7f24p2ZfhLEHGiZE0Sjbli8g7ca klG87mhw8o/+/zRUIe9h+A33m42e2hRbikKfO4bvHhdxUp5b85BhaZv86Zo92qFw 0bzi/ZC+euH+c= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:date:from:in-reply-to:message-id :references:subject:to:x-me-sender:x-me-sender:x-sasl-enc; s= fm2; bh=rD1LtsDhTsRmKM1GJAsN6ZZ5CUl4Kk4YueIHszPzq/4=; b=bzfxz2he ywI1nDvuv+q3ZiI5drEtzYXMqRiOAcy0mS1wm4/qBGOyb2nHw2SW4fjCr/dl5zNc kv4rOBAU0lf/RHI+5ONGIi1Xv3Sdu+Ys/m8AxBsVymjFlrEb0ZRrkrvKDYsTXtEi pakT9YRreKdWZTktdGevmdwVVgl6TIMvXrzvffZuLXKNb2oS0luW87J6w6ABmxib 6WgAYokkT1VFvWlLpGUXqNdZArXQZ4skX0lx0KWy7u+8G/nHrJTKNZedz7xD7ljT aJHsC2N+zAAsNh53dHb4yBFfw6ZybR5c4HrVbblLwQCHTRxYiluU+D/Mr4jxx7Bg LokebZ97u0eUxQ== X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Tue, 27 Feb 2018 00:39:15 -0500 Message-Id: <1519709965-29833-7-git-send-email-cota@braap.org> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1519709965-29833-1-git-send-email-cota@braap.org> References: <1519709965-29833-1-git-send-email-cota@braap.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 66.111.4.26 Subject: [Qemu-devel] [PATCH 06/16] 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: Paolo Bonzini , Richard Henderson Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail: RSF_0 Z_629925259 SPT_0 Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Groundwork for supporting parallel TCG generation. We never remove entries from the radix tree, so we can use cmpxchg to implement lockless insertions. Signed-off-by: Emilio G. Cota Reviewed-by: Alex Benn=C3=A9e Reviewed-by: Richard Henderson --- accel/tcg/translate-all.c | 24 ++++++++++++++---------- docs/devel/multi-thread-tcg.txt | 4 ++-- 2 files changed, 16 insertions(+), 12 deletions(-) diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c index 06aa905..f2bfa71 100644 --- a/accel/tcg/translate-all.c +++ b/accel/tcg/translate-all.c @@ -472,20 +472,12 @@ static void page_init(void) #endif } =20 -/* If alloc=3D1: - * 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; =20 - if (alloc) { - assert_memory_lock(); - } - /* Level 1. Always allocated. */ lp =3D l1_map + ((index >> v_l1_shift) & (v_l1_size - 1)); =20 @@ -494,11 +486,17 @@ static PageDesc *page_find_alloc(tb_page_addr_t index= , int alloc) void **p =3D atomic_rcu_read(lp); =20 if (p =3D=3D NULL) { + void *existing; + if (!alloc) { return NULL; } p =3D g_new0(void *, V_L2_SIZE); - atomic_rcu_set(lp, p); + existing =3D atomic_cmpxchg(lp, NULL, p); + if (unlikely(existing)) { + g_free(p); + p =3D existing; + } } =20 lp =3D p + ((index >> (i * V_L2_BITS)) & (V_L2_SIZE - 1)); @@ -506,11 +504,17 @@ static PageDesc *page_find_alloc(tb_page_addr_t index= , int alloc) =20 pd =3D atomic_rcu_read(lp); if (pd =3D=3D NULL) { + void *existing; + if (!alloc) { return NULL; } pd =3D g_new0(PageDesc, V_L2_SIZE); - atomic_rcu_set(lp, pd); + existing =3D atomic_cmpxchg(lp, NULL, pd); + if (unlikely(existing)) { + g_free(pd); + pd =3D existing; + } } =20 return pd + (index & (V_L2_SIZE - 1)); diff --git a/docs/devel/multi-thread-tcg.txt b/docs/devel/multi-thread-tcg.= txt index a99b456..faf8918 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 li= sts that allow searching for linked pages are done under the protect of the tb_lock(). =20 -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. =20 The lookup caches are updated atomically and the lookup hash uses QHT which is designed for concurrent safe lookup. --=20 2.7.4