From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=74.125.82.178 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1793811432; b=5bKJ88LpfrVR3jANBSV+wBe3eHJeX4sLmvxRckRDxWwgRFOa5v6s/tDXyCiWBgw96hC0 aUIeFgiBmmVQTQFBDjouIxl6aCq8w0lMvud1tuesliIgMcuxA5DjoEe30Pri9eFzO/6zU +Mk8AM+uoXPisxefrvigGbuMwqG+EfI6ixvpJ8eD47h8onZWJkFk1DivAs9cAmKKK/8M6 EZXuI0hmUXFkndVIlbD0sGwyV0LW+2pcgs/bipPoIp/1h990958xjC1cw62ZLDxezeWWn QBvpIpSoA7yD6ALayW0TJEMagt3pSiJ3QKARvvBL+lv9+ydVOqIOFhsGtwTiG1zQsqA== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1793811432; h=DMARC-Filter:Received:DKIM-Signature:X-Google-DKIM-Signature: X-Forwarded-Encrypted:X-Gm-Message-State:X-Gm-Gg:X-Received:Received: From:To:Cc:Subject:Date:Message-ID:X-Mailer:In-Reply-To:References: MIME-Version:Content-Transfer-Encoding; bh=tXppOOg9gP9zhrC6rnkPUZoXeQTDUJQYOVYW2OTPzPI=; b=ff1KJj2XLMaHL+f1X/JEsCM7nZsqz7A5d7mldpXsLiZy/xMfqZf3AgAFUjgpZEWGlqPY X0hGG2nDu3GtMM6v1Lgl2jR4khcgAZ6dbTK66xfCp7d2H64zy1hDQJGwJJWxOnonSIXea 5d0cJwamxARFzh2fsMOZ3kP81lIdwg0BN3GQU5yoyJbL/FhXf32avXzx9tgyGa92xFwof IDykO3KnL+O03V8GuznkuobTVkFjEoKILdH8BYZEpd1N0MMv/65uBE0Ud1SYftQHbuXWg TR1MmsIFlqGwjT6f5+r+DEoyBz3pM6eHRcNmpYvHsZDIN1+ZrNhbntlZknGU0xzM/5w== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20260707 header.b=h4S2qj3Z; arc=none smtp.remote-ip=74.125.82.178 Received: from mail-dy1-f178.google.com (mail-dy1-f178.google.com [74.125.82.178]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 88708606A33A for ; Wed, 4 Nov 2026 16:57:11 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org 88708606A33A Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key, unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20260707 header.b=h4S2qj3Z Received: by mail-dy1-f178.google.com with SMTP id 5a478bee46e88-36c9a93a1abso855602eec.1 for ; Wed, 04 Nov 2026 08:57:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20260707; t=1793811431; x=1794416231; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=tXppOOg9gP9zhrC6rnkPUZoXeQTDUJQYOVYW2OTPzPI=; b=h4S2qj3Zw5mQsW0vUwapAB+pXGLcN8QJxvJq2jtKV39mp1Un3Bt/uQnthNho6H6T8L jVe25KmCUbTodqm3XKYbmR9sDEPANyP8yYf0bXQIIlRliFQ6QuSi/aqA0vM+htGngKio YlOFXqUGkMy/9ufjU7sonb51VeJRcZgWc9Sp8h8qaOvt3PcjRsWIHqgUwIJKZMllb96b QiIp1Dh0FkwAeuylqmsEwRMvnH37XX0B0G5mIv+Z91y4aD6WE4MiVEiXINhkPGnMjDbQ hWKsKfBmN5TOyVIlGQgSKearP35ODPiCHcvVC9fCcN4SFtryJX446kPf0shs9VayZYek uJ8w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1793811431; x=1794416231; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to:content-type; bh=tXppOOg9gP9zhrC6rnkPUZoXeQTDUJQYOVYW2OTPzPI=; b=vAJKcYefLrff5PdZMobLmlp7GRd8GZakL2K7StnbDmgtL0IB40M4fCD2dZACtDr3mk OlcZZoxhvnTLmTtzHkEnvQ8Ik5GqFIvlxYty6o8zaDWOVcGgZirQ1DAtIQq/6IgbuuSx gfzt7W4OPHzIg7ZwYWO1xBoN5utTsRYxIuY/PgPm9bi4U11vavcCKkAuF9ycixxzU7s9 Ft1MEbQWO0d95T+Rij44ZdxeT8nyBb39NzmS5B5NJLJGh9nUwK/tI5pNHKa0kO/1ewZ7 ku2u5HgCPWh3HRk03kYfSsv2+2NV20W6PIvb0wQP8nm1azEpOebk/TSAHaTNz6IGP5EY znzQ== X-Forwarded-Encrypted: i=1; AKwUvBzjwcd72TLOjkONrzFU6oo/xtmnCUndizQImRr3nUI2pMSBNO47rK8gxBoEyGOVaGQCpDzmpeUM+bE=@vger.kernel.org X-Gm-Message-State: APuU4Z8JmGQaBj0smOinNe8KCkqPk3pTknoasPubnBHdiAPyhCZsGGSs Spv9sN29A+NjeIRrTAt99QR0OCmAeJIPGAfRlnNAHxxqrkJPphhd+wh/TkvsUc2NaysEvQ== X-Gm-Gg: AYBFou1fimN+i9etHgQtt+fNryR9TrLTxI1hVLjAxRTPIyAnnOuE8Rtb8CYVSSsfWcm 0dhjjUYNcdxS4ddbPfxjgNluOghlJzABg/QVFhD/yl9+UKBIJqJQUZJ0scGROGEqt6j3pTNbEhT TA1o+71QiTmWe1g8Ms1x56ZklmqolY2p2qsBvVdIipsd3xJCNRnSHrnBF0kpT8Rme2AwziA/y/B /up5/SXqqL8vhftTluhtR6MYLKtm+NW23ueaI7tICnUYh3ukdPXWyMaSbRr66WXwfe5Bhnj+tZP RzMsHsWoDt9gwOotiKMOcPKfDgef+mQlMunyRjzHm6r7/g0nSQx5p7S4vUVGDyuuwLm2YIhVr6m zD9Jxlm0SZCAAHKF/8jDyplEpKrqoW1Zc6jvhs0V5ipBk5FYd24xj7lZXSFU2OD8PsWM3pSyP1m E+Hkvj7op+7okhlzU5LZZCgTy2ISDTS5IQX8SZ91cEmpvlCy3G5i7yRDdh4kI/vKEkJ7XdXw2uq l/2ag8Q3S2cVp9thQvUIFYzj7H9uRoL7F8VZJrZGzp2XCg3rmoV+G0OEqJbmbXewu08Mxt6wu2K DHvGLkIiiLUtGx1EB8j82jtF017ygETCOXt9SjE= X-Received: by 2002:a05:7301:b82:b0:36a:2f6c:490e with SMTP id 5a478bee46e88-36de5f700bbmr85786eec.6.1793811430093; Wed, 04 Nov 2026 08:57:10 -0800 (PST) Received: from kernel.. ([216.195.201.23]) by smtp.gmail.com with ESMTPSA id 5a478bee46e88-36ca38d46fcsm9019567eec.13.2026.11.04.08.57.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 04 Nov 2026 08:57:09 -0800 (PST) From: Kunwu Chan To: paulmck@kernel.org, boqun@kernel.org, mathieu.desnoyers@efficios.com, jiangshanlai@gmail.com, corbet@lwn.net, mingo@redhat.com, frederic@kernel.org, neeraj.upadhyay@kernel.org, josh@joshtriplett.org, urezki@gmail.com, dave@stgolabs.net Cc: stern@rowland.harvard.edu, parri.andrea@gmail.com, will@kernel.org, dhowells@redhat.com, j.alglave@ucl.ac.uk, luc.maranget@inria.fr, akiyks@gmail.com, dlustig@nvidia.com, joelagnelf@nvidia.com, skhan@linuxfoundation.org, rdunlap@infradead.org, longman@redhat.com, rostedt@goodmis.org, qiang.zhang@linux.dev, kunwu.chan@gmail.com, brads@mainlining.org, linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org, lkmm@lists.linux.dev, linux-doc@vger.kernel.org, rcu@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: [PATCH 12/28] hazptr: Remove per-waiter scan fallback, simplify synchronize Date: Thu, 5 Nov 2026 00:54:30 +0800 Message-ID: <20261104165504.2430480-13-kunwu.chan@gmail.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20261104165504.2430480-1-kunwu.chan@gmail.com> References: <20261104165504.2430480-1-kunwu.chan@gmail.com> X-Mailing-List: linux-doc@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Transfer-Encoding: 8bit With try_acquire, per-CPU slots publish their target address directly (no wildcard transient), so a single Bloom-walk pass suffices. Drop the per-waiter exact-match fallback that busy-waited on remote slots; waiters whose address is in the Bloom filter wait for the next scan cycle. Extend hazptr_scan_walk() with an optional @watch parameter for exact-match lookups (used by the upcoming stall detector). Signed-off-by: Kunwu Chan --- kernel/hazptr.c | 104 +++++++++++++++++++++++++++--------------------- 1 file changed, 58 insertions(+), 46 deletions(-) diff --git a/kernel/hazptr.c b/kernel/hazptr.c index 059c356ceaa7..4784df78be4e 100644 --- a/kernel/hazptr.c +++ b/kernel/hazptr.c @@ -39,10 +39,6 @@ struct hazptr_overflow_list { * successively iterates on both lists. Therefore, only list removals * can cause the iteration to retry, and the number of removals is * limited to the number of list elements. - * - * Due to the overflow list raw spin lock, the hazard pointer readers are - * blocking, starvation-free with bounded waiting, assuming bounded critical - * sections and no NMI or virtualization-induced holder preemption. */ struct hazptr_overflow_list_flip { struct hazptr_overflow_list array[2]; @@ -153,12 +149,12 @@ void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p) EXPORT_SYMBOL_GPL(__hazptr_acquire); /* - * Perform piecewise iteration on overflow list waiting until "addr" and - * wildcard are not present. Raw spinlock is released and taken between each - * list item and busy loop iteration. The overflow list generation is checked - * each time the lock is taken to validate that the list has not changed before - * resuming iteration or busy wait. If the generation has changed, retry the - * entire list traversal. + * Perform piecewise iteration on overflow list waiting until "addr" is + * not present. Raw spinlock is released and taken between each list + * item and busy loop iteration. The overflow list generation is checked + * each time the lock is taken to validate that the list has not changed + * before resuming iteration or busy wait. If the generation has + * changed, retry the entire list traversal. */ static void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list, void *addr) @@ -228,8 +224,8 @@ void hazptr_scan_cpu_slots(void *addr) } } -static -void hazptr_scan_overflow_list_period(void *addr, unsigned int scan_idx) +static void __maybe_unused +hazptr_scan_overflow_list_period(void *addr, unsigned int scan_idx) { int cpu; @@ -310,15 +306,28 @@ static bool hazptr_bloom_contains(const struct hazptr_bloom *bloom, void *addr) } /* - * Walk all slots and record observed non-wildcard addresses into - * the Bloom filter. A single pass suffices on the try_acquire - * fast path (readers publish their target directly). + * Walk all slots and return true if @watch (non-NULL) is present. + * If @bloom is non-NULL, record observed non-wildcard addresses in it. + * A NULL @watch means pure collection mode: never early-returns on a + * match. + * + * A wildcard in an overflow-list slot means a slow-path acquire is in + * flight: that slot may resolve to any address (including @watch or a + * Bloom-collected one) after the walk. To keep the single-pass + * completion decision safe, the caller must observe wildcards and + * defer completion decisions for one cycle; @wildcard (if non-NULL) + * is set to true in that case. In watch mode, a wildcard also counts + * as "present" so exact-match callers do not complete. */ -static void hazptr_scan_walk(struct hazptr_bloom *bloom) +static bool hazptr_scan_walk(void *watch, struct hazptr_bloom *bloom, + bool *wildcard) { int cpu; - hazptr_bloom_reset(bloom); + if (bloom) + hazptr_bloom_reset(bloom); + if (wildcard) + *wildcard = false; for_each_possible_cpu(cpu) { struct hazptr_percpu_slots *percpu_slots = per_cpu_ptr(&hazptr_percpu_slots, cpu); @@ -329,8 +338,11 @@ static void hazptr_scan_walk(struct hazptr_bloom *bloom) struct hazptr_slot_item *item = &percpu_slots->items[idx]; void *v; + /* Pairs with smp_store_release in hazptr_release(). */ v = smp_load_acquire(&item->slot.addr); - if (v && !is_wildcard(v)) + if (watch && (v == watch || is_wildcard(v))) + return true; + if (bloom && v && !is_wildcard(v)) hazptr_bloom_add(bloom, v); } for (int i = 0; i < 2; i++) { @@ -342,16 +354,24 @@ static void hazptr_scan_walk(struct hazptr_bloom *bloom) hlist_for_each_entry(b, &list->head, overflow_node) { void *v; + /* Pairs with smp_store_release in hazptr_release(). */ v = smp_load_acquire(&b->slot.addr); - if (v && !is_wildcard(v)) + if (watch && (v == watch || is_wildcard(v))) { + raw_spin_unlock_irqrestore(&list->lock, flags); + return true; + } + if (bloom && v && !is_wildcard(v)) hazptr_bloom_add(bloom, v); + else if (v && is_wildcard(v) && wildcard) + *wildcard = true; } raw_spin_unlock_irqrestore(&list->lock, flags); } } + + return false; } -/* Need is_wildcard for the Bloom filter */ /* * Shared scan: batch concurrent hazptr_synchronize() callers into a * single kthread-driven scan, avoiding redundant per-CPU and @@ -416,28 +436,32 @@ static void hazptr_scan_do_cycle(void) } /* - * Walk all slots and record observed addresses into the + * Scan all slots: record observed addresses into the * Bloom filter, then complete waiters whose address is * not present. On the try_acquire fast path, readers * publish their target directly (no wildcard transient), - * so a single pass suffices. + * so a single pass suffices for per-CPU slots. */ - hazptr_scan_walk(&hazptr_scan.bloom); + { + bool wildcard; - list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) { - if (!hazptr_bloom_contains(&hazptr_scan.bloom, w->addr)) - list_move(&w->node, &done); + hazptr_scan_walk(NULL, &hazptr_scan.bloom, &wildcard); + /* + * A wildcard in an overflow-list slot is a slow-path + * acquire in flight: that slot can resolve to any + * address after the walk, so defer completion + * decisions to the next cycle. + */ + if (!wildcard) + /* Complete waiters whose address is not in the filter. */ + list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) { + if (!hazptr_bloom_contains(&hazptr_scan.bloom, w->addr)) + list_move(&w->node, &done); + } } mutex_unlock(&hazptr_phase_lock); - /* Waiters still blocked: their address was observed present. */ - list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) { - hazptr_scan_cpu_slots(w->addr); - hazptr_scan_overflow_list_all(w->addr); - list_move(&w->node, &done); - } - list_for_each_entry_safe(w, n, &done, node) { list_del_init(&w->node); complete(&w->done); @@ -496,8 +520,6 @@ core_initcall(hazptr_scan_init); */ void hazptr_synchronize(void *addr) { - unsigned int scan_list_phase; - /* * Busy-wait should only be done from preemptible context. */ @@ -521,18 +543,8 @@ void hazptr_synchronize(void *addr) } guard(mutex)(&hazptr_phase_lock); - - /* Scan per-CPU slots. */ hazptr_scan_cpu_slots(addr); - - /* - * Scan overflow lists *after* scanning per-CPU slots. See - * hazptr_promote_to_backup_slot() for scan ordering requirement. - */ - scan_list_phase = flip_list_phase(hazptr_overflow_list_phase); - hazptr_scan_overflow_list_period(addr, scan_list_phase); - WRITE_ONCE(hazptr_overflow_list_phase, scan_list_phase); /* Flip the current list phase. */ - hazptr_scan_overflow_list_period(addr, flip_list_phase(scan_list_phase)); + hazptr_scan_overflow_list_all(addr); } EXPORT_SYMBOL_GPL(hazptr_synchronize); -- 2.43.0