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

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

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

[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

[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