vlocks.rst 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
  1. ======================================
  2. vlocks for Bare-Metal Mutual Exclusion
  3. ======================================
  4. Voting Locks, or "vlocks" provide a simple low-level mutual exclusion
  5. mechanism, with reasonable but minimal requirements on the memory
  6. system.
  7. These are intended to be used to coordinate critical activity among CPUs
  8. which are otherwise non-coherent, in situations where the hardware
  9. provides no other mechanism to support this and ordinary spinlocks
  10. cannot be used.
  11. vlocks make use of the atomicity provided by the memory system for
  12. writes to a single memory location. To arbitrate, every CPU "votes for
  13. itself", by storing a unique number to a common memory location. The
  14. final value seen in that memory location when all the votes have been
  15. cast identifies the winner.
  16. In order to make sure that the election produces an unambiguous result
  17. in finite time, a CPU will only enter the election in the first place if
  18. no winner has been chosen and the election does not appear to have
  19. started yet.
  20. Algorithm
  21. ---------
  22. The easiest way to explain the vlocks algorithm is with some pseudo-code::
  23. int currently_voting[NR_CPUS] = { 0, };
  24. int last_vote = -1; /* no votes yet */
  25. bool vlock_trylock(int this_cpu)
  26. {
  27. /* signal our desire to vote */
  28. currently_voting[this_cpu] = 1;
  29. if (last_vote != -1) {
  30. /* someone already volunteered himself */
  31. currently_voting[this_cpu] = 0;
  32. return false; /* not ourself */
  33. }
  34. /* let's suggest ourself */
  35. last_vote = this_cpu;
  36. currently_voting[this_cpu] = 0;
  37. /* then wait until everyone else is done voting */
  38. for_each_cpu(i) {
  39. while (currently_voting[i] != 0)
  40. /* wait */;
  41. }
  42. /* result */
  43. if (last_vote == this_cpu)
  44. return true; /* we won */
  45. return false;
  46. }
  47. bool vlock_unlock(void)
  48. {
  49. last_vote = -1;
  50. }
  51. The currently_voting[] array provides a way for the CPUs to determine
  52. whether an election is in progress, and plays a role analogous to the
  53. "entering" array in Lamport's bakery algorithm [1].
  54. However, once the election has started, the underlying memory system
  55. atomicity is used to pick the winner. This avoids the need for a static
  56. priority rule to act as a tie-breaker, or any counters which could
  57. overflow.
  58. As long as the last_vote variable is globally visible to all CPUs, it
  59. will contain only one value that won't change once every CPU has cleared
  60. its currently_voting flag.
  61. Features and limitations
  62. ------------------------
  63. * vlocks are not intended to be fair. In the contended case, it is the
  64. _last_ CPU which attempts to get the lock which will be most likely
  65. to win.
  66. vlocks are therefore best suited to situations where it is necessary
  67. to pick a unique winner, but it does not matter which CPU actually
  68. wins.
  69. * Like other similar mechanisms, vlocks will not scale well to a large
  70. number of CPUs.
  71. vlocks can be cascaded in a voting hierarchy to permit better scaling
  72. if necessary, as in the following hypothetical example for 4096 CPUs::
  73. /* first level: local election */
  74. my_town = towns[(this_cpu >> 4) & 0xf];
  75. I_won = vlock_trylock(my_town, this_cpu & 0xf);
  76. if (I_won) {
  77. /* we won the town election, let's go for the state */
  78. my_state = states[(this_cpu >> 8) & 0xf];
  79. I_won = vlock_lock(my_state, this_cpu & 0xf));
  80. if (I_won) {
  81. /* and so on */
  82. I_won = vlock_lock(the_whole_country, this_cpu & 0xf];
  83. if (I_won) {
  84. /* ... */
  85. }
  86. vlock_unlock(the_whole_country);
  87. }
  88. vlock_unlock(my_state);
  89. }
  90. vlock_unlock(my_town);
  91. ARM implementation
  92. ------------------
  93. The current ARM implementation [2] contains some optimisations beyond
  94. the basic algorithm:
  95. * By packing the members of the currently_voting array close together,
  96. we can read the whole array in one transaction (providing the number
  97. of CPUs potentially contending the lock is small enough). This
  98. reduces the number of round-trips required to external memory.
  99. In the ARM implementation, this means that we can use a single load
  100. and comparison::
  101. LDR Rt, [Rn]
  102. CMP Rt, #0
  103. ...in place of code equivalent to::
  104. LDRB Rt, [Rn]
  105. CMP Rt, #0
  106. LDRBEQ Rt, [Rn, #1]
  107. CMPEQ Rt, #0
  108. LDRBEQ Rt, [Rn, #2]
  109. CMPEQ Rt, #0
  110. LDRBEQ Rt, [Rn, #3]
  111. CMPEQ Rt, #0
  112. This cuts down on the fast-path latency, as well as potentially
  113. reducing bus contention in contended cases.
  114. The optimisation relies on the fact that the ARM memory system
  115. guarantees coherency between overlapping memory accesses of
  116. different sizes, similarly to many other architectures. Note that
  117. we do not care which element of currently_voting appears in which
  118. bits of Rt, so there is no need to worry about endianness in this
  119. optimisation.
  120. If there are too many CPUs to read the currently_voting array in
  121. one transaction then multiple transations are still required. The
  122. implementation uses a simple loop of word-sized loads for this
  123. case. The number of transactions is still fewer than would be
  124. required if bytes were loaded individually.
  125. In principle, we could aggregate further by using LDRD or LDM, but
  126. to keep the code simple this was not attempted in the initial
  127. implementation.
  128. * vlocks are currently only used to coordinate between CPUs which are
  129. unable to enable their caches yet. This means that the
  130. implementation removes many of the barriers which would be required
  131. when executing the algorithm in cached memory.
  132. packing of the currently_voting array does not work with cached
  133. memory unless all CPUs contending the lock are cache-coherent, due
  134. to cache writebacks from one CPU clobbering values written by other
  135. CPUs. (Though if all the CPUs are cache-coherent, you should be
  136. probably be using proper spinlocks instead anyway).
  137. * The "no votes yet" value used for the last_vote variable is 0 (not
  138. -1 as in the pseudocode). This allows statically-allocated vlocks
  139. to be implicitly initialised to an unlocked state simply by putting
  140. them in .bss.
  141. An offset is added to each CPU's ID for the purpose of setting this
  142. variable, so that no CPU uses the value 0 for its ID.
  143. Colophon
  144. --------
  145. Originally created and documented by Dave Martin for Linaro Limited, for
  146. use in ARM-based big.LITTLE platforms, with review and input gratefully
  147. received from Nicolas Pitre and Achin Gupta. Thanks to Nicolas for
  148. grabbing most of this text out of the relevant mail thread and writing
  149. up the pseudocode.
  150. Copyright (C) 2012-2013 Linaro Limited
  151. Distributed under the terms of Version 2 of the GNU General Public
  152. License, as defined in linux/COPYING.
  153. References
  154. ----------
  155. [1] Lamport, L. "A New Solution of Dijkstra's Concurrent Programming
  156. Problem", Communications of the ACM 17, 8 (August 1974), 453-455.
  157. https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm
  158. [2] linux/arch/arm/common/vlock.S, www.kernel.org.