/* SPDX-License-Identifier: GPL-2.0 */ #ifndef _GEN_PV_LOCK_SLOWPATH #error "do not include this file" #endif #include <linux/hash.h> #include <linux/memblock.h> #include <linux/debug_locks.h> /* * Implement paravirt qspinlocks; the general idea is to halt the vcpus instead * of spinning them. * * This relies on the architecture to provide two paravirt hypercalls: * * pv_wait(u8 *ptr, u8 val) -- suspends the vcpu if *ptr == val * pv_kick(cpu) -- wakes a suspended vcpu * * Using these we implement __pv_queued_spin_lock_slowpath() and * __pv_queued_spin_unlock() to replace native_queued_spin_lock_slowpath() and * native_queued_spin_unlock(). */ #define _Q_SLOW_VAL … /* * Queue Node Adaptive Spinning * * A queue node vCPU will stop spinning if the vCPU in the previous node is * not running. The one lock stealing attempt allowed at slowpath entry * mitigates the slight slowdown for non-overcommitted guest with this * aggressive wait-early mechanism. * * The status of the previous node will be checked at fixed interval * controlled by PV_PREV_CHECK_MASK. This is to ensure that we won't * pound on the cacheline of the previous node too heavily. */ #define PV_PREV_CHECK_MASK … /* * Queue node uses: vcpu_running & vcpu_halted. * Queue head uses: vcpu_running & vcpu_hashed. */ enum vcpu_state { … }; struct pv_node { … }; /* * Hybrid PV queued/unfair lock * * By replacing the regular queued_spin_trylock() with the function below, * it will be called once when a lock waiter enter the PV slowpath before * being queued. * * The pending bit is set by the queue head vCPU of the MCS wait queue in * pv_wait_head_or_lock() to signal that it is ready to spin on the lock. * When that bit becomes visible to the incoming waiters, no lock stealing * is allowed. The function will return immediately to make the waiters * enter the MCS wait queue. So lock starvation shouldn't happen as long * as the queued mode vCPUs are actively running to set the pending bit * and hence disabling lock stealing. * * When the pending bit isn't set, the lock waiters will stay in the unfair * mode spinning on the lock unless the MCS wait queue is empty. In this * case, the lock waiters will enter the queued mode slowpath trying to * become the queue head and set the pending bit. * * This hybrid PV queued/unfair lock combines the best attributes of a * queued lock (no lock starvation) and an unfair lock (good performance * on not heavily contended locks). */ #define queued_spin_trylock(l) … static inline bool pv_hybrid_queued_unfair_trylock(struct qspinlock *lock) { … } /* * The pending bit is used by the queue head vCPU to indicate that it * is actively spinning on the lock and no lock stealing is allowed. */ #if _Q_PENDING_BITS == 8 static __always_inline void set_pending(struct qspinlock *lock) { … } /* * The pending bit check in pv_queued_spin_steal_lock() isn't a memory * barrier. Therefore, an atomic cmpxchg_acquire() is used to acquire the * lock just to be sure that it will get it. */ static __always_inline bool trylock_clear_pending(struct qspinlock *lock) { … } #else /* _Q_PENDING_BITS == 8 */ static __always_inline void set_pending(struct qspinlock *lock) { atomic_or(_Q_PENDING_VAL, &lock->val); } static __always_inline bool trylock_clear_pending(struct qspinlock *lock) { int old, new; old = atomic_read(&lock->val); do { if (old & _Q_LOCKED_MASK) return false; /* * Try to clear pending bit & set locked bit */ new = (old & ~_Q_PENDING_MASK) | _Q_LOCKED_VAL; } while (!atomic_try_cmpxchg_acquire (&lock->val, &old, new)); return true; } #endif /* _Q_PENDING_BITS == 8 */ /* * Lock and MCS node addresses hash table for fast lookup * * Hashing is done on a per-cacheline basis to minimize the need to access * more than one cacheline. * * Dynamically allocate a hash table big enough to hold at least 4X the * number of possible cpus in the system. Allocation is done on page * granularity. So the minimum number of hash buckets should be at least * 256 (64-bit) or 512 (32-bit) to fully utilize a 4k page. * * Since we should not be holding locks from NMI context (very rare indeed) the * max load factor is 0.75, which is around the point where open addressing * breaks down. * */ struct pv_hash_entry { … }; #define PV_HE_PER_LINE … #define PV_HE_MIN … static struct pv_hash_entry *pv_lock_hash; static unsigned int pv_lock_hash_bits __read_mostly; /* * Allocate memory for the PV qspinlock hash buckets * * This function should be called from the paravirt spinlock initialization * routine. */ void __init __pv_init_lock_hash(void) { … } #define for_each_hash_entry(he, offset, hash) … static struct qspinlock **pv_hash(struct qspinlock *lock, struct pv_node *node) { … } static struct pv_node *pv_unhash(struct qspinlock *lock) { … } /* * Return true if when it is time to check the previous node which is not * in a running state. */ static inline bool pv_wait_early(struct pv_node *prev, int loop) { … } /* * Initialize the PV part of the mcs_spinlock node. */ static void pv_init_node(struct mcs_spinlock *node) { … } /* * Wait for node->locked to become true, halt the vcpu after a short spin. * pv_kick_node() is used to set _Q_SLOW_VAL and fill in hash table on its * behalf. */ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev) { … } /* * Called after setting next->locked = 1 when we're the lock owner. * * Instead of waking the waiters stuck in pv_wait_node() advance their state * such that they're waiting in pv_wait_head_or_lock(), this avoids a * wake/sleep cycle. */ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node) { … } /* * Wait for l->locked to become clear and acquire the lock; * halt the vcpu after a short spin. * __pv_queued_spin_unlock() will wake us. * * The current value of the lock will be returned for additional processing. */ static u32 pv_wait_head_or_lock(struct qspinlock *lock, struct mcs_spinlock *node) { … } /* * Include the architecture specific callee-save thunk of the * __pv_queued_spin_unlock(). This thunk is put together with * __pv_queued_spin_unlock() to make the callee-save thunk and the real unlock * function close to each other sharing consecutive instruction cachelines. * Alternatively, architecture specific version of __pv_queued_spin_unlock() * can be defined. */ #include <asm/qspinlock_paravirt.h> /* * PV versions of the unlock fastpath and slowpath functions to be used * instead of queued_spin_unlock(). */ __visible __lockfunc void __pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked) { … } #ifndef __pv_queued_spin_unlock __visible __lockfunc void __pv_queued_spin_unlock(struct qspinlock *lock) { u8 locked = _Q_LOCKED_VAL; /* * We must not unlock if SLOW, because in that case we must first * unhash. Otherwise it would be possible to have multiple @lock * entries, which would be BAD. */ if (try_cmpxchg_release(&lock->locked, &locked, 0)) return; __pv_queued_spin_unlock_slowpath(lock, locked); } #endif /* __pv_queued_spin_unlock */
Codebase Browser
linux