From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=74.125.82.179 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1793811340; b=dMiqNNE9F2Og3kzeKl5vqBn5z46wD2xWQJVN3xiom1BfUDzCWwOyD8d5PhkMjNYa7+SE uZAd/p0zhEk0lMruS1It7emz+HofQvY0UBHrqIajnshLYK4r+th0dCDBqmdVVFjOYcnWa Y57yic73xDyrBmNA+rA7ob1ZE00jDPlB8XNle8HXpTMPnxgmeocvTUDN5I9Cjwn+7+x6Q ViDPtqkJa104K4VrHy5Rp9eGrm5/WKPvXfx1OcKmf6bTD/K9i8tJm6/wFrJHzV7q7nwRz h3nCQSetecQp3nvzrW1cox8HZAk7NpbI5gBpQZ6ANpTTUHjikc3CyCIl8KH8PJEBgWg== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1793811340; 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=GfiEJ9ZFFgFLvm1lz7uB9aBGd1QKPWSUh66STtJdHAI=; b=kCZTMMvtx6b9TcvcrtRPQpNhDjc7zOKSuLvzpY3vbdq4cGjVRUqQDRL3DzROpMYsT/Ug 7gAS9MQ8MZCLkDXqiE1sna8qeDzjb8AN/kTwuHfet0chwNecDVgm7YwZ6hZfiP2KQT6Dz SVL3lE4xTlSe4XDBOlo8DBIPjRIk4FwxcnHBSB8aFqqn4UkN7SSMfp9c50L8aDpjO8YId O7qkmiL9/Pnl+3fZ9WYylDRpGcGO77fvvu4AyQqFHQX7aduBE/XyX7DlAzhfNhlqCR5fJ QBSMxnbzrHCT/HinpJPZG5WwLN7PnuEBXf1fvulqY2LYoUasXYY5GuT/aP3CPdCFAaw== 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=Xf8O32Ua; arc=none smtp.remote-ip=74.125.82.179 Received: from mail-dy1-f179.google.com (mail-dy1-f179.google.com [74.125.82.179]) (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 08E08606A328 for ; Wed, 4 Nov 2026 16:55:39 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org 08E08606A328 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=Xf8O32Ua Received: by mail-dy1-f179.google.com with SMTP id 5a478bee46e88-35c76e9614aso1205075eec.0 for ; Wed, 04 Nov 2026 08:55:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20260707; t=1793811339; x=1794416139; 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=GfiEJ9ZFFgFLvm1lz7uB9aBGd1QKPWSUh66STtJdHAI=; b=Xf8O32Ua/K8LxgJ7sbXqPBXwHkdxv+vRskincGO6vQ8zK5h53QtNjUPd8nry9ho1vA mq3AQCf2j1Maalwu9nkipJdcNSPBYC2HFJb/NFANPgqiJizNEjsATBqouJtGp6zEIQYf 7utJvj219RiRm8VRVUOSFJ8ZGEL4Ogl3NHLkKzfqtwlbzhI0HAX9qz4snpqtOquj/B2w i1Gu/j4GQC7q4v0kPmLiZfC9weAuK+JEDz1HAY8QW1Z3Nptb6wZdfjd+/eOm8tqXO7qq oALi8+Ui0UkS1BmtB4upr9haqFcHba+mcLaJ8w7DFFDmc2nOpogToR5/72TEAU7M7e0d fa5g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1793811339; x=1794416139; 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=GfiEJ9ZFFgFLvm1lz7uB9aBGd1QKPWSUh66STtJdHAI=; b=NnBcg3UM77Rsp3Awao8qEQo7nW9uTm7uSgW20AL07CaQArUYpbD49n69YG8NgCZwRd Qq2tP8r5Ipv34vs3dUTibHKHWh107t69xwk9HvEG660fWDZUjs05qLDgqOUVFNdMN9YI ZYAg4MP7swaqLuQopkfajwhmp3m6qraOT9Z8zTcpM3sCeiUXClZc2TO2rQm52XJpHmNK b611Hw97j84HbaiP+/fw7dVYGh0NstN9aJdTROP2JlIPTFFlmdtbccySK2UxsZscdK82 Eikxhg5lIKB17uq/XImUfqPEVXibV0ZzsTZQbqrKYwDpKTALOIgt9ecIZ9ZV2yFU/A0p 1cWw== X-Forwarded-Encrypted: i=1; AKwUvBzb4U6P+oaUP7CycZ6PJhy3uYzyARMc6TMbiLCKQjFxqn1VkpoKBaaMXlC6yVETDSW0TgaGWF9QvxG+OfQ=@vger.kernel.org X-Gm-Message-State: APuU4Z+wyUBpzoomY+STZp63hwMMzSjtzx69E5khNkq8L1D2K63EYru+ bzKIDRI0SmvxyjYNviRmL3cNKv0O7Me55bgfSIyHjXcEMKfpdvEymYF5 X-Gm-Gg: AYBFou2rPsi4BV48mQPDBaeiGVsgCdqOWKKbn63jv3F10u9qfXxqxQxBDEagCTSzB6J lshp5eIiBlqx4q7tfDoEpq6y4KT33ZB68n0dTDgajVNiNTzpJQ483PDqmC1d6qFWaAqMGvjraHe 8mfPB+VekvRo24dZqT9rme/1I9uVvON2uE6d07NhbMQ7tt5FSOgDytp+RiNZZugDKKDYDD64SY2 m+uXPrWMhBSFtdJnXH67rIyTembTg4nRGh5bUECLnxOAUYbpzYe6Y1yBLCMnHf6wBeghnBSsOry ec/bRJ+WXmvSWjD/FwOSGA7g5THcSUx/Nu1hb1TQA3wiYATfn726ugus97OpfyNZ3e1GtLnM3ty /6NV7Y96/GFfLn3I+xKTzyq6bsCy1U3nAROtTSPPXfaBgKqzJtgmtwWmCvfWOJ45yAB9WrDL7Ac JvP5zs1lqI3XcM/M7Q+9QUsagnCXAteRb38sK9t+MHFtQeBg8JCqkmH+VkoEvzSBsAC8CSC05r+ vKlC4vev9IEUSaKAmhV9btYMVXvymiXKzmtLVLVlw5Yy8ybZ5BZTduo8PDMgdjK+P1ki9SHTBa/ b9syYcMDYrvTGl01cwfgIhh+H1QR32bIdxwGFUc= X-Received: by 2002:a05:7300:dd42:b0:36a:7c69:3f83 with SMTP id 5a478bee46e88-36c8d2540fcmr6653140eec.3.1793811338443; Wed, 04 Nov 2026 08:55:38 -0800 (PST) Received: from kernel.. ([216.195.201.23]) by smtp.gmail.com with ESMTPSA id 5a478bee46e88-36ca38d46fcsm9019567eec.13.2026.11.04.08.55.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 04 Nov 2026 08:55:37 -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 02/28] hazptr: Use Bloom filter for shared scan waiters Date: Thu, 5 Nov 2026 00:54:20 +0800 Message-ID: <20261104165504.2430480-3-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-kernel@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 Replace the per-waiter sequential scan with a shared Bloom filter built during a single walk: each observed non-wildcard address sets three bits. A waiter whose address hashes to an unset bit can be completed without another slot walk. A Bloom filter has no false negatives, so an address absent from the scan cannot be held by an observed slot; false positives only delay completion to a later scan cycle. The filter uses a one-page bitmap with three multiply-shift hash functions. It lives in the hazptr_scan_state and is only touched by the scan kthread. Suggested-by: Boqun Feng Signed-off-by: Kunwu Chan Suggested-by: Mathieu Desnoyers Acked-by: Bradley Morgan --- kernel/hazptr.c | 122 +++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 116 insertions(+), 6 deletions(-) diff --git a/kernel/hazptr.c b/kernel/hazptr.c index 013c24021c43..059c356ceaa7 100644 --- a/kernel/hazptr.c +++ b/kernel/hazptr.c @@ -16,6 +16,8 @@ #include #include #include +#include +#include #define HAZPTR_WILDCARD ((void *) 1UL) @@ -57,6 +59,12 @@ unsigned int flip_list_phase(unsigned int phase) return 1 - phase; } +static +bool is_wildcard(void *addr) +{ + return (unsigned long)addr == (unsigned long)HAZPTR_WILDCARD; +} + static struct hazptr_slot_item *hazptr_get_free_percpu_slot_item(void) { @@ -252,6 +260,98 @@ static void hazptr_scan_overflow_list_all(void *addr) } } +/* Number of hash functions for the Bloom filter. */ +#define HAZPTR_BLOOM_HASHES 3 + +/* Number of bits in the Bloom filter bitmap: one page. */ +#define HAZPTR_BLOOM_NBITS (PAGE_SIZE * 8) + +struct hazptr_bloom { + unsigned long map[PAGE_SIZE / sizeof(unsigned long)]; +}; + +/* + * Multiply @addr by a per-hash odd constant and use the high bits + * as the Bloom filter index. + */ +static unsigned long hazptr_bloom_hash(void *addr, unsigned int i) +{ + static const u64 mult[HAZPTR_BLOOM_HASHES] = { + 0x9E3779B97F4A7C15ULL, + 0xC2B2AE3D27D4EB4FULL, + 0x165667B19E3779F9ULL, + }; + u64 hash = (u64)(unsigned long)addr * mult[i]; + + return hash >> (64 - ilog2(HAZPTR_BLOOM_NBITS)); +} + +static void hazptr_bloom_reset(struct hazptr_bloom *bloom) +{ + bitmap_zero(bloom->map, HAZPTR_BLOOM_NBITS); +} + +static void hazptr_bloom_add(struct hazptr_bloom *bloom, void *addr) +{ + unsigned int i; + + for (i = 0; i < HAZPTR_BLOOM_HASHES; i++) + __set_bit(hazptr_bloom_hash(addr, i), bloom->map); +} + +static bool hazptr_bloom_contains(const struct hazptr_bloom *bloom, void *addr) +{ + unsigned int i; + + for (i = 0; i < HAZPTR_BLOOM_HASHES; i++) + if (!test_bit(hazptr_bloom_hash(addr, i), bloom->map)) + return false; + return true; +} + +/* + * 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). + */ +static void hazptr_scan_walk(struct hazptr_bloom *bloom) +{ + int cpu; + + hazptr_bloom_reset(bloom); + + for_each_possible_cpu(cpu) { + struct hazptr_percpu_slots *percpu_slots = per_cpu_ptr(&hazptr_percpu_slots, cpu); + struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu); + unsigned int idx; + + for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) { + struct hazptr_slot_item *item = &percpu_slots->items[idx]; + void *v; + + v = smp_load_acquire(&item->slot.addr); + if (v && !is_wildcard(v)) + hazptr_bloom_add(bloom, v); + } + for (int i = 0; i < 2; i++) { + struct hazptr_overflow_list *list = &overflow_list_flip->array[i]; + struct hazptr_backup_slot *b; + unsigned long flags; + + raw_spin_lock_irqsave(&list->lock, flags); + hlist_for_each_entry(b, &list->head, overflow_node) { + void *v; + + v = smp_load_acquire(&b->slot.addr); + if (v && !is_wildcard(v)) + hazptr_bloom_add(bloom, v); + } + raw_spin_unlock_irqrestore(&list->lock, flags); + } + } +} + +/* 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 @@ -272,6 +372,7 @@ struct hazptr_scan_state { struct mutex lock; struct list_head pending; struct list_head scanning; /* kthread only */ + struct hazptr_bloom bloom; /* kthread only */ }; static struct hazptr_scan_state hazptr_scan; @@ -315,19 +416,28 @@ static void hazptr_scan_do_cycle(void) } /* - * Process each waiter: scan per-CPU slots and overflow lists - * until the waiter's address is released. This is the same - * scan the direct fallback performs, delegated to a kthread so - * callers sleep instead of busy-waiting. + * Walk all slots and 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. */ + hazptr_scan_walk(&hazptr_scan.bloom); + + 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); } - mutex_unlock(&hazptr_phase_lock); - list_for_each_entry_safe(w, n, &done, node) { list_del_init(&w->node); complete(&w->done); -- 2.43.0