qspinlock.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /*
  3. * Queued spinlock
  4. *
  5. * (C) Copyright 2013-2015 Hewlett-Packard Development Company, L.P.
  6. * (C) Copyright 2013-2014,2018 Red Hat, Inc.
  7. * (C) Copyright 2015 Intel Corp.
  8. * (C) Copyright 2015 Hewlett-Packard Enterprise Development LP
  9. *
  10. * Authors: Waiman Long <[email protected]>
  11. * Peter Zijlstra <[email protected]>
  12. */
  13. #ifndef _GEN_PV_LOCK_SLOWPATH
  14. #include <linux/smp.h>
  15. #include <linux/bug.h>
  16. #include <linux/cpumask.h>
  17. #include <linux/percpu.h>
  18. #include <linux/hardirq.h>
  19. #include <linux/mutex.h>
  20. #include <linux/prefetch.h>
  21. #include <asm/byteorder.h>
  22. #include <asm/qspinlock.h>
  23. #include <trace/events/lock.h>
  24. /*
  25. * Include queued spinlock statistics code
  26. */
  27. #include "qspinlock_stat.h"
  28. /*
  29. * The basic principle of a queue-based spinlock can best be understood
  30. * by studying a classic queue-based spinlock implementation called the
  31. * MCS lock. A copy of the original MCS lock paper ("Algorithms for Scalable
  32. * Synchronization on Shared-Memory Multiprocessors by Mellor-Crummey and
  33. * Scott") is available at
  34. *
  35. * https://bugzilla.kernel.org/show_bug.cgi?id=206115
  36. *
  37. * This queued spinlock implementation is based on the MCS lock, however to
  38. * make it fit the 4 bytes we assume spinlock_t to be, and preserve its
  39. * existing API, we must modify it somehow.
  40. *
  41. * In particular; where the traditional MCS lock consists of a tail pointer
  42. * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
  43. * unlock the next pending (next->locked), we compress both these: {tail,
  44. * next->locked} into a single u32 value.
  45. *
  46. * Since a spinlock disables recursion of its own context and there is a limit
  47. * to the contexts that can nest; namely: task, softirq, hardirq, nmi. As there
  48. * are at most 4 nesting levels, it can be encoded by a 2-bit number. Now
  49. * we can encode the tail by combining the 2-bit nesting level with the cpu
  50. * number. With one byte for the lock value and 3 bytes for the tail, only a
  51. * 32-bit word is now needed. Even though we only need 1 bit for the lock,
  52. * we extend it to a full byte to achieve better performance for architectures
  53. * that support atomic byte write.
  54. *
  55. * We also change the first spinner to spin on the lock bit instead of its
  56. * node; whereby avoiding the need to carry a node from lock to unlock, and
  57. * preserving existing lock API. This also makes the unlock code simpler and
  58. * faster.
  59. *
  60. * N.B. The current implementation only supports architectures that allow
  61. * atomic operations on smaller 8-bit and 16-bit data types.
  62. *
  63. */
  64. #include "mcs_spinlock.h"
  65. #define MAX_NODES 4
  66. /*
  67. * On 64-bit architectures, the mcs_spinlock structure will be 16 bytes in
  68. * size and four of them will fit nicely in one 64-byte cacheline. For
  69. * pvqspinlock, however, we need more space for extra data. To accommodate
  70. * that, we insert two more long words to pad it up to 32 bytes. IOW, only
  71. * two of them can fit in a cacheline in this case. That is OK as it is rare
  72. * to have more than 2 levels of slowpath nesting in actual use. We don't
  73. * want to penalize pvqspinlocks to optimize for a rare case in native
  74. * qspinlocks.
  75. */
  76. struct qnode {
  77. struct mcs_spinlock mcs;
  78. #ifdef CONFIG_PARAVIRT_SPINLOCKS
  79. long reserved[2];
  80. #endif
  81. };
  82. /*
  83. * The pending bit spinning loop count.
  84. * This heuristic is used to limit the number of lockword accesses
  85. * made by atomic_cond_read_relaxed when waiting for the lock to
  86. * transition out of the "== _Q_PENDING_VAL" state. We don't spin
  87. * indefinitely because there's no guarantee that we'll make forward
  88. * progress.
  89. */
  90. #ifndef _Q_PENDING_LOOPS
  91. #define _Q_PENDING_LOOPS 1
  92. #endif
  93. /*
  94. * Per-CPU queue node structures; we can never have more than 4 nested
  95. * contexts: task, softirq, hardirq, nmi.
  96. *
  97. * Exactly fits one 64-byte cacheline on a 64-bit architecture.
  98. *
  99. * PV doubles the storage and uses the second cacheline for PV state.
  100. */
  101. static DEFINE_PER_CPU_ALIGNED(struct qnode, qnodes[MAX_NODES]);
  102. /*
  103. * We must be able to distinguish between no-tail and the tail at 0:0,
  104. * therefore increment the cpu number by one.
  105. */
  106. static inline __pure u32 encode_tail(int cpu, int idx)
  107. {
  108. u32 tail;
  109. tail = (cpu + 1) << _Q_TAIL_CPU_OFFSET;
  110. tail |= idx << _Q_TAIL_IDX_OFFSET; /* assume < 4 */
  111. return tail;
  112. }
  113. static inline __pure struct mcs_spinlock *decode_tail(u32 tail)
  114. {
  115. int cpu = (tail >> _Q_TAIL_CPU_OFFSET) - 1;
  116. int idx = (tail & _Q_TAIL_IDX_MASK) >> _Q_TAIL_IDX_OFFSET;
  117. return per_cpu_ptr(&qnodes[idx].mcs, cpu);
  118. }
  119. static inline __pure
  120. struct mcs_spinlock *grab_mcs_node(struct mcs_spinlock *base, int idx)
  121. {
  122. return &((struct qnode *)base + idx)->mcs;
  123. }
  124. #define _Q_LOCKED_PENDING_MASK (_Q_LOCKED_MASK | _Q_PENDING_MASK)
  125. #if _Q_PENDING_BITS == 8
  126. /**
  127. * clear_pending - clear the pending bit.
  128. * @lock: Pointer to queued spinlock structure
  129. *
  130. * *,1,* -> *,0,*
  131. */
  132. static __always_inline void clear_pending(struct qspinlock *lock)
  133. {
  134. WRITE_ONCE(lock->pending, 0);
  135. }
  136. /**
  137. * clear_pending_set_locked - take ownership and clear the pending bit.
  138. * @lock: Pointer to queued spinlock structure
  139. *
  140. * *,1,0 -> *,0,1
  141. *
  142. * Lock stealing is not allowed if this function is used.
  143. */
  144. static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
  145. {
  146. WRITE_ONCE(lock->locked_pending, _Q_LOCKED_VAL);
  147. }
  148. /*
  149. * xchg_tail - Put in the new queue tail code word & retrieve previous one
  150. * @lock : Pointer to queued spinlock structure
  151. * @tail : The new queue tail code word
  152. * Return: The previous queue tail code word
  153. *
  154. * xchg(lock, tail), which heads an address dependency
  155. *
  156. * p,*,* -> n,*,* ; prev = xchg(lock, node)
  157. */
  158. static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
  159. {
  160. /*
  161. * We can use relaxed semantics since the caller ensures that the
  162. * MCS node is properly initialized before updating the tail.
  163. */
  164. return (u32)xchg_relaxed(&lock->tail,
  165. tail >> _Q_TAIL_OFFSET) << _Q_TAIL_OFFSET;
  166. }
  167. #else /* _Q_PENDING_BITS == 8 */
  168. /**
  169. * clear_pending - clear the pending bit.
  170. * @lock: Pointer to queued spinlock structure
  171. *
  172. * *,1,* -> *,0,*
  173. */
  174. static __always_inline void clear_pending(struct qspinlock *lock)
  175. {
  176. atomic_andnot(_Q_PENDING_VAL, &lock->val);
  177. }
  178. /**
  179. * clear_pending_set_locked - take ownership and clear the pending bit.
  180. * @lock: Pointer to queued spinlock structure
  181. *
  182. * *,1,0 -> *,0,1
  183. */
  184. static __always_inline void clear_pending_set_locked(struct qspinlock *lock)
  185. {
  186. atomic_add(-_Q_PENDING_VAL + _Q_LOCKED_VAL, &lock->val);
  187. }
  188. /**
  189. * xchg_tail - Put in the new queue tail code word & retrieve previous one
  190. * @lock : Pointer to queued spinlock structure
  191. * @tail : The new queue tail code word
  192. * Return: The previous queue tail code word
  193. *
  194. * xchg(lock, tail)
  195. *
  196. * p,*,* -> n,*,* ; prev = xchg(lock, node)
  197. */
  198. static __always_inline u32 xchg_tail(struct qspinlock *lock, u32 tail)
  199. {
  200. u32 old, new, val = atomic_read(&lock->val);
  201. for (;;) {
  202. new = (val & _Q_LOCKED_PENDING_MASK) | tail;
  203. /*
  204. * We can use relaxed semantics since the caller ensures that
  205. * the MCS node is properly initialized before updating the
  206. * tail.
  207. */
  208. old = atomic_cmpxchg_relaxed(&lock->val, val, new);
  209. if (old == val)
  210. break;
  211. val = old;
  212. }
  213. return old;
  214. }
  215. #endif /* _Q_PENDING_BITS == 8 */
  216. /**
  217. * queued_fetch_set_pending_acquire - fetch the whole lock value and set pending
  218. * @lock : Pointer to queued spinlock structure
  219. * Return: The previous lock value
  220. *
  221. * *,*,* -> *,1,*
  222. */
  223. #ifndef queued_fetch_set_pending_acquire
  224. static __always_inline u32 queued_fetch_set_pending_acquire(struct qspinlock *lock)
  225. {
  226. return atomic_fetch_or_acquire(_Q_PENDING_VAL, &lock->val);
  227. }
  228. #endif
  229. /**
  230. * set_locked - Set the lock bit and own the lock
  231. * @lock: Pointer to queued spinlock structure
  232. *
  233. * *,*,0 -> *,0,1
  234. */
  235. static __always_inline void set_locked(struct qspinlock *lock)
  236. {
  237. WRITE_ONCE(lock->locked, _Q_LOCKED_VAL);
  238. }
  239. /*
  240. * Generate the native code for queued_spin_unlock_slowpath(); provide NOPs for
  241. * all the PV callbacks.
  242. */
  243. static __always_inline void __pv_init_node(struct mcs_spinlock *node) { }
  244. static __always_inline void __pv_wait_node(struct mcs_spinlock *node,
  245. struct mcs_spinlock *prev) { }
  246. static __always_inline void __pv_kick_node(struct qspinlock *lock,
  247. struct mcs_spinlock *node) { }
  248. static __always_inline u32 __pv_wait_head_or_lock(struct qspinlock *lock,
  249. struct mcs_spinlock *node)
  250. { return 0; }
  251. #define pv_enabled() false
  252. #define pv_init_node __pv_init_node
  253. #define pv_wait_node __pv_wait_node
  254. #define pv_kick_node __pv_kick_node
  255. #define pv_wait_head_or_lock __pv_wait_head_or_lock
  256. #ifdef CONFIG_PARAVIRT_SPINLOCKS
  257. #define queued_spin_lock_slowpath native_queued_spin_lock_slowpath
  258. #endif
  259. #endif /* _GEN_PV_LOCK_SLOWPATH */
  260. /**
  261. * queued_spin_lock_slowpath - acquire the queued spinlock
  262. * @lock: Pointer to queued spinlock structure
  263. * @val: Current value of the queued spinlock 32-bit word
  264. *
  265. * (queue tail, pending bit, lock value)
  266. *
  267. * fast : slow : unlock
  268. * : :
  269. * uncontended (0,0,0) -:--> (0,0,1) ------------------------------:--> (*,*,0)
  270. * : | ^--------.------. / :
  271. * : v \ \ | :
  272. * pending : (0,1,1) +--> (0,1,0) \ | :
  273. * : | ^--' | | :
  274. * : v | | :
  275. * uncontended : (n,x,y) +--> (n,0,0) --' | :
  276. * queue : | ^--' | :
  277. * : v | :
  278. * contended : (*,x,y) +--> (*,0,0) ---> (*,0,1) -' :
  279. * queue : ^--' :
  280. */
  281. void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
  282. {
  283. struct mcs_spinlock *prev, *next, *node;
  284. u32 old, tail;
  285. int idx;
  286. BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
  287. if (pv_enabled())
  288. goto pv_queue;
  289. if (virt_spin_lock(lock))
  290. return;
  291. /*
  292. * Wait for in-progress pending->locked hand-overs with a bounded
  293. * number of spins so that we guarantee forward progress.
  294. *
  295. * 0,1,0 -> 0,0,1
  296. */
  297. if (val == _Q_PENDING_VAL) {
  298. int cnt = _Q_PENDING_LOOPS;
  299. val = atomic_cond_read_relaxed(&lock->val,
  300. (VAL != _Q_PENDING_VAL) || !cnt--);
  301. }
  302. /*
  303. * If we observe any contention; queue.
  304. */
  305. if (val & ~_Q_LOCKED_MASK)
  306. goto queue;
  307. /*
  308. * trylock || pending
  309. *
  310. * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
  311. */
  312. val = queued_fetch_set_pending_acquire(lock);
  313. /*
  314. * If we observe contention, there is a concurrent locker.
  315. *
  316. * Undo and queue; our setting of PENDING might have made the
  317. * n,0,0 -> 0,0,0 transition fail and it will now be waiting
  318. * on @next to become !NULL.
  319. */
  320. if (unlikely(val & ~_Q_LOCKED_MASK)) {
  321. /* Undo PENDING if we set it. */
  322. if (!(val & _Q_PENDING_MASK))
  323. clear_pending(lock);
  324. goto queue;
  325. }
  326. /*
  327. * We're pending, wait for the owner to go away.
  328. *
  329. * 0,1,1 -> 0,1,0
  330. *
  331. * this wait loop must be a load-acquire such that we match the
  332. * store-release that clears the locked bit and create lock
  333. * sequentiality; this is because not all
  334. * clear_pending_set_locked() implementations imply full
  335. * barriers.
  336. */
  337. if (val & _Q_LOCKED_MASK)
  338. atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_MASK));
  339. /*
  340. * take ownership and clear the pending bit.
  341. *
  342. * 0,1,0 -> 0,0,1
  343. */
  344. clear_pending_set_locked(lock);
  345. lockevent_inc(lock_pending);
  346. return;
  347. /*
  348. * End of pending bit optimistic spinning and beginning of MCS
  349. * queuing.
  350. */
  351. queue:
  352. lockevent_inc(lock_slowpath);
  353. pv_queue:
  354. node = this_cpu_ptr(&qnodes[0].mcs);
  355. idx = node->count++;
  356. tail = encode_tail(smp_processor_id(), idx);
  357. trace_contention_begin(lock, LCB_F_SPIN);
  358. /*
  359. * 4 nodes are allocated based on the assumption that there will
  360. * not be nested NMIs taking spinlocks. That may not be true in
  361. * some architectures even though the chance of needing more than
  362. * 4 nodes will still be extremely unlikely. When that happens,
  363. * we fall back to spinning on the lock directly without using
  364. * any MCS node. This is not the most elegant solution, but is
  365. * simple enough.
  366. */
  367. if (unlikely(idx >= MAX_NODES)) {
  368. lockevent_inc(lock_no_node);
  369. while (!queued_spin_trylock(lock))
  370. cpu_relax();
  371. goto release;
  372. }
  373. node = grab_mcs_node(node, idx);
  374. /*
  375. * Keep counts of non-zero index values:
  376. */
  377. lockevent_cond_inc(lock_use_node2 + idx - 1, idx);
  378. /*
  379. * Ensure that we increment the head node->count before initialising
  380. * the actual node. If the compiler is kind enough to reorder these
  381. * stores, then an IRQ could overwrite our assignments.
  382. */
  383. barrier();
  384. node->locked = 0;
  385. node->next = NULL;
  386. pv_init_node(node);
  387. /*
  388. * We touched a (possibly) cold cacheline in the per-cpu queue node;
  389. * attempt the trylock once more in the hope someone let go while we
  390. * weren't watching.
  391. */
  392. if (queued_spin_trylock(lock))
  393. goto release;
  394. /*
  395. * Ensure that the initialisation of @node is complete before we
  396. * publish the updated tail via xchg_tail() and potentially link
  397. * @node into the waitqueue via WRITE_ONCE(prev->next, node) below.
  398. */
  399. smp_wmb();
  400. /*
  401. * Publish the updated tail.
  402. * We have already touched the queueing cacheline; don't bother with
  403. * pending stuff.
  404. *
  405. * p,*,* -> n,*,*
  406. */
  407. old = xchg_tail(lock, tail);
  408. next = NULL;
  409. /*
  410. * if there was a previous node; link it and wait until reaching the
  411. * head of the waitqueue.
  412. */
  413. if (old & _Q_TAIL_MASK) {
  414. prev = decode_tail(old);
  415. /* Link @node into the waitqueue. */
  416. WRITE_ONCE(prev->next, node);
  417. pv_wait_node(node, prev);
  418. arch_mcs_spin_lock_contended(&node->locked);
  419. /*
  420. * While waiting for the MCS lock, the next pointer may have
  421. * been set by another lock waiter. We optimistically load
  422. * the next pointer & prefetch the cacheline for writing
  423. * to reduce latency in the upcoming MCS unlock operation.
  424. */
  425. next = READ_ONCE(node->next);
  426. if (next)
  427. prefetchw(next);
  428. }
  429. /*
  430. * we're at the head of the waitqueue, wait for the owner & pending to
  431. * go away.
  432. *
  433. * *,x,y -> *,0,0
  434. *
  435. * this wait loop must use a load-acquire such that we match the
  436. * store-release that clears the locked bit and create lock
  437. * sequentiality; this is because the set_locked() function below
  438. * does not imply a full barrier.
  439. *
  440. * The PV pv_wait_head_or_lock function, if active, will acquire
  441. * the lock and return a non-zero value. So we have to skip the
  442. * atomic_cond_read_acquire() call. As the next PV queue head hasn't
  443. * been designated yet, there is no way for the locked value to become
  444. * _Q_SLOW_VAL. So both the set_locked() and the
  445. * atomic_cmpxchg_relaxed() calls will be safe.
  446. *
  447. * If PV isn't active, 0 will be returned instead.
  448. *
  449. */
  450. if ((val = pv_wait_head_or_lock(lock, node)))
  451. goto locked;
  452. val = atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK));
  453. locked:
  454. /*
  455. * claim the lock:
  456. *
  457. * n,0,0 -> 0,0,1 : lock, uncontended
  458. * *,*,0 -> *,*,1 : lock, contended
  459. *
  460. * If the queue head is the only one in the queue (lock value == tail)
  461. * and nobody is pending, clear the tail code and grab the lock.
  462. * Otherwise, we only need to grab the lock.
  463. */
  464. /*
  465. * In the PV case we might already have _Q_LOCKED_VAL set, because
  466. * of lock stealing; therefore we must also allow:
  467. *
  468. * n,0,1 -> 0,0,1
  469. *
  470. * Note: at this point: (val & _Q_PENDING_MASK) == 0, because of the
  471. * above wait condition, therefore any concurrent setting of
  472. * PENDING will make the uncontended transition fail.
  473. */
  474. if ((val & _Q_TAIL_MASK) == tail) {
  475. if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
  476. goto release; /* No contention */
  477. }
  478. /*
  479. * Either somebody is queued behind us or _Q_PENDING_VAL got set
  480. * which will then detect the remaining tail and queue behind us
  481. * ensuring we'll see a @next.
  482. */
  483. set_locked(lock);
  484. /*
  485. * contended path; wait for next if not observed yet, release.
  486. */
  487. if (!next)
  488. next = smp_cond_load_relaxed(&node->next, (VAL));
  489. arch_mcs_spin_unlock_contended(&next->locked);
  490. pv_kick_node(lock, next);
  491. release:
  492. trace_contention_end(lock, 0);
  493. /*
  494. * release the node
  495. */
  496. __this_cpu_dec(qnodes[0].mcs.count);
  497. }
  498. EXPORT_SYMBOL(queued_spin_lock_slowpath);
  499. /*
  500. * Generate the paravirt code for queued_spin_unlock_slowpath().
  501. */
  502. #if !defined(_GEN_PV_LOCK_SLOWPATH) && defined(CONFIG_PARAVIRT_SPINLOCKS)
  503. #define _GEN_PV_LOCK_SLOWPATH
  504. #undef pv_enabled
  505. #define pv_enabled() true
  506. #undef pv_init_node
  507. #undef pv_wait_node
  508. #undef pv_kick_node
  509. #undef pv_wait_head_or_lock
  510. #undef queued_spin_lock_slowpath
  511. #define queued_spin_lock_slowpath __pv_queued_spin_lock_slowpath
  512. #include "qspinlock_paravirt.h"
  513. #include "qspinlock.c"
  514. bool nopvspin __initdata;
  515. static __init int parse_nopvspin(char *arg)
  516. {
  517. nopvspin = true;
  518. return 0;
  519. }
  520. early_param("nopvspin", parse_nopvspin);
  521. #endif