[deliverable/linux.git] / kernel / locking / qspinlock_paravirt.h

#ifndef _GEN_PV_LOCK_SLOWPATH
#error "do not include this file"
#endif

#include <linux/hash.h>
#include <linux/bootmem.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	(3U << _Q_LOCKED_OFFSET)

/*
 * 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	0xff

/*
 * Queue node uses: vcpu_running & vcpu_halted.
 * Queue head uses: vcpu_running & vcpu_hashed.
 */
enum vcpu_state {
	vcpu_running = 0,
	vcpu_halted,		/* Used only in pv_wait_node */
	vcpu_hashed,		/* = pv_hash'ed + vcpu_halted */
};

struct pv_node {
	struct mcs_spinlock	mcs;
	struct mcs_spinlock	__res[3];

	int			cpu;
	u8			state;
};

/*
 * Include queued spinlock statistics code
 */
#include "qspinlock_stat.h"

/*
 * 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. By allowing one lock stealing attempt here when the pending
 * bit is off, it helps to reduce the performance impact of lock waiter
 * preemption without the drawback of lock starvation.
 */
#define queued_spin_trylock(l)	pv_queued_spin_steal_lock(l)
static inline bool pv_queued_spin_steal_lock(struct qspinlock *lock)
{
	struct __qspinlock *l = (void *)lock;
	int ret = !(atomic_read(&lock->val) & _Q_LOCKED_PENDING_MASK) &&
		   (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0);

	qstat_inc(qstat_pv_lock_stealing, ret);
	return ret;
}

/*
 * 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)
{
	struct __qspinlock *l = (void *)lock;

	WRITE_ONCE(l->pending, 1);
}

static __always_inline void clear_pending(struct qspinlock *lock)
{
	struct __qspinlock *l = (void *)lock;

	WRITE_ONCE(l->pending, 0);
}

/*
 * The pending bit check in pv_queued_spin_steal_lock() isn't a memory
 * barrier. Therefore, an atomic cmpxchg() is used to acquire the lock
 * just to be sure that it will get it.
 */
static __always_inline int trylock_clear_pending(struct qspinlock *lock)
{
	struct __qspinlock *l = (void *)lock;

	return !READ_ONCE(l->locked) &&
	       (cmpxchg(&l->locked_pending, _Q_PENDING_VAL, _Q_LOCKED_VAL)
			== _Q_PENDING_VAL);
}
#else /* _Q_PENDING_BITS == 8 */
static __always_inline void set_pending(struct qspinlock *lock)
{
	atomic_set_mask(_Q_PENDING_VAL, &lock->val);
}

static __always_inline void clear_pending(struct qspinlock *lock)
{
	atomic_clear_mask(_Q_PENDING_VAL, &lock->val);
}

static __always_inline int trylock_clear_pending(struct qspinlock *lock)
{
	int val = atomic_read(&lock->val);

	for (;;) {
		int old, new;

		if (val  & _Q_LOCKED_MASK)
			break;

		/*
		 * Try to clear pending bit & set locked bit
		 */
		old = val;
		new = (val & ~_Q_PENDING_MASK) | _Q_LOCKED_VAL;
		val = atomic_cmpxchg(&lock->val, old, new);

		if (val == old)
			return 1;
	}
	return 0;
}
#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 {
	struct qspinlock *lock;
	struct pv_node   *node;
};

#define PV_HE_PER_LINE	(SMP_CACHE_BYTES / sizeof(struct pv_hash_entry))
#define PV_HE_MIN	(PAGE_SIZE / sizeof(struct pv_hash_entry))

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)
{
	int pv_hash_size = ALIGN(4 * num_possible_cpus(), PV_HE_PER_LINE);

	if (pv_hash_size < PV_HE_MIN)
		pv_hash_size = PV_HE_MIN;

	/*
	 * Allocate space from bootmem which should be page-size aligned
	 * and hence cacheline aligned.
	 */
	pv_lock_hash = alloc_large_system_hash("PV qspinlock",
					       sizeof(struct pv_hash_entry),
					       pv_hash_size, 0, HASH_EARLY,
					       &pv_lock_hash_bits, NULL,
					       pv_hash_size, pv_hash_size);
}

#define for_each_hash_entry(he, offset, hash)						\
	for (hash &= ~(PV_HE_PER_LINE - 1), he = &pv_lock_hash[hash], offset = 0;	\
	     offset < (1 << pv_lock_hash_bits);						\
	     offset++, he = &pv_lock_hash[(hash + offset) & ((1 << pv_lock_hash_bits) - 1)])

static struct qspinlock **pv_hash(struct qspinlock *lock, struct pv_node *node)
{
	unsigned long offset, hash = hash_ptr(lock, pv_lock_hash_bits);
	struct pv_hash_entry *he;
	int hopcnt = 0;

	for_each_hash_entry(he, offset, hash) {
		hopcnt++;
		if (!cmpxchg(&he->lock, NULL, lock)) {
			WRITE_ONCE(he->node, node);
			qstat_hop(hopcnt);
			return &he->lock;
		}
	}
	/*
	 * Hard assume there is a free entry for us.
	 *
	 * This is guaranteed by ensuring every blocked lock only ever consumes
	 * a single entry, and since we only have 4 nesting levels per CPU
	 * and allocated 4*nr_possible_cpus(), this must be so.
	 *
	 * The single entry is guaranteed by having the lock owner unhash
	 * before it releases.
	 */
	BUG();
}

static struct pv_node *pv_unhash(struct qspinlock *lock)
{
	unsigned long offset, hash = hash_ptr(lock, pv_lock_hash_bits);
	struct pv_hash_entry *he;
	struct pv_node *node;

	for_each_hash_entry(he, offset, hash) {
		if (READ_ONCE(he->lock) == lock) {
			node = READ_ONCE(he->node);
			WRITE_ONCE(he->lock, NULL);
			return node;
		}
	}
	/*
	 * Hard assume we'll find an entry.
	 *
	 * This guarantees a limited lookup time and is itself guaranteed by
	 * having the lock owner do the unhash -- IFF the unlock sees the
	 * SLOW flag, there MUST be a hash entry.
	 */
	BUG();
}

/*
 * 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)
{

	if ((loop & PV_PREV_CHECK_MASK) != 0)
		return false;

	return READ_ONCE(prev->state) != vcpu_running;
}

/*
 * Initialize the PV part of the mcs_spinlock node.
 */
static void pv_init_node(struct mcs_spinlock *node)
{
	struct pv_node *pn = (struct pv_node *)node;

	BUILD_BUG_ON(sizeof(struct pv_node) > 5*sizeof(struct mcs_spinlock));

	pn->cpu = smp_processor_id();
	pn->state = vcpu_running;
}

/*
 * 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)
{
	struct pv_node *pn = (struct pv_node *)node;
	struct pv_node *pp = (struct pv_node *)prev;
	int waitcnt = 0;
	int loop;
	bool wait_early;

	/* waitcnt processing will be compiled out if !QUEUED_LOCK_STAT */
	for (;; waitcnt++) {
		for (wait_early = false, loop = SPIN_THRESHOLD; loop; loop--) {
			if (READ_ONCE(node->locked))
				return;
			if (pv_wait_early(pp, loop)) {
				wait_early = true;
				break;
			}
			cpu_relax();
		}

		/*
		 * Order pn->state vs pn->locked thusly:
		 *
		 * [S] pn->state = vcpu_halted	  [S] next->locked = 1
		 *     MB			      MB
		 * [L] pn->locked		[RmW] pn->state = vcpu_hashed
		 *
		 * Matches the cmpxchg() from pv_kick_node().
		 */
		smp_store_mb(pn->state, vcpu_halted);

		if (!READ_ONCE(node->locked)) {
			qstat_inc(qstat_pv_wait_node, true);
			qstat_inc(qstat_pv_wait_again, waitcnt);
			qstat_inc(qstat_pv_wait_early, wait_early);
			pv_wait(&pn->state, vcpu_halted);
		}

		/*
		 * If pv_kick_node() changed us to vcpu_hashed, retain that
		 * value so that pv_wait_head_or_lock() knows to not also try
		 * to hash this lock.
		 */
		cmpxchg(&pn->state, vcpu_halted, vcpu_running);

		/*
		 * If the locked flag is still not set after wakeup, it is a
		 * spurious wakeup and the vCPU should wait again. However,
		 * there is a pretty high overhead for CPU halting and kicking.
		 * So it is better to spin for a while in the hope that the
		 * MCS lock will be released soon.
		 */
		qstat_inc(qstat_pv_spurious_wakeup, !READ_ONCE(node->locked));
	}

	/*
	 * By now our node->locked should be 1 and our caller will not actually
	 * spin-wait for it. We do however rely on our caller to do a
	 * load-acquire for us.
	 */
}

/*
 * 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)
{
	struct pv_node *pn = (struct pv_node *)node;
	struct __qspinlock *l = (void *)lock;

	/*
	 * If the vCPU is indeed halted, advance its state to match that of
	 * pv_wait_node(). If OTOH this fails, the vCPU was running and will
	 * observe its next->locked value and advance itself.
	 *
	 * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
	 */
	if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
		return;

	/*
	 * Put the lock into the hash table and set the _Q_SLOW_VAL.
	 *
	 * As this is the same vCPU that will check the _Q_SLOW_VAL value and
	 * the hash table later on at unlock time, no atomic instruction is
	 * needed.
	 */
	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
	(void)pv_hash(lock, pn);
}

/*
 * 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)
{
	struct pv_node *pn = (struct pv_node *)node;
	struct __qspinlock *l = (void *)lock;
	struct qspinlock **lp = NULL;
	int waitcnt = 0;
	int loop;

	/*
	 * If pv_kick_node() already advanced our state, we don't need to
	 * insert ourselves into the hash table anymore.
	 */
	if (READ_ONCE(pn->state) == vcpu_hashed)
		lp = (struct qspinlock **)1;

	/*
	 * Tracking # of slowpath locking operations
	 */
	qstat_inc(qstat_pv_lock_slowpath, true);

	for (;; waitcnt++) {
		/*
		 * Set correct vCPU state to be used by queue node wait-early
		 * mechanism.
		 */
		WRITE_ONCE(pn->state, vcpu_running);

		/*
		 * Set the pending bit in the active lock spinning loop to
		 * disable lock stealing before attempting to acquire the lock.
		 */
		set_pending(lock);
		for (loop = SPIN_THRESHOLD; loop; loop--) {
			if (trylock_clear_pending(lock))
				goto gotlock;
			cpu_relax();
		}
		clear_pending(lock);


		if (!lp) { /* ONCE */
			lp = pv_hash(lock, pn);

			/*
			 * We must hash before setting _Q_SLOW_VAL, such that
			 * when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock()
			 * we'll be sure to be able to observe our hash entry.
			 *
			 *   [S] <hash>                 [Rmw] l->locked == _Q_SLOW_VAL
			 *       MB                           RMB
			 * [RmW] l->locked = _Q_SLOW_VAL  [L] <unhash>
			 *
			 * Matches the smp_rmb() in __pv_queued_spin_unlock().
			 */
			if (xchg(&l->locked, _Q_SLOW_VAL) == 0) {
				/*
				 * The lock was free and now we own the lock.
				 * Change the lock value back to _Q_LOCKED_VAL
				 * and unhash the table.
				 */
				WRITE_ONCE(l->locked, _Q_LOCKED_VAL);
				WRITE_ONCE(*lp, NULL);
				goto gotlock;
			}
		}
		WRITE_ONCE(pn->state, vcpu_halted);
		qstat_inc(qstat_pv_wait_head, true);
		qstat_inc(qstat_pv_wait_again, waitcnt);
		pv_wait(&l->locked, _Q_SLOW_VAL);

		/*
		 * The unlocker should have freed the lock before kicking the
		 * CPU. So if the lock is still not free, it is a spurious
		 * wakeup or another vCPU has stolen the lock. The current
		 * vCPU should spin again.
		 */
		qstat_inc(qstat_pv_spurious_wakeup, READ_ONCE(l->locked));
	}

	/*
	 * The cmpxchg() or xchg() call before coming here provides the
	 * acquire semantics for locking. The dummy ORing of _Q_LOCKED_VAL
	 * here is to indicate to the compiler that the value will always
	 * be nozero to enable better code optimization.
	 */
gotlock:
	return (u32)(atomic_read(&lock->val) | _Q_LOCKED_VAL);
}

/*
 * PV versions of the unlock fastpath and slowpath functions to be used
 * instead of queued_spin_unlock().
 */
__visible void
__pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked)
{
	struct __qspinlock *l = (void *)lock;
	struct pv_node *node;

	if (unlikely(locked != _Q_SLOW_VAL)) {
		WARN(!debug_locks_silent,
		     "pvqspinlock: lock 0x%lx has corrupted value 0x%x!\n",
		     (unsigned long)lock, atomic_read(&lock->val));
		return;
	}

	/*
	 * A failed cmpxchg doesn't provide any memory-ordering guarantees,
	 * so we need a barrier to order the read of the node data in
	 * pv_unhash *after* we've read the lock being _Q_SLOW_VAL.
	 *
	 * Matches the cmpxchg() in pv_wait_head_or_lock() setting _Q_SLOW_VAL.
	 */
	smp_rmb();

	/*
	 * Since the above failed to release, this must be the SLOW path.
	 * Therefore start by looking up the blocked node and unhashing it.
	 */
	node = pv_unhash(lock);

	/*
	 * Now that we have a reference to the (likely) blocked pv_node,
	 * release the lock.
	 */
	smp_store_release(&l->locked, 0);

	/*
	 * At this point the memory pointed at by lock can be freed/reused,
	 * however we can still use the pv_node to kick the CPU.
	 * The other vCPU may not really be halted, but kicking an active
	 * vCPU is harmless other than the additional latency in completing
	 * the unlock.
	 */
	qstat_inc(qstat_pv_kick_unlock, true);
	pv_kick(node->cpu);
}

/*
 * 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>

#ifndef __pv_queued_spin_unlock
__visible void __pv_queued_spin_unlock(struct qspinlock *lock)
{
	struct __qspinlock *l = (void *)lock;
	u8 locked;

	/*
	 * 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.
	 */
	locked = cmpxchg(&l->locked, _Q_LOCKED_VAL, 0);
	if (likely(locked == _Q_LOCKED_VAL))
		return;

	__pv_queued_spin_unlock_slowpath(lock, locked);
}
#endif /* __pv_queued_spin_unlock */
Commit	Line	Data
a23db284 WL	1	#ifndef _GEN_PV_LOCK_SLOWPATH
	2	#error "do not include this file"
	3	#endif
	4
	5	#include <linux/hash.h>
	6	#include <linux/bootmem.h>
cba77f03	7	#include <linux/debug_locks.h>
a23db284 WL	8
	9	/*
	10	* Implement paravirt qspinlocks; the general idea is to halt the vcpus instead
	11	* of spinning them.
	12	*
	13	* This relies on the architecture to provide two paravirt hypercalls:
	14	*
	15	* pv_wait(u8 ptr, u8 val) -- suspends the vcpu if ptr == val
	16	* pv_kick(cpu) -- wakes a suspended vcpu
	17	*
	18	* Using these we implement __pv_queued_spin_lock_slowpath() and
	19	* __pv_queued_spin_unlock() to replace native_queued_spin_lock_slowpath() and
	20	* native_queued_spin_unlock().
	21	*/
	22
	23	#define _Q_SLOW_VAL (3U << _Q_LOCKED_OFFSET)
	24
cd0272fa WL	25	/*
	26	* Queue Node Adaptive Spinning
	27	*
	28	* A queue node vCPU will stop spinning if the vCPU in the previous node is
	29	* not running. The one lock stealing attempt allowed at slowpath entry
	30	* mitigates the slight slowdown for non-overcommitted guest with this
	31	* aggressive wait-early mechanism.
	32	*
	33	* The status of the previous node will be checked at fixed interval
	34	* controlled by PV_PREV_CHECK_MASK. This is to ensure that we won't
	35	* pound on the cacheline of the previous node too heavily.
	36	*/
	37	#define PV_PREV_CHECK_MASK 0xff
	38
75d22702 WL	39	/*
	40	* Queue node uses: vcpu_running & vcpu_halted.
	41	* Queue head uses: vcpu_running & vcpu_hashed.
	42	*/
a23db284 WL	43	enum vcpu_state {
a23db284 WL	44	vcpu_running = 0,
75d22702 WL	45	vcpu_halted, /* Used only in pv_wait_node */
75d22702 WL	46	vcpu_hashed, /* = pv_hash'ed + vcpu_halted */
a23db284 WL	47	};
	48
	49	struct pv_node {
	50	struct mcs_spinlock mcs;
	51	struct mcs_spinlock __res[3];
	52
	53	int cpu;
	54	u8 state;
	55	};
	56
eaff0e70 WL	57	/*
	58	* Include queued spinlock statistics code
	59	*/
	60	#include "qspinlock_stat.h"
	61
1c4941fd WL	62	/*
	63	* By replacing the regular queued_spin_trylock() with the function below,
	64	* it will be called once when a lock waiter enter the PV slowpath before
	65	* being queued. By allowing one lock stealing attempt here when the pending
	66	* bit is off, it helps to reduce the performance impact of lock waiter
	67	* preemption without the drawback of lock starvation.
	68	*/
	69	#define queued_spin_trylock(l) pv_queued_spin_steal_lock(l)
	70	static inline bool pv_queued_spin_steal_lock(struct qspinlock *lock)
	71	{
	72	struct __qspinlock l = (void )lock;
eaff0e70 WL	73	int ret = !(atomic_read(&lock->val) & _Q_LOCKED_PENDING_MASK) &&
eaff0e70 WL	74	(cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0);
1c4941fd	75
eaff0e70 WL	76	qstat_inc(qstat_pv_lock_stealing, ret);
eaff0e70 WL	77	return ret;
1c4941fd WL	78	}
	79
	80	/*
	81	* The pending bit is used by the queue head vCPU to indicate that it
	82	* is actively spinning on the lock and no lock stealing is allowed.
	83	*/
	84	#if _Q_PENDING_BITS == 8
	85	static __always_inline void set_pending(struct qspinlock *lock)
	86	{
	87	struct __qspinlock l = (void )lock;
	88
	89	WRITE_ONCE(l->pending, 1);
	90	}
	91
	92	static __always_inline void clear_pending(struct qspinlock *lock)
	93	{
	94	struct __qspinlock l = (void )lock;
	95
	96	WRITE_ONCE(l->pending, 0);
	97	}
	98
	99	/*
	100	* The pending bit check in pv_queued_spin_steal_lock() isn't a memory
	101	* barrier. Therefore, an atomic cmpxchg() is used to acquire the lock
	102	* just to be sure that it will get it.
	103	*/
	104	static __always_inline int trylock_clear_pending(struct qspinlock *lock)
	105	{
	106	struct __qspinlock l = (void )lock;
	107
	108	return !READ_ONCE(l->locked) &&
	109	(cmpxchg(&l->locked_pending, _Q_PENDING_VAL, _Q_LOCKED_VAL)
	110	== _Q_PENDING_VAL);
	111	}
	112	#else /* _Q_PENDING_BITS == 8 */
	113	static __always_inline void set_pending(struct qspinlock *lock)
	114	{
	115	atomic_set_mask(_Q_PENDING_VAL, &lock->val);
	116	}
	117
	118	static __always_inline void clear_pending(struct qspinlock *lock)
	119	{
	120	atomic_clear_mask(_Q_PENDING_VAL, &lock->val);
	121	}
	122
	123	static __always_inline int trylock_clear_pending(struct qspinlock *lock)
	124	{
	125	int val = atomic_read(&lock->val);
	126
	127	for (;;) {
	128	int old, new;
	129
	130	if (val & _Q_LOCKED_MASK)
	131	break;
	132
	133	/*
	134	* Try to clear pending bit & set locked bit
	135	*/
	136	old = val;
	137	new = (val & ~_Q_PENDING_MASK) \| _Q_LOCKED_VAL;
	138	val = atomic_cmpxchg(&lock->val, old, new);
	139
	140	if (val == old)
	141	return 1;
142	}
143	return 0;
144	}
145	#endif /* _Q_PENDING_BITS == 8 */
146
a23db284 WL	147	/*
	148	* Lock and MCS node addresses hash table for fast lookup
	149	*
	150	* Hashing is done on a per-cacheline basis to minimize the need to access
	151	* more than one cacheline.
	152	*
	153	* Dynamically allocate a hash table big enough to hold at least 4X the
	154	* number of possible cpus in the system. Allocation is done on page
	155	* granularity. So the minimum number of hash buckets should be at least
	156	* 256 (64-bit) or 512 (32-bit) to fully utilize a 4k page.
	157	*
	158	* Since we should not be holding locks from NMI context (very rare indeed) the
	159	* max load factor is 0.75, which is around the point where open addressing
	160	* breaks down.
	161	*
	162	*/
	163	struct pv_hash_entry {
	164	struct qspinlock *lock;
	165	struct pv_node *node;
	166	};
	167
	168	#define PV_HE_PER_LINE (SMP_CACHE_BYTES / sizeof(struct pv_hash_entry))
	169	#define PV_HE_MIN (PAGE_SIZE / sizeof(struct pv_hash_entry))
	170
	171	static struct pv_hash_entry *pv_lock_hash;
	172	static unsigned int pv_lock_hash_bits __read_mostly;
	173
	174	/*
	175	* Allocate memory for the PV qspinlock hash buckets
	176	*
	177	* This function should be called from the paravirt spinlock initialization
	178	* routine.
	179	*/
	180	void __init __pv_init_lock_hash(void)
	181	{
	182	int pv_hash_size = ALIGN(4 * num_possible_cpus(), PV_HE_PER_LINE);
	183
	184	if (pv_hash_size < PV_HE_MIN)
	185	pv_hash_size = PV_HE_MIN;
	186
	187	/*
	188	* Allocate space from bootmem which should be page-size aligned
	189	* and hence cacheline aligned.
	190	*/
	191	pv_lock_hash = alloc_large_system_hash("PV qspinlock",
	192	sizeof(struct pv_hash_entry),
	193	pv_hash_size, 0, HASH_EARLY,
	194	&pv_lock_hash_bits, NULL,
	195	pv_hash_size, pv_hash_size);
	196	}
	197
	198	#define for_each_hash_entry(he, offset, hash) \
	199	for (hash &= ~(PV_HE_PER_LINE - 1), he = &pv_lock_hash[hash], offset = 0; \
	200	offset < (1 << pv_lock_hash_bits); \
	201	offset++, he = &pv_lock_hash[(hash + offset) & ((1 << pv_lock_hash_bits) - 1)])
	202
	203	static struct qspinlock *pv_hash(struct qspinlock lock, struct pv_node *node)
	204	{
	205	unsigned long offset, hash = hash_ptr(lock, pv_lock_hash_bits);
	206	struct pv_hash_entry *he;
45e898b7	207	int hopcnt = 0;
a23db284 WL	208
a23db284 WL	209	for_each_hash_entry(he, offset, hash) {
45e898b7	210	hopcnt++;
a23db284 WL	211	if (!cmpxchg(&he->lock, NULL, lock)) {
a23db284 WL	212	WRITE_ONCE(he->node, node);
45e898b7	213	qstat_hop(hopcnt);
a23db284 WL	214	return &he->lock;
	215	}
	216	}
	217	/*
	218	* Hard assume there is a free entry for us.
	219	*
	220	* This is guaranteed by ensuring every blocked lock only ever consumes
	221	* a single entry, and since we only have 4 nesting levels per CPU
	222	* and allocated 4*nr_possible_cpus(), this must be so.
	223	*
	224	* The single entry is guaranteed by having the lock owner unhash
	225	* before it releases.
	226	*/
	227	BUG();
	228	}
	229
	230	static struct pv_node pv_unhash(struct qspinlock lock)
	231	{
	232	unsigned long offset, hash = hash_ptr(lock, pv_lock_hash_bits);
	233	struct pv_hash_entry *he;
	234	struct pv_node *node;
	235
	236	for_each_hash_entry(he, offset, hash) {
	237	if (READ_ONCE(he->lock) == lock) {
	238	node = READ_ONCE(he->node);
	239	WRITE_ONCE(he->lock, NULL);
	240	return node;
	241	}
	242	}
	243	/*
	244	* Hard assume we'll find an entry.
	245	*
	246	* This guarantees a limited lookup time and is itself guaranteed by
	247	* having the lock owner do the unhash -- IFF the unlock sees the
	248	* SLOW flag, there MUST be a hash entry.
	249	*/
	250	BUG();
	251	}
	252
cd0272fa WL	253	/*
	254	* Return true if when it is time to check the previous node which is not
	255	* in a running state.
	256	*/
	257	static inline bool
	258	pv_wait_early(struct pv_node *prev, int loop)
	259	{
	260
	261	if ((loop & PV_PREV_CHECK_MASK) != 0)
	262	return false;
	263
	264	return READ_ONCE(prev->state) != vcpu_running;
	265	}
	266
a23db284 WL	267	/*
	268	* Initialize the PV part of the mcs_spinlock node.
	269	*/
	270	static void pv_init_node(struct mcs_spinlock *node)
	271	{
	272	struct pv_node pn = (struct pv_node )node;
	273
	274	BUILD_BUG_ON(sizeof(struct pv_node) > 5*sizeof(struct mcs_spinlock));
	275
	276	pn->cpu = smp_processor_id();
	277	pn->state = vcpu_running;
	278	}
	279
	280	/*
	281	* Wait for node->locked to become true, halt the vcpu after a short spin.
75d22702 WL	282	* pv_kick_node() is used to set _Q_SLOW_VAL and fill in hash table on its
75d22702 WL	283	* behalf.
a23db284	284	*/
cd0272fa	285	static void pv_wait_node(struct mcs_spinlock node, struct mcs_spinlock prev)
a23db284 WL	286	{
a23db284 WL	287	struct pv_node pn = (struct pv_node )node;
cd0272fa	288	struct pv_node pp = (struct pv_node )prev;
45e898b7	289	int waitcnt = 0;
a23db284	290	int loop;
cd0272fa	291	bool wait_early;
a23db284	292
45e898b7 WL	293	/* waitcnt processing will be compiled out if !QUEUED_LOCK_STAT */
45e898b7 WL	294	for (;; waitcnt++) {
cd0272fa	295	for (wait_early = false, loop = SPIN_THRESHOLD; loop; loop--) {
a23db284 WL	296	if (READ_ONCE(node->locked))
a23db284 WL	297	return;
cd0272fa WL	298	if (pv_wait_early(pp, loop)) {
	299	wait_early = true;
	300	break;
	301	}
a23db284 WL	302	cpu_relax();
	303	}
	304
	305	/*
	306	* Order pn->state vs pn->locked thusly:
	307	*
	308	* [S] pn->state = vcpu_halted [S] next->locked = 1
	309	* MB MB
75d22702	310	* [L] pn->locked [RmW] pn->state = vcpu_hashed
a23db284	311	*
75d22702	312	* Matches the cmpxchg() from pv_kick_node().
a23db284	313	*/
b92b8b35	314	smp_store_mb(pn->state, vcpu_halted);
a23db284	315
45e898b7 WL	316	if (!READ_ONCE(node->locked)) {
	317	qstat_inc(qstat_pv_wait_node, true);
	318	qstat_inc(qstat_pv_wait_again, waitcnt);
cd0272fa	319	qstat_inc(qstat_pv_wait_early, wait_early);
a23db284	320	pv_wait(&pn->state, vcpu_halted);
45e898b7	321	}
a23db284 WL	322
a23db284 WL	323	/*
45e898b7	324	* If pv_kick_node() changed us to vcpu_hashed, retain that
1c4941fd WL	325	* value so that pv_wait_head_or_lock() knows to not also try
1c4941fd WL	326	* to hash this lock.
a23db284	327	*/
75d22702	328	cmpxchg(&pn->state, vcpu_halted, vcpu_running);
a23db284 WL	329
	330	/*
	331	* If the locked flag is still not set after wakeup, it is a
	332	* spurious wakeup and the vCPU should wait again. However,
	333	* there is a pretty high overhead for CPU halting and kicking.
	334	* So it is better to spin for a while in the hope that the
	335	* MCS lock will be released soon.
	336	*/
45e898b7	337	qstat_inc(qstat_pv_spurious_wakeup, !READ_ONCE(node->locked));
a23db284	338	}
75d22702	339
a23db284 WL	340	/*
	341	* By now our node->locked should be 1 and our caller will not actually
	342	* spin-wait for it. We do however rely on our caller to do a
	343	* load-acquire for us.
	344	*/
	345	}
	346
	347	/*
75d22702 WL	348	* Called after setting next->locked = 1 when we're the lock owner.
75d22702 WL	349	*
1c4941fd WL	350	* Instead of waking the waiters stuck in pv_wait_node() advance their state
	351	* such that they're waiting in pv_wait_head_or_lock(), this avoids a
	352	* wake/sleep cycle.
a23db284	353	*/
75d22702	354	static void pv_kick_node(struct qspinlock lock, struct mcs_spinlock node)
a23db284 WL	355	{
a23db284 WL	356	struct pv_node pn = (struct pv_node )node;
75d22702	357	struct __qspinlock l = (void )lock;
a23db284 WL	358
a23db284 WL	359	/*
75d22702 WL	360	* If the vCPU is indeed halted, advance its state to match that of
	361	* pv_wait_node(). If OTOH this fails, the vCPU was running and will
	362	* observe its next->locked value and advance itself.
a23db284	363	*
75d22702 WL	364	* Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
	365	*/
	366	if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
	367	return;
	368
	369	/*
	370	* Put the lock into the hash table and set the _Q_SLOW_VAL.
a23db284	371	*
75d22702 WL	372	* As this is the same vCPU that will check the _Q_SLOW_VAL value and
	373	* the hash table later on at unlock time, no atomic instruction is
	374	* needed.
a23db284	375	*/
75d22702 WL	376	WRITE_ONCE(l->locked, _Q_SLOW_VAL);
75d22702 WL	377	(void)pv_hash(lock, pn);
a23db284 WL	378	}
	379
	380	/*
1c4941fd WL	381	* Wait for l->locked to become clear and acquire the lock;
1c4941fd WL	382	* halt the vcpu after a short spin.
a23db284	383	* __pv_queued_spin_unlock() will wake us.
1c4941fd WL	384	*
1c4941fd WL	385	* The current value of the lock will be returned for additional processing.
a23db284	386	*/
1c4941fd WL	387	static u32
1c4941fd WL	388	pv_wait_head_or_lock(struct qspinlock lock, struct mcs_spinlock node)
a23db284 WL	389	{
	390	struct pv_node pn = (struct pv_node )node;
	391	struct __qspinlock l = (void )lock;
	392	struct qspinlock **lp = NULL;
45e898b7	393	int waitcnt = 0;
a23db284 WL	394	int loop;
a23db284 WL	395
75d22702 WL	396	/*
	397	* If pv_kick_node() already advanced our state, we don't need to
	398	* insert ourselves into the hash table anymore.
	399	*/
	400	if (READ_ONCE(pn->state) == vcpu_hashed)
	401	lp = (struct qspinlock **)1;
	402
32d62510 WL	403	/*
	404	* Tracking # of slowpath locking operations
	405	*/
	406	qstat_inc(qstat_pv_lock_slowpath, true);
	407
45e898b7	408	for (;; waitcnt++) {
cd0272fa WL	409	/*
	410	* Set correct vCPU state to be used by queue node wait-early
	411	* mechanism.
	412	*/
	413	WRITE_ONCE(pn->state, vcpu_running);
	414
1c4941fd WL	415	/*
	416	* Set the pending bit in the active lock spinning loop to
	417	* disable lock stealing before attempting to acquire the lock.
	418	*/
	419	set_pending(lock);
a23db284	420	for (loop = SPIN_THRESHOLD; loop; loop--) {
1c4941fd WL	421	if (trylock_clear_pending(lock))
1c4941fd WL	422	goto gotlock;
a23db284 WL	423	cpu_relax();
a23db284 WL	424	}
1c4941fd WL	425	clear_pending(lock);
1c4941fd WL	426
a23db284	427
a23db284 WL	428	if (!lp) { /* ONCE */
a23db284 WL	429	lp = pv_hash(lock, pn);
75d22702	430
a23db284	431	/*
3b3fdf10 WD	432	* We must hash before setting _Q_SLOW_VAL, such that
	433	* when we observe _Q_SLOW_VAL in __pv_queued_spin_unlock()
	434	* we'll be sure to be able to observe our hash entry.
a23db284	435	*
3b3fdf10 WD	436	* [S] <hash> [Rmw] l->locked == _Q_SLOW_VAL
	437	* MB RMB
	438	* [RmW] l->locked = _Q_SLOW_VAL [L] <unhash>
a23db284	439	*
3b3fdf10	440	* Matches the smp_rmb() in __pv_queued_spin_unlock().
a23db284	441	*/
1c4941fd	442	if (xchg(&l->locked, _Q_SLOW_VAL) == 0) {
a23db284	443	/*
1c4941fd WL	444	* The lock was free and now we own the lock.
	445	* Change the lock value back to _Q_LOCKED_VAL
	446	* and unhash the table.
a23db284	447	*/
1c4941fd	448	WRITE_ONCE(l->locked, _Q_LOCKED_VAL);
a23db284	449	WRITE_ONCE(*lp, NULL);
1c4941fd	450	goto gotlock;
a23db284 WL	451	}
a23db284 WL	452	}
cd0272fa	453	WRITE_ONCE(pn->state, vcpu_halted);
45e898b7 WL	454	qstat_inc(qstat_pv_wait_head, true);
45e898b7 WL	455	qstat_inc(qstat_pv_wait_again, waitcnt);
a23db284 WL	456	pv_wait(&l->locked, _Q_SLOW_VAL);
	457
	458	/*
	459	* The unlocker should have freed the lock before kicking the
	460	* CPU. So if the lock is still not free, it is a spurious
1c4941fd WL	461	* wakeup or another vCPU has stolen the lock. The current
1c4941fd WL	462	* vCPU should spin again.
a23db284	463	*/
1c4941fd	464	qstat_inc(qstat_pv_spurious_wakeup, READ_ONCE(l->locked));
a23db284 WL	465	}
	466
	467	/*
1c4941fd WL	468	* The cmpxchg() or xchg() call before coming here provides the
	469	* acquire semantics for locking. The dummy ORing of _Q_LOCKED_VAL
	470	* here is to indicate to the compiler that the value will always
	471	* be nozero to enable better code optimization.
a23db284	472	*/
1c4941fd WL	473	gotlock:
1c4941fd WL	474	return (u32)(atomic_read(&lock->val) \| _Q_LOCKED_VAL);
a23db284 WL	475	}
	476
	477	/*
d7804530 WL	478	* PV versions of the unlock fastpath and slowpath functions to be used
d7804530 WL	479	* instead of queued_spin_unlock().
a23db284	480	*/
d7804530 WL	481	__visible void
d7804530 WL	482	__pv_queued_spin_unlock_slowpath(struct qspinlock *lock, u8 locked)
a23db284 WL	483	{
	484	struct __qspinlock l = (void )lock;
	485	struct pv_node *node;
a23db284	486
0b792bf5 PZ	487	if (unlikely(locked != _Q_SLOW_VAL)) {
	488	WARN(!debug_locks_silent,
	489	"pvqspinlock: lock 0x%lx has corrupted value 0x%x!\n",
	490	(unsigned long)lock, atomic_read(&lock->val));
cba77f03 WL	491	return;
	492	}
	493
3b3fdf10 WD	494	/*
	495	* A failed cmpxchg doesn't provide any memory-ordering guarantees,
	496	* so we need a barrier to order the read of the node data in
	497	* pv_unhash after we've read the lock being _Q_SLOW_VAL.
	498	*
1c4941fd	499	* Matches the cmpxchg() in pv_wait_head_or_lock() setting _Q_SLOW_VAL.
3b3fdf10 WD	500	*/
	501	smp_rmb();
	502
a23db284 WL	503	/*
	504	* Since the above failed to release, this must be the SLOW path.
	505	* Therefore start by looking up the blocked node and unhashing it.
	506	*/
	507	node = pv_unhash(lock);
	508
	509	/*
	510	* Now that we have a reference to the (likely) blocked pv_node,
	511	* release the lock.
	512	*/
	513	smp_store_release(&l->locked, 0);
	514
	515	/*
	516	* At this point the memory pointed at by lock can be freed/reused,
	517	* however we can still use the pv_node to kick the CPU.
75d22702 WL	518	* The other vCPU may not really be halted, but kicking an active
	519	* vCPU is harmless other than the additional latency in completing
	520	* the unlock.
a23db284	521	*/
45e898b7	522	qstat_inc(qstat_pv_kick_unlock, true);
93edc8bd	523	pv_kick(node->cpu);
a23db284	524	}
d7804530	525
a23db284 WL	526	/*
	527	* Include the architecture specific callee-save thunk of the
	528	* __pv_queued_spin_unlock(). This thunk is put together with
d7804530 WL	529	* __pv_queued_spin_unlock() to make the callee-save thunk and the real unlock
	530	* function close to each other sharing consecutive instruction cachelines.
	531	* Alternatively, architecture specific version of __pv_queued_spin_unlock()
	532	* can be defined.
a23db284 WL	533	*/
	534	#include <asm/qspinlock_paravirt.h>
	535
d7804530 WL	536	#ifndef __pv_queued_spin_unlock
	537	__visible void __pv_queued_spin_unlock(struct qspinlock *lock)
	538	{
	539	struct __qspinlock l = (void )lock;
	540	u8 locked;
	541
	542	/*
	543	* We must not unlock if SLOW, because in that case we must first
	544	* unhash. Otherwise it would be possible to have multiple @lock
	545	* entries, which would be BAD.
	546	*/
	547	locked = cmpxchg(&l->locked, _Q_LOCKED_VAL, 0);
	548	if (likely(locked == _Q_LOCKED_VAL))
	549	return;
	550
	551	__pv_queued_spin_unlock_slowpath(lock, locked);
	552	}
	553	#endif /* __pv_queued_spin_unlock */