Re: [PATCH RFC v3 02/15] hazptr: use Bloom filter for shared scan waiters

Re: [PATCH RFC v3 02/15] hazptr: use Bloom filter for shared scan waiters

[Joel Fernandes]

> On Oct 9, 2026, at 11:07 PM, KunWu Chan <kunwu.chan@gmail.com> wrote:
> 
> On Tue, Oct 6, 2026 at 1:51 PM Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
>> 
>>> On 2026-10-05 13:15, Kunwu Chan wrote:
>>> Replace the per-waiter exact-match scan with a shared Bloom filter
>>> built during the second drain pass: each observed non-wildcard
>>> address sets three bits, so 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 final drain 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, so waiter state remains on the caller's stack
>>> and no dynamic allocation is needed.
>>> 
>>> Suggested-by: Boqun Feng <boqun@kernel.org>
>> 
>> I actually suggested that to Boqun in the first place. Feel
>> free to add my suggested-by tag as well. :)
>> 
>> Did you run your Bloom filter in a test program on the side to
>> see how it behaves with pointers, and confirm that the false
>> positive rate is not too high due to hashing algorithm/constants
>> concerns ?
>> 
> 
> Hi Mathieu,
> 
> I ran a standalone test using the hash functions and
> constants from
> the patch, with random,
> page-aligned, cacheline-aligned, sequential, and two synthetic
> kernel-like address patterns.

kernel-like? Linux or CUDA? I have to say I find AI generated messages hard to read.

> 
> With 768 inserted addresses, the measured false-positive rates were
> 0.025%–0.034% across
> these patterns, compared with an ideal Bloom-filter estimate of about
> 0.031%. I also tested larger
> insertion counts as stress cases. The results were consistent across
> three seeds,
> with only minor variation for the random distribution.

Why is the distribution random?

> 
> These are synthetic address distributions rather than measurements
> from actual kernel waiter
> addresses, but they provide an initial check of the hash functions
> against several structured
> address patterns.

Why not just provide the test code? Oh, but your AI  crutches did not ask you to do that.

Joel



> 
> Thanks,
> Kunwu
> 
>> Thanks!
>> 
>> Mathieu
>> 
>>> Signed-off-by: Kunwu Chan <kunwu.chan@gmail.com>
>>> ---
>>>  kernel/hazptr.c | 93 +++++++++++++++++++++++++++++++++++++++++++------
>>>  1 file changed, 83 insertions(+), 10 deletions(-)
>>> 
>>> diff --git a/kernel/hazptr.c b/kernel/hazptr.c
>>> index 9e274a691af5..900ba35de2cb 100644
>>> --- a/kernel/hazptr.c
>>> +++ b/kernel/hazptr.c
>>> @@ -7,6 +7,7 @@
>>>   */
>>> 
>>>  #include <linux/hazptr.h>
>>> +#include <linux/bitops.h>
>>>  #include <linux/percpu.h>
>>>  #include <linux/spinlock.h>
>>>  #include <linux/mutex.h>
>>> @@ -16,6 +17,7 @@
>>>  #include <linux/kthread.h>
>>>  #include <linux/swait.h>
>>>  #include <linux/sched.h>
>>> +#include <linux/bitmap.h>
>>> 
>>>  /*
>>>   * The current hazard pointer wildcard. Flips between 1UL and 2UL to guarantee
>>> @@ -213,6 +215,55 @@ void hazptr_scan_period(void *addr, void *scan_wildcard)
>>>      }
>>>  }
>>> 
>>> +/* 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;
>>> +}
>>> +
>>>  struct hazptr_waiter {
>>>      struct list_head node;
>>>      void *addr;
>>> @@ -226,17 +277,26 @@ 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;
>>> 
>>>  /*
>>> - * Check per-CPU slots before overflow-list slots to match the
>>> - * acquisition ordering of promoted slots.
>>> + * Walk all slots and return true if @watch is present.  If @bloom
>>> + * is non-NULL, record observed non-wildcard addresses in it.
>>> + *
>>> + * Per-CPU slots are examined before overflow-list slots on each CPU
>>> + * to preserve the acquisition ordering required by the promote path:
>>> + * synchronize must observe the per-CPU slot release before the
>>> + * overflow-list entry can be missed.
>>>   */
>>> -static bool hazptr_value_present(void *val)
>>> +static bool hazptr_scan_walk(void *watch, struct hazptr_bloom *bloom)
>>>  {
>>>      int cpu;
>>> 
>>> +     if (bloom)
>>> +             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);
>>> @@ -244,10 +304,14 @@ static bool hazptr_value_present(void *val)
>>> 
>>>              for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
>>>                      struct hazptr_slot_item *item = &percpu_slots->items[idx];
>>> +                     void *v;
>>> 
>>>                      /* Pairs with smp_store_release in hazptr_release(). */
>>> -                     if (smp_load_acquire(&item->slot.addr) == val)
>>> +                     v = smp_load_acquire(&item->slot.addr);
>>> +                     if (v == watch)
>>>                              return true;
>>> +                     if (bloom && 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];
>>> @@ -256,11 +320,16 @@ static bool hazptr_value_present(void *val)
>>> 
>>>                      raw_spin_lock_irqsave(&list->lock, flags);
>>>                      hlist_for_each_entry(b, &list->head, overflow_node) {
>>> +                             void *v;
>>> +
>>>                              /* Pairs with smp_store_release in hazptr_release(). */
>>> -                             if (smp_load_acquire(&b->slot.addr) == val) {
>>> +                             v = smp_load_acquire(&b->slot.addr);
>>> +                             if (v == watch) {
>>>                                      raw_spin_unlock_irqrestore(&list->lock, flags);
>>>                                      return true;
>>>                              }
>>> +                             if (bloom && v && !is_wildcard(v))
>>> +                                     hazptr_bloom_add(bloom, v);
>>>                      }
>>>                      raw_spin_unlock_irqrestore(&list->lock, flags);
>>>              }
>>> @@ -276,7 +345,7 @@ static bool hazptr_value_present(void *val)
>>>   */
>>>  static void hazptr_drain_wildcard(void *wc)
>>>  {
>>> -     while (hazptr_value_present(wc))
>>> +     while (hazptr_scan_walk(wc, NULL))
>>>              cond_resched();
>>>  }
>>> 
>>> @@ -309,12 +378,16 @@ static void hazptr_scan_do_cycle(void)
>>>      WRITE_ONCE(hazptr_wildcard, scan_wildcard);
>>>      old_wildcard = flip_wildcard(scan_wildcard);
>>> 
>>> -     /* Pass 2: drain the old wildcard. */
>>> -     hazptr_drain_wildcard(old_wildcard);
>>> +     /*
>>> +      * Pass 2: drain the old wildcard while collecting observed
>>> +      * addresses into the Bloom filter.
>>> +      */
>>> +     while (hazptr_scan_walk(old_wildcard, &hazptr_scan.bloom))
>>> +             cond_resched();
>>> 
>>> -     /* Complete waiters whose address is no longer held by any slot. */
>>> +     /* Complete waiters whose address is not in the filter. */
>>>      list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) {
>>> -             if (!hazptr_value_present(w->addr))
>>> +             if (!hazptr_bloom_contains(&hazptr_scan.bloom, w->addr))
>>>                      list_move(&w->node, &done);
>>>      }
>>> 
>> 
>> 
>> --
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> https://www.efficios.com

[PATCH RFC v3 00/15] hazptr: batch synchronize operations through a shared scan

[Kunwu Chan]

This series extends Mathieu Desnoyers's hazard pointer implementation [1]
with a shared scan path for concurrent hazptr_synchronize() callers,
and adapts the lockdep dynamic-key hashlist use case from Boqun
Feng's 2025 shazptr series [2] to the current hazptr API.

The series also adds rcuscale support, torture coverage, and litmus
tests for the hazptr implementation.

The lockdep conversion replaces the expedited RCU wait in
lockdep_unregister_key() with hazptr_synchronize().  This limits
the wait to hazard pointers protecting the target hash bucket
instead of waiting for a system-wide expedited RCU grace period.

[1] https://lore.kernel.org/all/20260919000056.3132131-26-paulmck@kernel.org/
[2] https://lore.kernel.org/lkml/20250625031101.12555-1-boqun.feng@gmail.com/

Performance data
================

The measurements below were collected on an ARM64 KVM guest running
on an ARM64 server (96 vCPUs, 8 GB RAM), unless noted otherwise.
The kernel is based on Paul McKenney's -rcu tree "dev" branch at
commit d21906b0aa1e ("doc: Document additional RCU task-stall dump
information") with the full hazptr patch series applied.

CONFIG_PREEMPT=y, CONFIG_PREEMPT_RCU=y, CONFIG_NR_CPUS=256.
Configuration is saved alongside each result set.

Following Paul's suggestion, the reader-side refscale numbers are
reported separately for CONFIG_PROVE_LOCKING=n and
CONFIG_PROVE_LOCKING=y, since lockdep instrumentation significantly
affects the measured RCU and SRCU reader-side costs but has little
effect on the hazptr reader path in this setup.

Lockdep workload -- tc qdisc mq x100, CONFIG_PROVE_LOCKING=y,
96 background hazptr readers:

  function-call IPIs (100 tc qdisc operations):  183

For reference, insmod/rmmod x10 in the same setup generated 4930
function-call IPIs.

The lockdep_unregister_key() path is the motivating use case for
this series: it replaces a system-wide synchronize_rcu_expedited()
call with a hazptr_synchronize() scoped to the per-key hash bucket.

Writer-side effective per-GP time (rcuscale, nwriters=16, nreaders=0,
one run per CPU count; computed as total test duration divided by
the total number of grace periods across all writers):

                         hazptr      RCU         Tree SRCU
  CPUs                   per-GP      per-GP      per-GP
  -----------------------------------------------------------
   24                    498 us      863 us      632 us
   96                    493 us      865 us      599 us
  128                    493 us      873 us      789 us
  256                    500 us      1162 us     476 us

At 96 CPUs the measurements are from the comparison blocks in the
same guest boot (order: hazptr nw=16, hazptr nw=1, hazptr nw=16,
rcu nw=1, rcu nw=16, srcu nw=1, srcu nw=16).  The hazptr scalability
row uses the first hazptr nw=16 block, which is consistent with the
single per-CPU runs at 24, 128, and 256 CPUs.  RCU and Tree SRCU
use their standard implementations.

Hazptr effective per-GP time stays nearly constant from 24 to 256
CPUs, remaining within 493-500 us, consistent with the shared-scan
kthread amortising the scan across concurrent synchronize callers.
At 96 CPUs, the effective per-GP times are approximately 865 us for
RCU, 599 us for SRCU, and 493 us for hazptr with 16 concurrent
callers.

For comparison, the nwriters=1, nreaders=0 case measured about 19 us
per grace period in this run at 96 CPUs.

Reader-side overhead (refscale, nreaders=-1 for 75% of 96 online
CPUs, nruns=5, median of 5 runs per scale type):

  The lockdep=n and lockdep=y refscale numbers were collected in
  separate QEMU boots from kernels built from the same source tree
  with PROVE_LOCKING toggled.  The first hazptr block in each boot
  is used.  All 96 vCPUs were visible to the guest (CONFIG_NR_CPUS=256).

                   PROVE_LOCKING=n     PROVE_LOCKING=y
  hazptr           26.1 ns             25.6 ns
  RCU               5.0 ns            165.5 ns
  SRCU             38.8 ns            192.3 ns

Hazptr reader-side overhead is nearly unchanged with and without
CONFIG_PROVE_LOCKING in this setup, while RCU and SRCU show
substantially higher costs when lockdep is enabled.  This is why
the refscale results are reported separately for the two
configurations.

Hazptr torture regression (CONFIG_PROVE_LOCKING=y):
basic, lockdep+wq_churn, and SLOWPATH PASS at 96 CPUs;
CPU sweep (8/16/32/64/128/256) also PASS with no lockdep warnings.

Additional x86 server testing with Lian Wang is planned(maybe after
LPC).

Test reproducibility
---------------------

Across five refscale runs, the standard deviation was 0.16 ns for
hazptr and 0.12 ns for RCU with PROVE_LOCKING=n.  Rcuscale data
points are based on a single test run per CPU count, but each run
covers thousands of individual grace periods and the hazptr 
measurements remain within 493-500us across the tested CPU counts.
The lockdep workload measurement uses 100 tc qdisc operations in 
a single QEMU boot; repeated runs agree to within ~10 IPIs on 
this server.

Changes since v2
================

- v2: https://lore.kernel.org/all/20261002170847.3653663-1-kunwu.chan@gmail.com/

Only cover letter changes; no code changes since v2.

- Fixed attribution: the base hazptr implementation is Mathieu
  Desnoyers's work.

- Split the refscale reader-overhead table into separate
  PROVE_LOCKING=n and PROVE_LOCKING=y columns, following Paul's
  suggestion, so that the lockdep impact on RCU and SRCU fast
  paths is visible rather than folded into a single number.

- Replaced the rcuscale "per-writer latency" column with
  per-grace-period values.  The new metric (total test duration
  divided by total grace periods) is more directly interpretable
  when comparing 1-vs-16 concurrent synchronize callers.  The
  nw=16 comparison now uses the same rcuscale test block for
  hazptr, RCU, and SRCU at each CPU count.  The nw=1 baseline
  is provided for reference so that the reader can see the single-
  writer cost and the per-GP cost under 16 concurrent callers side
  by side.

- Added test-condition and reproducibility notes (kernel commit,
  PREEMPT model, visible CPU count, boot ordering, standard
  deviation, sample sizes).

- Removed the unreviewed srcua scale-type patch from this series;
  it will be posted separately.

Changes since RFC/WIP
=====================

- RFC/WIP: https://lore.kernel.org/all/20260922070950.4173245-1-kunwu.chan@gmail.com/

- Split the original 4-patch RFC/WIP into smaller commits covering
  shared scanning, correctness, API support, lockdep, scaling, and
  torture testing.

- Incorporated Boqun Feng's review feedback: use a Bloom filter to
  avoid per-waiter allocation, add scoped_guard() support, and add
  a debug option to force the hazptr acquire slow path.

- Fixed scan ordering around backup-slot promotion by scanning all
  per-CPU slots before the overflow lists, with a separate
  overflow-list phase.

- Simplified the scan cycle to flip first and drain only the old
  wildcard generation, with herd7-verified LKMM tests for both the
  in-flight and resolved publication cases.

- Extended rcuscale and hazptrtorture coverage, added a selftest
  script for the torture configurations, and fixed the
  hazptr_release() kernel-doc.


Kunwu Chan (15):
  hazptr: add shared scan kthread
  hazptr: use Bloom filter for shared scan waiters
  hazptr: scan all per-CPU slots before overflow lists
  hazptr: add scoped_guard() support
  hazptr: add debug option to force the acquire slow path
  hazptr: elide redundant first drain pass
  Documentation/litmus-tests: add hazptr wildcard-flip escape test
  locking/lockdep: use hazptr to wait for dynamic key lookups
  rcuscale: add hazptr scale type
  hazptr: fix kernel-doc of hazptr_release()
  Documentation/litmus-tests: add hazptr acquire-before-scan test
  hazptrtorture: add slowpath and lockdep scenarios
  hazptrtorture: add READERS4 and READERS0 torture configs
  hazptrtorture: add 128- and 256-CPU configs
  selftests/rcutorture: add hazptr torture test script

 Documentation/litmus-tests/README             |  13 +
 .../hazptr/hazptr-acquire-before-scan.litmus  |  45 +++
 .../hazptr/hazptr-wildcard-flip-escape.litmus |  46 +++
 include/linux/hazptr.h                        |  56 ++-
 kernel/hazptr.c                               | 336 +++++++++++++++++-
 kernel/locking/lockdep.c                      |  25 +-
 kernel/rcu/Kconfig.debug                      |  10 +
 kernel/rcu/hazptrtorture.c                    |  57 ++-
 kernel/rcu/rcuscale.c                         |  70 +++-
 .../selftests/rcutorture/bin/hazptr.sh        | 146 ++++++++
 .../rcutorture/configs/hazptr/CFLIST          |   6 +
 .../rcutorture/configs/hazptr/CPU128          |  16 +
 .../rcutorture/configs/hazptr/CPU128.boot     |   1 +
 .../rcutorture/configs/hazptr/CPU256          |  16 +
 .../rcutorture/configs/hazptr/CPU256.boot     |   1 +
 .../rcutorture/configs/hazptr/LOCKDEP         |  17 +
 .../rcutorture/configs/hazptr/LOCKDEP.boot    |   1 +
 .../rcutorture/configs/hazptr/READERS0        |  16 +
 .../rcutorture/configs/hazptr/READERS0.boot   |   2 +
 .../rcutorture/configs/hazptr/READERS4        |  16 +
 .../rcutorture/configs/hazptr/READERS4.boot   |   2 +
 .../rcutorture/configs/hazptr/SLOWPATH        |  16 +
 22 files changed, 881 insertions(+), 33 deletions(-)
 create mode 100644 Documentation/litmus-tests/hazptr/hazptr-acquire-before-scan.litmus
 create mode 100644 Documentation/litmus-tests/hazptr/hazptr-wildcard-flip-escape.litmus
 create mode 100755 tools/testing/selftests/rcutorture/bin/hazptr.sh
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/CPU128
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/CPU128.boot
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/CPU256
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/CPU256.boot
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/LOCKDEP
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/LOCKDEP.boot
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/READERS0
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/READERS0.boot
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/READERS4
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/READERS4.boot
 create mode 100644 tools/testing/selftests/rcutorture/configs/hazptr/SLOWPATH

base-commit: d21906b0aa1e9573cdb5e7acaca44966b9d1dcd2
-- 
2.43.0

[PATCH RFC v3 02/15] hazptr: use Bloom filter for shared scan waiters

[Kunwu Chan]

Replace the per-waiter exact-match scan with a shared Bloom filter
built during the second drain pass: each observed non-wildcard
address sets three bits, so 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 final drain 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, so waiter state remains on the caller's stack
and no dynamic allocation is needed.

Suggested-by: Boqun Feng <boqun@kernel.org>
Signed-off-by: Kunwu Chan <kunwu.chan@gmail.com>
---
 kernel/hazptr.c | 93 +++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 83 insertions(+), 10 deletions(-)

diff --git a/kernel/hazptr.c b/kernel/hazptr.c
index 9e274a691af5..900ba35de2cb 100644
--- a/kernel/hazptr.c
+++ b/kernel/hazptr.c
@@ -7,6 +7,7 @@
  */
 
 #include <linux/hazptr.h>
+#include <linux/bitops.h>
 #include <linux/percpu.h>
 #include <linux/spinlock.h>
 #include <linux/mutex.h>
@@ -16,6 +17,7 @@
 #include <linux/kthread.h>
 #include <linux/swait.h>
 #include <linux/sched.h>
+#include <linux/bitmap.h>
 
 /*
  * The current hazard pointer wildcard. Flips between 1UL and 2UL to guarantee
@@ -213,6 +215,55 @@ void hazptr_scan_period(void *addr, void *scan_wildcard)
 	}
 }
 
+/* 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;
+}
+
 struct hazptr_waiter {
 	struct list_head node;
 	void *addr;
@@ -226,17 +277,26 @@ 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;
 
 /*
- * Check per-CPU slots before overflow-list slots to match the
- * acquisition ordering of promoted slots.
+ * Walk all slots and return true if @watch is present.  If @bloom
+ * is non-NULL, record observed non-wildcard addresses in it.
+ *
+ * Per-CPU slots are examined before overflow-list slots on each CPU
+ * to preserve the acquisition ordering required by the promote path:
+ * synchronize must observe the per-CPU slot release before the
+ * overflow-list entry can be missed.
  */
-static bool hazptr_value_present(void *val)
+static bool hazptr_scan_walk(void *watch, struct hazptr_bloom *bloom)
 {
 	int cpu;
 
+	if (bloom)
+		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);
@@ -244,10 +304,14 @@ static bool hazptr_value_present(void *val)
 
 		for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
 			struct hazptr_slot_item *item = &percpu_slots->items[idx];
+			void *v;
 
 			/* Pairs with smp_store_release in hazptr_release(). */
-			if (smp_load_acquire(&item->slot.addr) == val)
+			v = smp_load_acquire(&item->slot.addr);
+			if (v == watch)
 				return true;
+			if (bloom && 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];
@@ -256,11 +320,16 @@ static bool hazptr_value_present(void *val)
 
 			raw_spin_lock_irqsave(&list->lock, flags);
 			hlist_for_each_entry(b, &list->head, overflow_node) {
+				void *v;
+
 				/* Pairs with smp_store_release in hazptr_release(). */
-				if (smp_load_acquire(&b->slot.addr) == val) {
+				v = smp_load_acquire(&b->slot.addr);
+				if (v == watch) {
 					raw_spin_unlock_irqrestore(&list->lock, flags);
 					return true;
 				}
+				if (bloom && v && !is_wildcard(v))
+					hazptr_bloom_add(bloom, v);
 			}
 			raw_spin_unlock_irqrestore(&list->lock, flags);
 		}
@@ -276,7 +345,7 @@ static bool hazptr_value_present(void *val)
  */
 static void hazptr_drain_wildcard(void *wc)
 {
-	while (hazptr_value_present(wc))
+	while (hazptr_scan_walk(wc, NULL))
 		cond_resched();
 }
 
@@ -309,12 +378,16 @@ static void hazptr_scan_do_cycle(void)
 	WRITE_ONCE(hazptr_wildcard, scan_wildcard);
 	old_wildcard = flip_wildcard(scan_wildcard);
 
-	/* Pass 2: drain the old wildcard. */
-	hazptr_drain_wildcard(old_wildcard);
+	/*
+	 * Pass 2: drain the old wildcard while collecting observed
+	 * addresses into the Bloom filter.
+	 */
+	while (hazptr_scan_walk(old_wildcard, &hazptr_scan.bloom))
+		cond_resched();
 
-	/* Complete waiters whose address is no longer held by any slot. */
+	/* Complete waiters whose address is not in the filter. */
 	list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) {
-		if (!hazptr_value_present(w->addr))
+		if (!hazptr_bloom_contains(&hazptr_scan.bloom, w->addr))
 			list_move(&w->node, &done);
 	}
 
-- 
2.43.0

Re: [PATCH RFC v3 02/15] hazptr: use Bloom filter for shared scan waiters

[Mathieu Desnoyers]

On 2026-10-05 13:15, Kunwu Chan wrote:
> Replace the per-waiter exact-match scan with a shared Bloom filter
> built during the second drain pass: each observed non-wildcard
> address sets three bits, so 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 final drain 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, so waiter state remains on the caller's stack
> and no dynamic allocation is needed.
> 
> Suggested-by: Boqun Feng <boqun@kernel.org>

I actually suggested that to Boqun in the first place. Feel
free to add my suggested-by tag as well. :)

Did you run your Bloom filter in a test program on the side to
see how it behaves with pointers, and confirm that the false
positive rate is not too high due to hashing algorithm/constants
concerns ?

Thanks!

Mathieu

> Signed-off-by: Kunwu Chan <kunwu.chan@gmail.com>
> ---
>   kernel/hazptr.c | 93 +++++++++++++++++++++++++++++++++++++++++++------
>   1 file changed, 83 insertions(+), 10 deletions(-)
> 
> diff --git a/kernel/hazptr.c b/kernel/hazptr.c
> index 9e274a691af5..900ba35de2cb 100644
> --- a/kernel/hazptr.c
> +++ b/kernel/hazptr.c
> @@ -7,6 +7,7 @@
>    */
>   
>   #include <linux/hazptr.h>
> +#include <linux/bitops.h>
>   #include <linux/percpu.h>
>   #include <linux/spinlock.h>
>   #include <linux/mutex.h>
> @@ -16,6 +17,7 @@
>   #include <linux/kthread.h>
>   #include <linux/swait.h>
>   #include <linux/sched.h>
> +#include <linux/bitmap.h>
>   
>   /*
>    * The current hazard pointer wildcard. Flips between 1UL and 2UL to guarantee
> @@ -213,6 +215,55 @@ void hazptr_scan_period(void *addr, void *scan_wildcard)
>   	}
>   }
>   
> +/* 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;
> +}
> +
>   struct hazptr_waiter {
>   	struct list_head node;
>   	void *addr;
> @@ -226,17 +277,26 @@ 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;
>   
>   /*
> - * Check per-CPU slots before overflow-list slots to match the
> - * acquisition ordering of promoted slots.
> + * Walk all slots and return true if @watch is present.  If @bloom
> + * is non-NULL, record observed non-wildcard addresses in it.
> + *
> + * Per-CPU slots are examined before overflow-list slots on each CPU
> + * to preserve the acquisition ordering required by the promote path:
> + * synchronize must observe the per-CPU slot release before the
> + * overflow-list entry can be missed.
>    */
> -static bool hazptr_value_present(void *val)
> +static bool hazptr_scan_walk(void *watch, struct hazptr_bloom *bloom)
>   {
>   	int cpu;
>   
> +	if (bloom)
> +		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);
> @@ -244,10 +304,14 @@ static bool hazptr_value_present(void *val)
>   
>   		for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
>   			struct hazptr_slot_item *item = &percpu_slots->items[idx];
> +			void *v;
>   
>   			/* Pairs with smp_store_release in hazptr_release(). */
> -			if (smp_load_acquire(&item->slot.addr) == val)
> +			v = smp_load_acquire(&item->slot.addr);
> +			if (v == watch)
>   				return true;
> +			if (bloom && 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];
> @@ -256,11 +320,16 @@ static bool hazptr_value_present(void *val)
>   
>   			raw_spin_lock_irqsave(&list->lock, flags);
>   			hlist_for_each_entry(b, &list->head, overflow_node) {
> +				void *v;
> +
>   				/* Pairs with smp_store_release in hazptr_release(). */
> -				if (smp_load_acquire(&b->slot.addr) == val) {
> +				v = smp_load_acquire(&b->slot.addr);
> +				if (v == watch) {
>   					raw_spin_unlock_irqrestore(&list->lock, flags);
>   					return true;
>   				}
> +				if (bloom && v && !is_wildcard(v))
> +					hazptr_bloom_add(bloom, v);
>   			}
>   			raw_spin_unlock_irqrestore(&list->lock, flags);
>   		}
> @@ -276,7 +345,7 @@ static bool hazptr_value_present(void *val)
>    */
>   static void hazptr_drain_wildcard(void *wc)
>   {
> -	while (hazptr_value_present(wc))
> +	while (hazptr_scan_walk(wc, NULL))
>   		cond_resched();
>   }
>   
> @@ -309,12 +378,16 @@ static void hazptr_scan_do_cycle(void)
>   	WRITE_ONCE(hazptr_wildcard, scan_wildcard);
>   	old_wildcard = flip_wildcard(scan_wildcard);
>   
> -	/* Pass 2: drain the old wildcard. */
> -	hazptr_drain_wildcard(old_wildcard);
> +	/*
> +	 * Pass 2: drain the old wildcard while collecting observed
> +	 * addresses into the Bloom filter.
> +	 */
> +	while (hazptr_scan_walk(old_wildcard, &hazptr_scan.bloom))
> +		cond_resched();
>   
> -	/* Complete waiters whose address is no longer held by any slot. */
> +	/* Complete waiters whose address is not in the filter. */
>   	list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) {
> -		if (!hazptr_value_present(w->addr))
> +		if (!hazptr_bloom_contains(&hazptr_scan.bloom, w->addr))
>   			list_move(&w->node, &done);
>   	}
>   


-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: [PATCH RFC v3 02/15] hazptr: use Bloom filter for shared scan waiters

[KunWu Chan]

On Tue, Oct 6, 2026 at 1:51 PM Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
>
> On 2026-10-05 13:15, Kunwu Chan wrote:
> > Replace the per-waiter exact-match scan with a shared Bloom filter
> > built during the second drain pass: each observed non-wildcard
> > address sets three bits, so 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 final drain 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, so waiter state remains on the caller's stack
> > and no dynamic allocation is needed.
> >
> > Suggested-by: Boqun Feng <boqun@kernel.org>
>
> I actually suggested that to Boqun in the first place. Feel
> free to add my suggested-by tag as well. :)
>

Thanks, Mathieu. I wasn't aware that you originally suggested the Bloom
filter idea to Boqun. I'll add your Suggested-by tag.

> Did you run your Bloom filter in a test program on the side to
> see how it behaves with pointers, and confirm that the false
> positive rate is not too high due to hashing algorithm/constants
> concerns ?
>

I haven't run a standalone Bloom filter test yet. I'll test the actual
hash functions
and constants from the patch with pointer-like and aligned address
distributions,
and measure the false-positive rate for representative numbers of
observed addresses.

The in-kernel tests currently pass, including hazptr.sh and rcuscale,
but I agree that
these don't directly characterize the Bloom filter's false-positive rate.
I'll add the standalone test results to the next version.

Thanks,
Kunwu

> Thanks!
>
> Mathieu
>
> > Signed-off-by: Kunwu Chan <kunwu.chan@gmail.com>
> > ---
> >   kernel/hazptr.c | 93 +++++++++++++++++++++++++++++++++++++++++++------
> >   1 file changed, 83 insertions(+), 10 deletions(-)
> >
> > diff --git a/kernel/hazptr.c b/kernel/hazptr.c
> > index 9e274a691af5..900ba35de2cb 100644
> > --- a/kernel/hazptr.c
> > +++ b/kernel/hazptr.c
> > @@ -7,6 +7,7 @@
> >    */
> >
> >   #include <linux/hazptr.h>
> > +#include <linux/bitops.h>
> >   #include <linux/percpu.h>
> >   #include <linux/spinlock.h>
> >   #include <linux/mutex.h>
> > @@ -16,6 +17,7 @@
> >   #include <linux/kthread.h>
> >   #include <linux/swait.h>
> >   #include <linux/sched.h>
> > +#include <linux/bitmap.h>
> >
> >   /*
> >    * The current hazard pointer wildcard. Flips between 1UL and 2UL to guarantee
> > @@ -213,6 +215,55 @@ void hazptr_scan_period(void *addr, void *scan_wildcard)
> >       }
> >   }
> >
> > +/* 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;
> > +}
> > +
> >   struct hazptr_waiter {
> >       struct list_head node;
> >       void *addr;
> > @@ -226,17 +277,26 @@ 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;
> >
> >   /*
> > - * Check per-CPU slots before overflow-list slots to match the
> > - * acquisition ordering of promoted slots.
> > + * Walk all slots and return true if @watch is present.  If @bloom
> > + * is non-NULL, record observed non-wildcard addresses in it.
> > + *
> > + * Per-CPU slots are examined before overflow-list slots on each CPU
> > + * to preserve the acquisition ordering required by the promote path:
> > + * synchronize must observe the per-CPU slot release before the
> > + * overflow-list entry can be missed.
> >    */
> > -static bool hazptr_value_present(void *val)
> > +static bool hazptr_scan_walk(void *watch, struct hazptr_bloom *bloom)
> >   {
> >       int cpu;
> >
> > +     if (bloom)
> > +             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);
> > @@ -244,10 +304,14 @@ static bool hazptr_value_present(void *val)
> >
> >               for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> >                       struct hazptr_slot_item *item = &percpu_slots->items[idx];
> > +                     void *v;
> >
> >                       /* Pairs with smp_store_release in hazptr_release(). */
> > -                     if (smp_load_acquire(&item->slot.addr) == val)
> > +                     v = smp_load_acquire(&item->slot.addr);
> > +                     if (v == watch)
> >                               return true;
> > +                     if (bloom && 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];
> > @@ -256,11 +320,16 @@ static bool hazptr_value_present(void *val)
> >
> >                       raw_spin_lock_irqsave(&list->lock, flags);
> >                       hlist_for_each_entry(b, &list->head, overflow_node) {
> > +                             void *v;
> > +
> >                               /* Pairs with smp_store_release in hazptr_release(). */
> > -                             if (smp_load_acquire(&b->slot.addr) == val) {
> > +                             v = smp_load_acquire(&b->slot.addr);
> > +                             if (v == watch) {
> >                                       raw_spin_unlock_irqrestore(&list->lock, flags);
> >                                       return true;
> >                               }
> > +                             if (bloom && v && !is_wildcard(v))
> > +                                     hazptr_bloom_add(bloom, v);
> >                       }
> >                       raw_spin_unlock_irqrestore(&list->lock, flags);
> >               }
> > @@ -276,7 +345,7 @@ static bool hazptr_value_present(void *val)
> >    */
> >   static void hazptr_drain_wildcard(void *wc)
> >   {
> > -     while (hazptr_value_present(wc))
> > +     while (hazptr_scan_walk(wc, NULL))
> >               cond_resched();
> >   }
> >
> > @@ -309,12 +378,16 @@ static void hazptr_scan_do_cycle(void)
> >       WRITE_ONCE(hazptr_wildcard, scan_wildcard);
> >       old_wildcard = flip_wildcard(scan_wildcard);
> >
> > -     /* Pass 2: drain the old wildcard. */
> > -     hazptr_drain_wildcard(old_wildcard);
> > +     /*
> > +      * Pass 2: drain the old wildcard while collecting observed
> > +      * addresses into the Bloom filter.
> > +      */
> > +     while (hazptr_scan_walk(old_wildcard, &hazptr_scan.bloom))
> > +             cond_resched();
> >
> > -     /* Complete waiters whose address is no longer held by any slot. */
> > +     /* Complete waiters whose address is not in the filter. */
> >       list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) {
> > -             if (!hazptr_value_present(w->addr))
> > +             if (!hazptr_bloom_contains(&hazptr_scan.bloom, w->addr))
> >                       list_move(&w->node, &done);
> >       }
> >
>
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com

Re: [PATCH RFC v3 02/15] hazptr: use Bloom filter for shared scan waiters

[KunWu Chan]

On Tue, Oct 6, 2026 at 1:51 PM Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
>
> On 2026-10-05 13:15, Kunwu Chan wrote:
> > Replace the per-waiter exact-match scan with a shared Bloom filter
> > built during the second drain pass: each observed non-wildcard
> > address sets three bits, so 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 final drain 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, so waiter state remains on the caller's stack
> > and no dynamic allocation is needed.
> >
> > Suggested-by: Boqun Feng <boqun@kernel.org>
>
> I actually suggested that to Boqun in the first place. Feel
> free to add my suggested-by tag as well. :)
>
> Did you run your Bloom filter in a test program on the side to
> see how it behaves with pointers, and confirm that the false
> positive rate is not too high due to hashing algorithm/constants
> concerns ?
>

Hi Mathieu,

I ran a standalone test using the hash functions and constants from
the patch, with random,
page-aligned, cacheline-aligned, sequential, and two synthetic
kernel-like address patterns.

With 768 inserted addresses, the measured false-positive rates were
0.025%–0.034% across
these patterns, compared with an ideal Bloom-filter estimate of about
0.031%. I also tested larger
 insertion counts as stress cases. The results were consistent across
three seeds,
with only minor variation for the random distribution.

These are synthetic address distributions rather than measurements
from actual kernel waiter
 addresses, but they provide an initial check of the hash functions
against several structured
address patterns.

Thanks,
Kunwu

> Thanks!
>
> Mathieu
>
> > Signed-off-by: Kunwu Chan <kunwu.chan@gmail.com>
> > ---
> >   kernel/hazptr.c | 93 +++++++++++++++++++++++++++++++++++++++++++------
> >   1 file changed, 83 insertions(+), 10 deletions(-)
> >
> > diff --git a/kernel/hazptr.c b/kernel/hazptr.c
> > index 9e274a691af5..900ba35de2cb 100644
> > --- a/kernel/hazptr.c
> > +++ b/kernel/hazptr.c
> > @@ -7,6 +7,7 @@
> >    */
> >
> >   #include <linux/hazptr.h>
> > +#include <linux/bitops.h>
> >   #include <linux/percpu.h>
> >   #include <linux/spinlock.h>
> >   #include <linux/mutex.h>
> > @@ -16,6 +17,7 @@
> >   #include <linux/kthread.h>
> >   #include <linux/swait.h>
> >   #include <linux/sched.h>
> > +#include <linux/bitmap.h>
> >
> >   /*
> >    * The current hazard pointer wildcard. Flips between 1UL and 2UL to guarantee
> > @@ -213,6 +215,55 @@ void hazptr_scan_period(void *addr, void *scan_wildcard)
> >       }
> >   }
> >
> > +/* 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;
> > +}
> > +
> >   struct hazptr_waiter {
> >       struct list_head node;
> >       void *addr;
> > @@ -226,17 +277,26 @@ 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;
> >
> >   /*
> > - * Check per-CPU slots before overflow-list slots to match the
> > - * acquisition ordering of promoted slots.
> > + * Walk all slots and return true if @watch is present.  If @bloom
> > + * is non-NULL, record observed non-wildcard addresses in it.
> > + *
> > + * Per-CPU slots are examined before overflow-list slots on each CPU
> > + * to preserve the acquisition ordering required by the promote path:
> > + * synchronize must observe the per-CPU slot release before the
> > + * overflow-list entry can be missed.
> >    */
> > -static bool hazptr_value_present(void *val)
> > +static bool hazptr_scan_walk(void *watch, struct hazptr_bloom *bloom)
> >   {
> >       int cpu;
> >
> > +     if (bloom)
> > +             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);
> > @@ -244,10 +304,14 @@ static bool hazptr_value_present(void *val)
> >
> >               for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> >                       struct hazptr_slot_item *item = &percpu_slots->items[idx];
> > +                     void *v;
> >
> >                       /* Pairs with smp_store_release in hazptr_release(). */
> > -                     if (smp_load_acquire(&item->slot.addr) == val)
> > +                     v = smp_load_acquire(&item->slot.addr);
> > +                     if (v == watch)
> >                               return true;
> > +                     if (bloom && 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];
> > @@ -256,11 +320,16 @@ static bool hazptr_value_present(void *val)
> >
> >                       raw_spin_lock_irqsave(&list->lock, flags);
> >                       hlist_for_each_entry(b, &list->head, overflow_node) {
> > +                             void *v;
> > +
> >                               /* Pairs with smp_store_release in hazptr_release(). */
> > -                             if (smp_load_acquire(&b->slot.addr) == val) {
> > +                             v = smp_load_acquire(&b->slot.addr);
> > +                             if (v == watch) {
> >                                       raw_spin_unlock_irqrestore(&list->lock, flags);
> >                                       return true;
> >                               }
> > +                             if (bloom && v && !is_wildcard(v))
> > +                                     hazptr_bloom_add(bloom, v);
> >                       }
> >                       raw_spin_unlock_irqrestore(&list->lock, flags);
> >               }
> > @@ -276,7 +345,7 @@ static bool hazptr_value_present(void *val)
> >    */
> >   static void hazptr_drain_wildcard(void *wc)
> >   {
> > -     while (hazptr_value_present(wc))
> > +     while (hazptr_scan_walk(wc, NULL))
> >               cond_resched();
> >   }
> >
> > @@ -309,12 +378,16 @@ static void hazptr_scan_do_cycle(void)
> >       WRITE_ONCE(hazptr_wildcard, scan_wildcard);
> >       old_wildcard = flip_wildcard(scan_wildcard);
> >
> > -     /* Pass 2: drain the old wildcard. */
> > -     hazptr_drain_wildcard(old_wildcard);
> > +     /*
> > +      * Pass 2: drain the old wildcard while collecting observed
> > +      * addresses into the Bloom filter.
> > +      */
> > +     while (hazptr_scan_walk(old_wildcard, &hazptr_scan.bloom))
> > +             cond_resched();
> >
> > -     /* Complete waiters whose address is no longer held by any slot. */
> > +     /* Complete waiters whose address is not in the filter. */
> >       list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) {
> > -             if (!hazptr_value_present(w->addr))
> > +             if (!hazptr_bloom_contains(&hazptr_scan.bloom, w->addr))
> >                       list_move(&w->node, &done);
> >       }
> >
>
>
> --
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com