qspinlock_paravirt.h 16 KB

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