On Tue, Sep 22, 2026 at 4:28 PM Boqun Feng <[email protected]> wrote: > > 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). >
Thanks boqun, this is a useful direction. > 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? Sure, I'll give it a try. I'll rework the scan state around the Bloom filter and address the per-CPU slot and wildcard handling in the next version. I'll also credit your 2025 patch design in the commit message. Thanks, Kunwu > > 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 > >
