From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4FF53385D6B for ; Sat, 8 Aug 2026 17:40:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786210859; cv=none; b=H8Z1VhSXljoFDZEfUoESdi6BKtv+Ar2orryuDVpi9GoKDlElTU8oBJ4WCUCkt5Qubpe6lwG2VSMH9CMmPtqyYK4pZznAprXErApRXyTB/uGtlGu+G9f7URzPJManKDYob1c+3xsu8lo2JU1MUqqla6XoTFCxE+E5icby3VOY5K4= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786210859; c=relaxed/simple; bh=20gakielCiYrHPUBn2JtxIhv0lum46RTpROoaAmvsIs=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=QRayebT+dszlrbH1n0BGbgmKDDjIY89hQknWIMh2ZNGjTdY6QxMu5fHFARCX0jwpQA917BOZoIg5VwDKT4bJ2l/tMVElqbPffOZ9JrNMUzsFvBxhXTREK6VjjqcZVZBHK4px4GJ7dj5nBloy6M1RZXLZNH0MGsokzz+aijw/jb8= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=c+xzVuXP; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="c+xzVuXP" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1786210316; bh=XairFsWV2sXCYth5FKGEcuAbm3bJmmUvIGdXO/QLWDM=; h=From:To:Cc:Subject:Date:From; b=c+xzVuXP/rC6cxTa3txcHS4HwAZM5X6AKvZOA2qJJcACpgTh02pZJ72XERERHzfxb 5sqo0PZn8F3iY+ylBdi2Da56OLrJmT/cVryn8OxfedL5HDhYGZ/qgvnRxxjHH8d5Uf QVC9geQg/4r840UW2cJJPWCh8pdODI8VFFlz3xszpvUkKWn6GDl2yVwc9YShvTO7Vw mZkRAHeWE2Ao1nU+Zl8hToxB4FRF/KIYUofNb27/4Pq5soTv8I4jCo4OFTN+P6Xlun miBFUtyazZHxIGXdROpCfXb1dLo3BDzThX0VknAj7AvwsyvcsutacjgngHh59EtSL1 wXbPn3BBh9xmA== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hHSkN6fpczM8D; Sat, 08 Aug 2026 13:31:56 -0400 (EDT) From: Mathieu Desnoyers To: "Paul E . McKenney" Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [RFC PATCH 1/1] hazptr: Implement two-phases wildcard scan Date: Sat, 8 Aug 2026 13:31:49 -0400 Message-ID: <20260808173152.6137-1-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Implement a two-phases wildcard scan to guarantee forward progress of synchronize_hazptr() even if there is a steady stream of ill-timed readers which populate wildcards into per-CPU slots. This is performed by flipping between two wildcard values (1UL and 2UL), and alternatively scanning for the opposite wildcard while newcoming readers use the other one. There is no possibility to miss a reader because all slots for all wildcards are accounted for during a synchronize. As a simplificaiton, use this period flip to drive the hazptr overflow list selection as well, since there is really no point is making the overflow list flip use a different state. Protect the wildcard flip with a mutex. Signed-off-by: Mathieu Desnoyers --- include/linux/hazptr.h | 6 ++- kernel/hazptr.c | 98 ++++++++++++++++++++++++++++++------------ 2 files changed, 74 insertions(+), 30 deletions(-) diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h index 43998bf43de4..43122c5673bd 100644 --- a/include/linux/hazptr.h +++ b/include/linux/hazptr.h @@ -28,7 +28,9 @@ /* 4 slots (each sizeof(hazptr_slot_item)) fit in a single 64-byte cache line. */ #define NR_HAZPTR_PERCPU_SLOTS 4 -#define HAZPTR_WILDCARD ((void *) 0x1UL) + +/* The current hazard pointer wildcard. */ +extern void *hazptr_wildcard; /* * Hazard pointer slot. @@ -243,7 +245,7 @@ void *hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p) #endif if (unlikely(slot->addr)) return __hazptr_acquire(ctx, addr_p); - WRITE_ONCE(slot->addr, HAZPTR_WILDCARD); /* Store B */ + WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard)); /* Store B */ /* Memory ordering: Store B before Load A. */ smp_mb(); diff --git a/kernel/hazptr.c b/kernel/hazptr.c index a9d3d68a1525..d3d1050d92cf 100644 --- a/kernel/hazptr.c +++ b/kernel/hazptr.c @@ -13,6 +13,17 @@ #include #include +/* + * The current hazard pointer wildcard. Flips between 1UL and 2UL to guarantee + * hazptr_synchronize forward progress even with a steady stream of readers. + * This wildcard value is used by acquire to temporarily tag the per-CPU slots. + * This also affects the overflow list selection: the current list used by + * readers is array[(unsigned long) hazptr_wildcard - 1]. + */ +static DEFINE_MUTEX(hazptr_wildcard_lock); /* Protect the wildcard flip. */ +void *hazptr_wildcard = (void *) 1UL; +EXPORT_SYMBOL_GPL(hazptr_wildcard); + struct hazptr_overflow_list { raw_spinlock_t lock; /* Lock protecting overflow list and list generation. */ struct hlist_head head; /* Overflow list head. */ @@ -28,8 +39,6 @@ struct hazptr_overflow_list { * limited to the number of list elements. */ struct hazptr_overflow_list_flip { - struct mutex lock; /* Mutex protecting add_idx from concurrent updates. */ - unsigned int add_idx; /* Index of current flip-list to add to. */ struct hazptr_overflow_list array[2]; }; @@ -38,6 +47,20 @@ static DEFINE_PER_CPU(struct hazptr_overflow_list_flip, percpu_overflow_list_fli DEFINE_PER_CPU(struct hazptr_percpu_slots, hazptr_percpu_slots); EXPORT_PER_CPU_SYMBOL_GPL(hazptr_percpu_slots); +static +void *flip_wildcard(void *wildcard) +{ + return ((unsigned long) wildcard == 1UL) ? (void *) 2UL : (void *) 1UL; +} + +static +bool is_wildcard(void *addr) +{ + if ((unsigned long) addr == 1UL || (unsigned long) addr == 2UL) + return true; + return false; +} + static struct hazptr_slot *hazptr_get_free_percpu_slot(struct hazptr_ctx *ctx) { @@ -72,7 +95,7 @@ void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p) */ if (unlikely(!slot)) slot = hazptr_chain_backup_slot(ctx); - WRITE_ONCE(slot->addr, HAZPTR_WILDCARD); /* Store B */ + WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard)); /* Store B */ /* Memory ordering: Store B before Load A. */ smp_mb(); @@ -118,7 +141,9 @@ void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list for (;;) { void *load_addr = smp_load_acquire(&backup_slot->slot.addr); /* Load B */ - if (load_addr != addr && load_addr != HAZPTR_WILDCARD) + /* We don't expect wildcards in overflow list. */ + WARN_ON_ONCE(is_wildcard(load_addr)); + if (load_addr != addr) break; raw_spin_unlock_irqrestore(&overflow_list->lock, flags); cpu_relax(); @@ -139,7 +164,7 @@ void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list } static -void hazptr_synchronize_cpu_slots(int cpu, void *addr) +void hazptr_synchronize_cpu_slots(int cpu, void *addr, void *scan_wildcard) { struct hazptr_percpu_slots *percpu_slots = per_cpu_ptr(&hazptr_percpu_slots, cpu); unsigned int idx; @@ -148,7 +173,39 @@ void hazptr_synchronize_cpu_slots(int cpu, void *addr) struct hazptr_slot_item *item = &percpu_slots->items[idx]; /* Busy-wait if node is found. */ - smp_cond_load_acquire(&item->slot.addr, VAL != addr && VAL != HAZPTR_WILDCARD); /* Load B */ + smp_cond_load_acquire(&item->slot.addr, VAL != addr && VAL != scan_wildcard); /* Load B */ + } +} + +static +void hazptr_scan_period(void *addr, void *scan_wildcard) +{ + unsigned int scan_idx = (unsigned long) scan_wildcard - 1; + int cpu; + + /* Scan all CPUs slots. */ + for_each_possible_cpu(cpu) { + struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu); + + /* + * Scan CPU slots. + * Forward progress against recurring wildcards is guaranteed + * by scanning for one wildcard while new elements use the + * other wildcard value (1UL vs 2UL). + * Forward progress against recurring single hazard pointer + * values is guaranteed by the fact that a hazard pointer + * is not reclaimed nor reused until the scan for that hazard + * pointer completes, which prevents a steady flow of readers + * to acquire that same hazard pointer value. + */ + hazptr_synchronize_cpu_slots(cpu, addr, scan_wildcard); + + /* + * Scan backup slots in percpu overflow lists. + * Forward progress is guaranteed by scanning one list + * while new elements are added into the other list. + */ + hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx], addr); } } @@ -161,7 +218,7 @@ void hazptr_synchronize_cpu_slots(int cpu, void *addr) */ void hazptr_synchronize(void *addr) { - int cpu; + void *scan_wildcard; /* * Busy-wait should only be done from preemptible context. @@ -177,33 +234,19 @@ void hazptr_synchronize(void *addr) return; /* Memory ordering: Store A before Load B. */ smp_mb(); - /* Scan all CPUs slots. */ - for_each_possible_cpu(cpu) { - struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu); - unsigned int scan_idx; - - /* Scan CPU slots. */ - hazptr_synchronize_cpu_slots(cpu, addr); - /* - * Scan backup slots in percpu overflow lists. - * Forward progress is guaranteed by scanning one list - * while new elements are added into the other list. - */ - guard(mutex)(&overflow_list_flip->lock); - scan_idx = overflow_list_flip->add_idx ^ 1; - hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx], addr); - /* Flip current list. */ - WRITE_ONCE(overflow_list_flip->add_idx, scan_idx); - hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx ^ 1], addr); - } + guard(mutex)(&hazptr_wildcard_lock); + scan_wildcard = flip_wildcard(hazptr_wildcard); + hazptr_scan_period(addr, scan_wildcard); + WRITE_ONCE(hazptr_wildcard, scan_wildcard); /* Flip the current wildcard. */ + hazptr_scan_period(addr, flip_wildcard(scan_wildcard)); } EXPORT_SYMBOL_GPL(hazptr_synchronize); struct hazptr_slot *hazptr_chain_backup_slot(struct hazptr_ctx *ctx) { struct hazptr_overflow_list_flip *overflow_list_flip = this_cpu_ptr(&percpu_overflow_list_flip); - unsigned int list_idx = READ_ONCE(overflow_list_flip->add_idx); + unsigned int list_idx = (unsigned long) READ_ONCE(hazptr_wildcard) - 1; struct hazptr_overflow_list *overflow_list = &overflow_list_flip->array[list_idx]; struct hazptr_slot *slot = &ctx->backup_slot.slot; @@ -233,7 +276,6 @@ void __init hazptr_init(void) for_each_possible_cpu(cpu) { struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu); - mutex_init(&overflow_list_flip->lock); for (int i = 0; i < 2; i++) { raw_spin_lock_init(&overflow_list_flip->array[i].lock); INIT_HLIST_HEAD(&overflow_list_flip->array[i].head); -- 2.43.0