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

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

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