On Tue, Oct 6, 2026 at 1:51 PM Mathieu Desnoyers <[email protected]> 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 <[email protected]> > > 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 <[email protected]> > > --- > > 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
