Introduce a "try acquire" hazard pointer fast path, which performs an early load of the address to store it into the hazard pointer slot, and then re-loads that address after a barrier to check whether it has changed meanwhile.
On comparison failure, rather than re-try, guarantee forward progress by falling back to the __hazptr_acquire slow path on failure. The acquire slow path attempts a try-acquire for any available per-CPU slot. If that fails, it chains the backup slot into the overflow list, therefore guaranteeing forward progress for both hazard pointer read-side and synchronize: - Readers set the wildcard, and then proceed to set the more specific address to replace the wildcard. - One synchronize alternates between two overflow list periods, scanning each one while readers are added to the other period, thus preventing a steady flow of readers from preventing synchronize forward progress. With this change, the scan on per-CPU slots don't need to expect a wildcard anymore, because none can be produced by readers. Wildcards are only expected within overflow lists. Signed-off-by: Mathieu Desnoyers <[email protected]> Cc: Paul E. McKenney <[email protected]> Cc: Boqun Feng <[email protected]> Cc: Bradley Morgan <[email protected]> Cc: Gary Guo <[email protected]> Cc: <[email protected]> Cc: <[email protected]> --- include/linux/hazptr.h | 47 +++++++++++-------- kernel/hazptr.c | 103 ++++++++++++++++++++--------------------- 2 files changed, 76 insertions(+), 74 deletions(-) diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h index d1670121947a..fcf017ca2255 100644 --- a/include/linux/hazptr.h +++ b/include/linux/hazptr.h @@ -29,9 +29,6 @@ /* 4 slots (each sizeof(hazptr_slot_item)) fit in a single 64-byte cache line. */ #define NR_HAZPTR_PERCPU_SLOTS 4 -/* The current hazard pointer wildcard. */ -extern void *hazptr_wildcard; - /* * Hazard pointer slot. */ @@ -190,6 +187,31 @@ void hazptr_note_context_switch(void) } } +/* Try hazard pointer protection. */ +static inline +void *__hazptr_try_acquire(struct hazptr_ctx *ctx, void * const *addr_p, struct hazptr_slot *slot) +{ + void *early_addr, *addr; + + if (unlikely(slot->addr)) + return NULL; + early_addr = READ_ONCE(*addr_p); /* Early load. */ + WRITE_ONCE(slot->addr, early_addr); /* Store B */ + /* Memory ordering: Store B before Load A. */ + smp_mb(); + addr = READ_ONCE(*addr_p); /* Load A */ + /* + * Validate that address did not change between Early load and Load A. + * Use ptr_eq() to make sure that result from Load A is returned to the + * caller to preserve address dependency. + */ + if (unlikely(!ptr_eq(addr, early_addr))) { + WRITE_ONCE(slot->addr, NULL); + return NULL; + } + return addr; +} + /** * hazptr_acquire - Load pointer at address and protect with hazard pointer. * @@ -245,24 +267,9 @@ void *hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p) ctx->acquire_cpu = smp_processor_id(); ctx->acquire_caller = _THIS_IP_; #endif - if (unlikely(slot->addr)) + addr = __hazptr_try_acquire(ctx, addr_p, slot); + if (unlikely(!addr)) return __hazptr_acquire(ctx, addr_p); - WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard)); /* Store B */ - - /* Memory ordering: Store B before Load A. */ - smp_mb(); - - /* - * Load @addr_p after storing wildcard to the hazard pointer slot. - */ - addr = READ_ONCE(*addr_p); /* Load A */ - - /* - * We don't care about ordering of Store C. It will simply - * replace the wildcard by a more specific address. If addr is - * NULL, we simply store NULL into the slot. - */ - WRITE_ONCE(slot->addr, addr); /* Store C */ slot_item->ctx.ctx = ctx; ctx->slot = slot; return addr; diff --git a/kernel/hazptr.c b/kernel/hazptr.c index 13faa5ba7677..3ca73b56a5c2 100644 --- a/kernel/hazptr.c +++ b/kernel/hazptr.c @@ -13,17 +13,9 @@ #include <linux/list.h> #include <linux/export.h> -static DEFINE_MUTEX(hazptr_phase_lock); /* Protect the wildcard and list phase flip. */ +#define HAZPTR_WILDCARD ((void *) 1UL) -/* - * 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]. - */ -void *hazptr_wildcard = (void *) 1UL; -EXPORT_SYMBOL_GPL(hazptr_wildcard); +static DEFINE_MUTEX(hazptr_phase_lock); /* Protect the list phase flip. */ /* The current overflow list phase. */ static unsigned int hazptr_overflow_list_phase; @@ -41,6 +33,10 @@ struct hazptr_overflow_list { * successively iterates on both lists. Therefore, only list removals * can cause the iteration to retry, and the number of removals is * limited to the number of list elements. + * + * Due to the overflow list raw spin lock, the hazard pointer readers are + * blocking, starvation-free with bounded waiting, assuming bounded critical + * sections and no NMI or virtualization-induced holder preemption. */ struct hazptr_overflow_list_flip { struct hazptr_overflow_list array[2]; @@ -51,26 +47,12 @@ 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 unsigned int flip_list_phase(unsigned int phase) { return 1 - phase; } -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) { @@ -96,16 +78,36 @@ struct hazptr_slot *hazptr_get_free_percpu_slot(struct hazptr_ctx *ctx) */ void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p) { - struct hazptr_slot *slot = hazptr_get_free_percpu_slot(ctx); + struct hazptr_slot *slot; void *addr; /* - * If all the per-CPU slots are already in use, fallback - * to the backup slot. + * In case we are called due to nested use of hazard pointers, + * try a slot protection with per-CPU slots. */ - if (unlikely(!slot)) - slot = hazptr_chain_backup_slot(ctx); - WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard)); /* Store B */ + slot = hazptr_get_free_percpu_slot(ctx); + if (likely(slot)) { + addr = __hazptr_try_acquire(ctx, addr_p, slot); + if (addr) { + ctx->slot = slot; + return addr; + } + } + + /* + * The backup slot overflow list guarantees forward progress of both + * hazard pointer readers and synchronize: + * + * - Readers set the wildcard, and then proceed to set the more + * specific address to replace the wildcard. + * + * - One synchronize alternates between two overflow list periods, + * scanning each one while readers are added to the other period, + * thus preventing a steady flow of readers from preventing + * synchronize forward progress. + */ + slot = hazptr_chain_backup_slot(ctx); + WRITE_ONCE(slot->addr, HAZPTR_WILDCARD); /* Store B */ /* Memory ordering: Store B before Load A. */ smp_mb(); @@ -121,20 +123,21 @@ void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p) * NULL, we simply store NULL into the slot. */ WRITE_ONCE(slot->addr, addr); /* Store C */ + ctx->slot = slot; - if (!addr && hazptr_slot_is_backup(ctx, slot)) + if (!addr) hazptr_unchain_backup_slot(ctx); return addr; } EXPORT_SYMBOL_GPL(__hazptr_acquire); /* - * Perform piecewise iteration on overflow list waiting until "addr" is - * not present. Raw spinlock is released and taken between each list - * item and busy loop iteration. The overflow list generation is checked - * each time the lock is taken to validate that the list has not changed - * before resuming iteration or busy wait. If the generation has - * changed, retry the entire list traversal. + * Perform piecewise iteration on overflow list waiting until "addr" and + * wildcard are not present. Raw spinlock is released and taken between each + * list item and busy loop iteration. The overflow list generation is checked + * each time the lock is taken to validate that the list has not changed before + * resuming iteration or busy wait. If the generation has changed, retry the + * entire list traversal. */ static void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list, void *addr) @@ -147,13 +150,11 @@ void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list retry: snapshot_gen = overflow_list->gen; hlist_for_each_entry(backup_slot, &overflow_list->head, overflow_node) { - /* Busy-wait if node is found. */ + /* Busy-wait if addr or wildcard are found. */ for (;;) { void *load_addr = smp_load_acquire(&backup_slot->slot.addr); /* Load B */ - /* We don't expect wildcards in overflow list. */ - WARN_ON_ONCE(is_wildcard(load_addr)); - if (load_addr != addr) + if (load_addr != addr && load_addr != HAZPTR_WILDCARD) break; raw_spin_unlock_irqrestore(&overflow_list->lock, flags); cpu_relax(); @@ -174,7 +175,7 @@ void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list } static -void hazptr_synchronize_cpu_slots(int cpu, void *addr, void *scan_wildcard) +void hazptr_synchronize_cpu_slots(int cpu, void *addr) { struct hazptr_percpu_slots *percpu_slots = per_cpu_ptr(&hazptr_percpu_slots, cpu); unsigned int idx; @@ -182,13 +183,13 @@ void hazptr_synchronize_cpu_slots(int cpu, void *addr, void *scan_wildcard) for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) { 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 != scan_wildcard); /* Load B */ + /* Busy-wait if addr is found. */ + smp_cond_load_acquire(&item->slot.addr, VAL != addr); /* Load B */ } } static -void hazptr_scan_cpu_slots_period(void *addr, void *scan_wildcard) +void hazptr_scan_cpu_slots(void *addr) { int cpu; @@ -196,16 +197,13 @@ void hazptr_scan_cpu_slots_period(void *addr, void *scan_wildcard) for_each_possible_cpu(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); + hazptr_synchronize_cpu_slots(cpu, addr); } } @@ -237,7 +235,6 @@ void hazptr_scan_overflow_list_period(void *addr, unsigned int scan_idx) void hazptr_synchronize(void *addr) { unsigned int scan_list_phase; - void *scan_wildcard; /* * Busy-wait should only be done from preemptible context. @@ -251,16 +248,14 @@ void hazptr_synchronize(void *addr) */ if (!addr) return; + /* Memory ordering: Store A before Load B. */ smp_mb(); guard(mutex)(&hazptr_phase_lock); /* Scan per-CPU slots. */ - scan_wildcard = flip_wildcard(hazptr_wildcard); - hazptr_scan_cpu_slots_period(addr, scan_wildcard); - WRITE_ONCE(hazptr_wildcard, scan_wildcard); /* Flip the current wildcard. */ - hazptr_scan_cpu_slots_period(addr, flip_wildcard(scan_wildcard)); + hazptr_scan_cpu_slots(addr); /* * Scan overflow lists *after* scanning per-CPU slots. See -- 2.43.0
