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

[Joel Fernandes <joelagnelf@nvidia.com>]

> 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