From nobody Tue Oct 28 12:38:31 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 1522980925393224.0881322713659; Thu, 5 Apr 2018 19:15:25 -0700 (PDT) Received: from localhost ([::1]:43993 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f4GuN-0003nk-Fx for importer@patchew.org; Thu, 05 Apr 2018 22:15:19 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:58414) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1f4GsL-0002GA-6c for qemu-devel@nongnu.org; Thu, 05 Apr 2018 22:13:15 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1f4GsI-0003UB-Tv for qemu-devel@nongnu.org; Thu, 05 Apr 2018 22:13:13 -0400 Received: from out5-smtp.messagingengine.com ([66.111.4.29]:56219) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1f4GsI-0003TO-Oj for qemu-devel@nongnu.org; Thu, 05 Apr 2018 22:13:10 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 800F820B3B; Thu, 5 Apr 2018 22:13:10 -0400 (EDT) Received: from mailfrontend1 ([10.202.2.162]) by compute4.internal (MEProxy); Thu, 05 Apr 2018 22:13:10 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 3EC80E502E; Thu, 5 Apr 2018 22:13:10 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=gWwkbrRXcVE5d5yKbFRBcT36K3 8CuBm+X+hItImPtpY=; b=wyZE0Y3Jk7R4R64eSvvkMeG7RupbYhU2HdnUVlb/gq 1044LWPom5B2fsWe9X3klptSsBnJRqfz/93+/OBoznthRyDvrXhCM+U/IFklNq6K qrXjB21jkGuaf+n+qzYWss0aZfw57aPJG2UVYDMEeH2UUdnj9yWAa+bF8cYZB6xj U= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm2; bh=gWwkbr RXcVE5d5yKbFRBcT36K38CuBm+X+hItImPtpY=; b=G33L4bB7f1jeco717o0X94 m9dgMZGv99rRJgul+dnLGfOQQV6IyLAOncCnEGSc1akLoOhVr4MRtwrZjisO8MMw ZVxht1f4p6FvupuDalt56aSXqSSXuIw9ZBFRJeezKs7r9zCTqeQYhoegAwexUt4w xb/jtg48NitTvZ5hCCXc6gaFANAWIKfxvgJqWj3R9jZarIXcpL2+X2rpTcab2Sxb wb71r4mXcX1s4nV21dYSLw9o3dhi1i0dFHvGF07xpu4UxwWeN8bUSL30Kspb/4Yd Va8XBF5NSScK1TzwC//WR/ZDBt4DfjDl7SuZrBoiS2K9WvZCvsNaeUT2UxlGgHZw == X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Thu, 5 Apr 2018 22:12:57 -0400 Message-Id: <1522980788-1252-7-git-send-email-cota@braap.org> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1522980788-1252-1-git-send-email-cota@braap.org> References: <1522980788-1252-1-git-send-email-cota@braap.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 66.111.4.29 Subject: [Qemu-devel] [PATCH v2 06/17] 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: Richard Henderson , =?UTF-8?q?Alex=20Benn=C3=A9e?= , Paolo Bonzini Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail: RSF_0 Z_629925259 SPT_0 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=C3=A9e Signed-off-by: Emilio G. Cota --- docs/devel/multi-thread-tcg.txt | 4 ++-- accel/tcg/translate-all.c | 24 ++++++++++++++---------- 2 files changed, 16 insertions(+), 12 deletions(-) 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. diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c index ecf898c..83aec43 100644 --- a/accel/tcg/translate-all.c +++ b/accel/tcg/translate-all.c @@ -469,20 +469,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 @@ -491,11 +483,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)); @@ -503,11 +501,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)); --=20 2.7.4