Kunwu Chan <[email protected]> writes:
> Boqun Feng pointed out that a promote racing a scan can cause the
> scan to miss a hazard pointer: hazptr_promote_to_backup_slot()
> chains the backup slot into an overflow list before clearing the
> per-CPU slot, so the scan must observe the old location before the
> new one. The scan currently visits each CPU's overflow lists right
> after that CPU's per-CPU slots, so a promote that moves a hazard
> pointer from a per-CPU slot of a later-scanned CPU into an overflow
> list of an earlier-scanned CPU can be missed.
>
> The direct two-phase scan has a related race because the overflow
> list selection follows the wildcard phase: a promote racing the
> wildcard flip can move a backup slot to the list not covered by the
> second phase.
>
> Fix this by scanning all per-CPU slots before any overflow-list
> slot, in both the shared-scan walk and the direct fallback scan.
> Give the overflow lists a flip phase of their own, independent of
> the wildcard, so each list is scanned while it is the non-live one:
> new backup slots are chained to the other list, preserving forward
> progress.
>
> The same race was also addressed by Mathieu Desnoyers.
Hello,
I tested the previous faulting patch with a standalone reproducer. It
admits the following interleaving, resulting in Too-short grace period.
Initially, hazptr_wildcard is 1. Below, p is a pointer to the protected
object, and slot is the reader's per-CPU slot.
Mutator Reader
------- ------
/* hazptr_acquire() */
void *addr;
WRITE_ONCE(slot->addr,
READ_ONCE(hazptr_wildcard));
...
addr = READ_ONCE(*addr_p);
/* addr == p */
void *old = p;
smp_store_release(&p, NULL);
hazptr_synchronize(old);
...
scan_wildcard =
flip_wildcard(hazptr_wildcard);
/* scan_wildcard == 2 */
/* First pass: Load B */
smp_cond_load_acquire(
&item->slot.addr,
VAL != addr &&
VAL != scan_wildcard);
/* Sees wildcard 1, so proceeds. */
/* Store C */
WRITE_ONCE(slot->addr, addr);
/* scans list 1. */
hazptr_synchronize_overflow_list(
&overflow_list_flip->array[scan_idx],
addr);
...
WRITE_ONCE(hazptr_wildcard,
scan_wildcard);
/* hazptr_wildcard == 2 */
hazptr_detach(&ctx);
...
/* hazptr_chain_backup_slot() */
unsigned int list_idx =
(unsigned long)
READ_ONCE(hazptr_wildcard) - 1;
/* list_idx == 1 */
...
/* Protection moves to the
* backup slot in list 1.
* The per-CPU slot is cleared. */
hazptr_scan_period(
addr, flip_wildcard(scan_wildcard));
/* Second pass sees the cleared
* per-CPU slot and scans list 0,
* missing the backup slot in list 1. */
/* Returns while the reader
* still holds the hazard pointer. */
The critical orderings extracted from this failure are:
1. [Load B] -> [Store C]
2. [WRITE_ONCE(hazptr_wildcard, scan_wildcard)]
-> [unsigned int list_idx = (unsigned long) READ_ONCE(hazptr_wildcard) - 1]
Kunwu's patch (hazptr: scan all per-CPU slots before overflow lists)
addresses the second ordering. The overflow-list phase is now flipped
only after both per-CPU scan passes.
I also tested the patched version and it did not reproduce the previous
failure.
> Fixes: 0b8114b25f17 ("hazptr: Implement two-phase wildcard scan")
> Reported-by: Boqun Feng <[email protected]>
> Link:
> https://lore.kernel.org/all/[email protected]/
> Signed-off-by: Kunwu Chan <[email protected]>
> ---
> kernel/hazptr.c | 88 +++++++++++++++++++++++++++++++++++--------------
> 1 file changed, 64 insertions(+), 24 deletions(-)
>
> diff --git a/kernel/hazptr.c b/kernel/hazptr.c
> index 900ba35de2cb..799784f698ed 100644
> --- a/kernel/hazptr.c
> +++ b/kernel/hazptr.c
> @@ -23,13 +23,20 @@
> * 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. */
> +static DEFINE_MUTEX(hazptr_phase_lock);
> +/* Protect the wildcard and overflow-list phase flips. */
> void *hazptr_wildcard = (void *) 1UL;
> EXPORT_SYMBOL_GPL(hazptr_wildcard);
>
> +/*
> + * The current overflow list phase. Independent from the wildcard so that the
> + * overflow list scan can be placed after the per-CPU slot scan while still
> + * scanning the non-live list: the current list used by readers is
> + * array[hazptr_overflow_list_phase].
> + */
> +static unsigned int hazptr_overflow_list_phase;
> +
> struct hazptr_overflow_list {
> raw_spinlock_t lock; /* Lock protecting overflow list and
> list generation. */
> struct hlist_head head; /* Overflow list head. */
> @@ -59,6 +66,12 @@ void *flip_wildcard(void *wildcard)
> return ((unsigned long) wildcard == 1UL) ? (void *) 2UL : (void *) 1UL;
> }
>
> +static
> +unsigned int flip_list_phase(unsigned int phase)
> +{
> + return 1 - phase;
> +}
> +
> static
> bool is_wildcard(void *addr)
> {
> @@ -184,15 +197,12 @@ void hazptr_synchronize_cpu_slots(int cpu, void *addr,
> void *scan_wildcard)
> }
>
> static
> -void hazptr_scan_period(void *addr, void *scan_wildcard)
> +void hazptr_scan_cpu_slots_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
> @@ -205,12 +215,22 @@ void hazptr_scan_period(void *addr, void *scan_wildcard)
> * to acquire that same hazard pointer value.
> */
> hazptr_synchronize_cpu_slots(cpu, addr, scan_wildcard);
> + }
> +}
> +
> +static
> +void hazptr_scan_overflow_list_period(void *addr, unsigned int scan_idx)
> +{
> + int cpu;
> +
> + /*
> + * Scan backup slots in percpu overflow lists.
> + * Forward progress is guaranteed by scanning one list
> + * while new elements are added into the other list.
> + */
> + for_each_possible_cpu(cpu) {
> + struct hazptr_overflow_list_flip *overflow_list_flip =
> per_cpu_ptr(&percpu_overflow_list_flip, cpu);
>
> - /*
> - * 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);
> }
> }
> @@ -285,10 +305,13 @@ static struct hazptr_scan_state hazptr_scan;
> * 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.
> + * All per-CPU slots are examined before any overflow-list slot: a
> + * promote (hazptr_detach() or a context switch) moves a hazard
> + * pointer from a per-CPU slot to an overflow list by chaining the
> + * backup slot before clearing the per-CPU slot, see
> + * hazptr_promote_to_backup_slot(). Therefore the scan must observe
> + * the old location before the new location for every slot/list
> + * pair, including pairs on different CPUs.
> */
> static bool hazptr_scan_walk(void *watch, struct hazptr_bloom *bloom)
> {
> @@ -297,9 +320,9 @@ static bool hazptr_scan_walk(void *watch, struct
> hazptr_bloom *bloom)
> if (bloom)
> hazptr_bloom_reset(bloom);
>
> + /* Scan all per-CPU slots before any overflow-list slot. */
> 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);
> unsigned int idx;
>
> for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> @@ -313,6 +336,10 @@ static bool hazptr_scan_walk(void *watch, struct
> hazptr_bloom *bloom)
> if (bloom && v && !is_wildcard(v))
> hazptr_bloom_add(bloom, v);
> }
> + }
> + for_each_possible_cpu(cpu) {
> + struct hazptr_overflow_list_flip *overflow_list_flip =
> per_cpu_ptr(&percpu_overflow_list_flip, cpu);
> +
> for (int i = 0; i < 2; i++) {
> struct hazptr_overflow_list *list =
> &overflow_list_flip->array[i];
> struct hazptr_backup_slot *b;
> @@ -359,14 +386,14 @@ static void hazptr_scan_do_cycle(void)
> struct hazptr_waiter *w, *n;
> LIST_HEAD(done);
>
> - mutex_lock(&hazptr_wildcard_lock);
> + mutex_lock(&hazptr_phase_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);
> + mutex_unlock(&hazptr_phase_lock);
> return;
> }
>
> @@ -391,7 +418,7 @@ static void hazptr_scan_do_cycle(void)
> list_move(&w->node, &done);
> }
>
> - mutex_unlock(&hazptr_wildcard_lock);
> + mutex_unlock(&hazptr_phase_lock);
>
> list_for_each_entry_safe(w, n, &done, node) {
> list_del_init(&w->node);
> @@ -463,6 +490,7 @@ static void hazptr_synchronize_queued(void *addr)
> void hazptr_synchronize(void *addr)
> {
> void *scan_wildcard;
> + unsigned int scan_list_phase;
>
> /*
> * Busy-wait should only be done from preemptible context.
> @@ -486,18 +514,30 @@ void hazptr_synchronize(void *addr)
> }
>
> /* Fallback: use the direct scan path. */
> - guard(mutex)(&hazptr_wildcard_lock);
> + guard(mutex)(&hazptr_phase_lock);
> scan_wildcard = flip_wildcard(hazptr_wildcard);
> - hazptr_scan_period(addr, scan_wildcard);
> + /* Scan per-CPU slots. */
> + hazptr_scan_cpu_slots_period(addr, scan_wildcard);
> WRITE_ONCE(hazptr_wildcard, scan_wildcard); /* Flip the current
> wildcard. */
> - hazptr_scan_period(addr, flip_wildcard(scan_wildcard));
> + hazptr_scan_cpu_slots_period(addr, flip_wildcard(scan_wildcard));
> +
> + /*
> + * Scan overflow lists *after* scanning all per-CPU slots, see
> + * hazptr_promote_to_backup_slot(). Flip the overflow list phase
> + * between the two lists so that each list is scanned while it is
> + * the non-live one.
> + */
> + scan_list_phase = flip_list_phase(hazptr_overflow_list_phase);
> + hazptr_scan_overflow_list_period(addr, scan_list_phase);
> + WRITE_ONCE(hazptr_overflow_list_phase, scan_list_phase);
> + hazptr_scan_overflow_list_period(addr,
> flip_list_phase(scan_list_phase));
> }
> 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 = (unsigned long) READ_ONCE(hazptr_wildcard) - 1;
> + unsigned int list_idx = READ_ONCE(hazptr_overflow_list_phase);
> struct hazptr_overflow_list *overflow_list =
> &overflow_list_flip->array[list_idx];
> struct hazptr_slot *slot = &ctx->backup_slot.slot;
--
Kai Ma
