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.
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;
--
2.43.0
