On Tue, Sep 22, 2026 at 03:09:47PM +0800, Kunwu Chan wrote:
> Batch concurrent hazptr_synchronize() callers into a shared scan
> cycle, avoiding redundant scans of the per-CPU slots.
>
> Queue waiters to a kthread and let each scan cycle make one pass
> over all CPUs. Each waiter tracks per-CPU progress for both
> wildcard generations, allowing multiple waiters to share the same
> scan.
>
> Flip the wildcard before scanning. New acquires then use the new
> generation, so the old-generation mask makes forward progress even
> under a steady stream of readers. Waiters that remain blocked are
> retried after a short delay.
>
> Fall back to the existing direct two-phase scan if the scan kthread
> is unavailable or waiter state cannot be allocated.
>
> Signed-off-by: Kunwu Chan <[email protected]>
> ---
> kernel/hazptr.c | 274 ++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 274 insertions(+)
>
> diff --git a/kernel/hazptr.c b/kernel/hazptr.c
> index d3d1050d92cf..ce553a61b119 100644
> --- a/kernel/hazptr.c
> +++ b/kernel/hazptr.c
> @@ -12,6 +12,10 @@
> #include <linux/mutex.h>
> #include <linux/list.h>
> #include <linux/export.h>
> +#include <linux/completion.h>
> +#include <linux/kthread.h>
> +#include <linux/slab.h>
> +#include <linux/swait.h>
>
> /*
> * The current hazard pointer wildcard. Flips between 1UL and 2UL to
> guarantee
> @@ -209,12 +213,251 @@ void hazptr_scan_period(void *addr, void
> *scan_wildcard)
> }
> }
>
> +/*
> + * Batch hazptr_synchronize() callers through a shared scan kthread.
> + */
> +
> +struct hazptr_waiter {
> + struct list_head node;
> + void *addr;
> + struct completion done;
> + /*
> + * Per-wildcard-generation progress masks. A CPU bit is
> + * cleared when the scan observes neither @addr nor that
> + * generation's wildcard on the CPU.
> + */
> + unsigned long *cpu_mask; /* 2 * BITS_TO_LONGS(nr_cpu_ids) */
This would requires allocation during hazptr_synchronize() and I would
like to avoid that (it's going to introduce a "allocating memory to free
memory" case).
Mathieu brought up a useful data structure for the scan: A Bloom filter:
https://en.wikipedia.org/wiki/Bloom_filter
, which is basically a bitmap set + k hash functions. Let's say we have
a struct bloom_filter (you can still with a page as the bitmap and k=3)
and put it in hazptr_scan_state. Then the scan would become:
bloom_filter_clear(); // <- reset the bloom filer.
for_each_possible_cpu()
hlist_for_each_entry(b, &list->head, overflow_node) {
bloom_filter_set(*b->slot.addr);
// ^ add the hazptr_acquire() adress into the bloom filter
}
list_for_each_entry(w, &hazptr_scan.scanning, node) {
if (!bloom_filter_contains(w->addr)) {
list_move(&w->node, &done);
}
}
Of course, there are some additional handling or optimizaiton we can do
with the per-CPU slot and wildcard, but this is the idea. It also makes
a potential call_hazptr() work.
Willing to give it a try?
Regards,
Boqun
> +};
> +
> +/* Return waiter @w's progress mask for wildcard generation @gen. */
> +static unsigned long *hazptr_waiter_mask(struct hazptr_waiter *w, int gen)
> +{
> + return w->cpu_mask + gen * BITS_TO_LONGS(nr_cpu_ids);
> +}
> +
> +struct hazptr_scan_state {
> + struct task_struct *kthread;
> + struct swait_queue_head wq;
> + bool wakeup;
> + struct mutex lock;
> + struct list_head pending;
> + struct list_head scanning; /* kthread only */
> +};
> +static struct hazptr_scan_state hazptr_scan;
> +
> +/*
> + * Check a CPU's overflow lists. A backup slot can hold a wildcard
> + * because __hazptr_acquire() writes the wildcard to any slot,
> + * including backup slots from hazptr_chain_backup_slot().
> + *
> + * @addr: address the waiter is waiting on
> + * @old_wc: wildcard value of the pre-flip generation
> + * @new_wc: wildcard value of the post-flip generation
> + * @has_old: set if any overflow slot holds @old_wc
> + * @has_new: set if any overflow slot holds @new_wc
> + *
> + * Returns true if @addr is present.
> + */
> +static bool hazptr_ovf_list_blocked(int cpu, void *addr,
> + void *old_wc, void *new_wc,
> + bool *has_old, bool *has_new)
> +{
> + struct hazptr_overflow_list_flip *ovf =
> per_cpu_ptr(&percpu_overflow_list_flip, cpu);
> + bool found_addr = false;
> + int i;
> +
> + for (i = 0; i < 2; i++) {
> + struct hazptr_overflow_list *list = &ovf->array[i];
> + struct hazptr_backup_slot *b;
> + unsigned long flags;
> +
> + raw_spin_lock_irqsave(&list->lock, flags);
> + hlist_for_each_entry(b, &list->head, overflow_node) {
> + /* Pairs with smp_store_release in hazptr_release(). */
> + void *val = smp_load_acquire(&b->slot.addr);
> +
> + if (val == addr)
> + found_addr = true;
> + else if (val == old_wc)
> + *has_old = true;
> + else if (val == new_wc)
> + *has_new = true;
> + }
> + raw_spin_unlock_irqrestore(&list->lock, flags);
> + }
> + return found_addr;
> +}
> +
> +/*
> + * Move pending waiters to ->scanning, flip the wildcard, then make
> + * one pass over all CPUs. Clear per-waiter bits for CPUs that no
> + * longer hold the waiter address or the corresponding wildcard.
> + *
> + * After the flip, new acquires use the new wildcard. The old
> + * generation therefore makes forward progress and is fully cleared
> + * after enough scan cycles.
> + */
> +static void hazptr_scan_do_cycle(void)
> +{
> + void *old_wc, *new_wc;
> + unsigned int old_idx, new_idx;
> + int cpu;
> + struct hazptr_waiter *w, *n;
> + LIST_HEAD(done);
> +
> + mutex_lock(&hazptr_wildcard_lock);
> +
> + mutex_lock(&hazptr_scan.lock);
> + list_splice_tail_init(&hazptr_scan.pending, &hazptr_scan.scanning);
> + mutex_unlock(&hazptr_scan.lock);
> +
> + if (list_empty(&hazptr_scan.scanning)) {
> + mutex_unlock(&hazptr_wildcard_lock);
> + return;
> + }
> +
> + old_wc = READ_ONCE(hazptr_wildcard);
> + new_wc = flip_wildcard(old_wc);
> + WRITE_ONCE(hazptr_wildcard, new_wc);
> + old_idx = (unsigned long)old_wc - 1;
> + new_idx = 1 - old_idx;
> +
> + /*
> + * One pass over all CPUs for the per-CPU slots, checking
> + * overflow lists for the remaining waiters.
> + */
> + for_each_possible_cpu(cpu) {
> + struct hazptr_percpu_slots *slots =
> per_cpu_ptr(&hazptr_percpu_slots, cpu);
> + void *vals[NR_HAZPTR_PERCPU_SLOTS];
> + bool has_old = false, has_new = false;
> + unsigned int idx;
> +
> + for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> + /* Pairs with smp_store_release in hazptr_release(). */
> + vals[idx] =
> smp_load_acquire(&slots->items[idx].slot.addr);
> + if (vals[idx] == old_wc)
> + has_old = true;
> + else if (vals[idx] == new_wc)
> + has_new = true;
> + }
> +
> + list_for_each_entry(w, &hazptr_scan.scanning, node) {
> + bool has_addr = false;
> +
> + if (!test_bit(cpu, hazptr_waiter_mask(w, old_idx)) &&
> + !test_bit(cpu, hazptr_waiter_mask(w, new_idx)))
> + continue; /* Both bits already clear. */
> + for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> + if (vals[idx] == w->addr) {
> + has_addr = true;
> + break;
> + }
> + }
> + if (!has_addr)
> + has_addr = hazptr_ovf_list_blocked(cpu, w->addr,
> + old_wc, new_wc, &has_old, &has_new);
> + if (has_addr)
> + continue;
> + if (!has_old)
> + __clear_bit(cpu, hazptr_waiter_mask(w,
> old_idx));
> + if (!has_new)
> + __clear_bit(cpu, hazptr_waiter_mask(w,
> new_idx));
> + }
> + }
> +
> + mutex_unlock(&hazptr_wildcard_lock);
> +
> + /* Complete waiters whose masks are both empty. */
> + list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) {
> + if (bitmap_empty(hazptr_waiter_mask(w, 0), nr_cpu_ids) &&
> + bitmap_empty(hazptr_waiter_mask(w, 1), nr_cpu_ids))
> + list_move(&w->node, &done);
> + }
> +
> + list_for_each_entry_safe(w, n, &done, node) {
> + list_del_init(&w->node);
> + complete(&w->done);
> + }
> +}
> +
> +/*
> + * Shared scan kthread for hazptr_synchronize() waiters.
> + */
> +static int hazptr_scan_kthread(void *unused)
> +{
> + for (;;) {
> + bool idle;
> +
> + swait_event_idle_exclusive(hazptr_scan.wq,
> + READ_ONCE(hazptr_scan.wakeup));
> +
> + hazptr_scan_do_cycle();
> +
> + mutex_lock(&hazptr_scan.lock);
> + idle = list_empty(&hazptr_scan.pending) &&
> + list_empty(&hazptr_scan.scanning);
> + if (idle)
> + WRITE_ONCE(hazptr_scan.wakeup, false);
> + mutex_unlock(&hazptr_scan.lock);
> +
> + if (idle)
> + continue;
> + /* Waiters still blocked: retry after a polling delay. */
> + schedule_timeout_idle(1);
> + }
> + return 0;
> +}
> +
> +/*
> + * Queue @addr for scan-thread processing, then sleep until the scan
> + * thread observes that @addr is no longer held by any hazard pointer.
> + * Returns false if the waiter masks cannot be allocated, in which
> + * case the caller falls back to the direct scan.
> + */
> +static bool hazptr_synchronize_queued(void *addr)
> +{
> + struct hazptr_waiter waiter = {
> + .addr = addr,
> + };
> + unsigned long *masks;
> + unsigned int mask_longs = BITS_TO_LONGS(nr_cpu_ids);
> +
> + masks = kcalloc(2, mask_longs * sizeof(unsigned long), GFP_KERNEL);
> + if (!masks)
> + return false;
> + bitmap_fill(masks, nr_cpu_ids);
> + bitmap_fill(masks + mask_longs, nr_cpu_ids);
> + waiter.cpu_mask = masks;
> +
> + init_completion(&waiter.done);
> + INIT_LIST_HEAD(&waiter.node);
> +
> + /* Enqueue and wake the scan kthread. */
> + mutex_lock(&hazptr_scan.lock);
> + list_add_tail(&waiter.node, &hazptr_scan.pending);
> + if (!READ_ONCE(hazptr_scan.wakeup)) {
> + WRITE_ONCE(hazptr_scan.wakeup, true);
> + swake_up_one(&hazptr_scan.wq);
> + }
> + mutex_unlock(&hazptr_scan.lock);
> +
> + /* Sleep until the scan thread completes this waiter. */
> + wait_for_completion(&waiter.done);
> + kfree(masks);
> + return true;
> +}
> +
> /*
> * hazptr_synchronize: Wait until @addr is released from all slots.
> *
> * Wait to observe that each slot contains a value that differs from
> * @addr before returning.
> * Should be called from preemptible context.
> + *
> + * If the scan kthread is running, the caller is queued and the scan
> + * thread performs the work, allowing multiple concurrent callers to
> + * share a single scan cycle. Otherwise, the existing direct
> + * two-phase scan is used as a fallback.
> */
> void hazptr_synchronize(void *addr)
> {
> @@ -235,6 +478,13 @@ void hazptr_synchronize(void *addr)
> /* Memory ordering: Store A before Load B. */
> smp_mb();
>
> + /* Use the scan thread if available. */
> + /* Pairs with smp_store_release in hazptr_scan_init(). */
> + if (smp_load_acquire(&hazptr_scan.kthread) &&
> + hazptr_synchronize_queued(addr))
> + return;
> +
> + /* Fallback: direct two-phase wildcard scan. */
> guard(mutex)(&hazptr_wildcard_lock);
> scan_wildcard = flip_wildcard(hazptr_wildcard);
> hazptr_scan_period(addr, scan_wildcard);
> @@ -282,3 +532,27 @@ void __init hazptr_init(void)
> }
> }
> }
> +
> +/*
> + * Initialize the scan kthread. On failure falls back to the direct
> + * scan (busy-wait) path at synchronize time.
> + * core_initcall ensures the scheduler is ready before kthread_run.
> + */
> +static int __init hazptr_scan_init(void)
> +{
> + struct task_struct *t;
> +
> + init_swait_queue_head(&hazptr_scan.wq);
> + mutex_init(&hazptr_scan.lock);
> + INIT_LIST_HEAD(&hazptr_scan.pending);
> + INIT_LIST_HEAD(&hazptr_scan.scanning);
> +
> + t = kthread_run(hazptr_scan_kthread, NULL, "hazptr_scan");
> + if (!IS_ERR(t))
> + /* Pairs with smp_load_acquire in hazptr_synchronize(). */
> + smp_store_release(&hazptr_scan.kthread, t);
> + else
> + pr_warn("hazptr: scan thread failed, using direct scan\n");
> + return 0;
> +}
> +core_initcall(hazptr_scan_init);
> --
> 2.43.0
>
