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. :) >
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 <[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
