1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Semaphore implementation exposed to Go.
6 // Intended use is provide a sleep and wakeup
7 // primitive that can be used in the contended case
8 // of other synchronization primitives.
9 // Thus it targets the same goal as Linux's futex,
10 // but it has much simpler semantics.
12 // That is, don't think of these as semaphores.
13 // Think of them as a way to implement sleep and wakeup
14 // such that every sleep is paired with a single wakeup,
15 // even if, due to races, the wakeup happens before the sleep.
17 // See Mullender and Cox, ``Semaphores in Plan 9,''
18 // http://swtch.com/semaphore.pdf
23 "runtime/internal/atomic"
24 "runtime/internal/sys"
28 // Asynchronous semaphore for sync.Mutex.
30 // A semaRoot holds a balanced tree of sudog with distinct addresses (s.elem).
31 // Each of those sudog may in turn point (through s.waitlink) to a list
32 // of other sudogs waiting on the same address.
33 // The operations on the inner lists of sudogs with the same address
34 // are all O(1). The scanning of the top-level semaRoot list is O(log n),
35 // where n is the number of distinct addresses with goroutines blocked
36 // on them that hash to the given semaRoot.
37 // See golang.org/issue/17953 for a program that worked badly
38 // before we introduced the second level of list, and test/locklinear.go
39 // for a test that exercises this.
40 type semaRoot
struct {
42 treap
*sudog
// root of balanced tree of unique waiters.
43 nwait
uint32 // Number of waiters. Read w/o the lock.
46 // Prime to not correlate with any user patterns.
47 const semTabSize
= 251
49 var semtable
[semTabSize
]struct {
51 pad
[sys
.CacheLineSize
- unsafe
.Sizeof(semaRoot
{})]byte
54 //go:linkname sync_runtime_Semacquire sync.runtime_Semacquire
55 func sync_runtime_Semacquire(addr
*uint32) {
56 semacquire1(addr
, false, semaBlockProfile
)
59 //go:linkname poll_runtime_Semacquire internal_poll.runtime_Semacquire
60 func poll_runtime_Semacquire(addr
*uint32) {
61 semacquire1(addr
, false, semaBlockProfile
)
64 //go:linkname sync_runtime_Semrelease sync.runtime_Semrelease
65 func sync_runtime_Semrelease(addr
*uint32, handoff
bool) {
66 semrelease1(addr
, handoff
)
69 //go:linkname sync_runtime_SemacquireMutex sync.runtime_SemacquireMutex
70 func sync_runtime_SemacquireMutex(addr
*uint32, lifo
bool) {
71 semacquire1(addr
, lifo
, semaBlockProfile|semaMutexProfile
)
74 //go:linkname poll_runtime_Semrelease internal_poll.runtime_Semrelease
75 func poll_runtime_Semrelease(addr
*uint32) {
79 func readyWithTime(s
*sudog
, traceskip
int) {
80 if s
.releasetime
!= 0 {
81 s
.releasetime
= cputicks()
83 goready(s
.g
, traceskip
)
86 type semaProfileFlags
int
89 semaBlockProfile semaProfileFlags
= 1 << iota
93 // Called from runtime.
94 func semacquire(addr
*uint32) {
95 semacquire1(addr
, false, 0)
98 func semacquire1(addr
*uint32, lifo
bool, profile semaProfileFlags
) {
101 throw("semacquire not on the G stack")
105 if cansemacquire(addr
) {
110 // increment waiter count
111 // try cansemacquire one more time, return if succeeded
112 // enqueue itself as a waiter
114 // (waiter descriptor is dequeued by signaler)
116 root
:= semroot(addr
)
121 if profile
&semaBlockProfile
!= 0 && blockprofilerate
> 0 {
125 if profile
&semaMutexProfile
!= 0 && mutexprofilerate
> 0 {
133 // Add ourselves to nwait to disable "easy case" in semrelease.
134 atomic
.Xadd(&root
.nwait
, 1)
135 // Check cansemacquire to avoid missed wakeup.
136 if cansemacquire(addr
) {
137 atomic
.Xadd(&root
.nwait
, -1)
141 // Any semrelease after the cansemacquire knows we're waiting
142 // (we set nwait above), so go to sleep.
143 root
.queue(addr
, s
, lifo
)
144 goparkunlock(&root
.lock
, "semacquire", traceEvGoBlockSync
, 4)
145 if s
.ticket
!= 0 ||
cansemacquire(addr
) {
149 if s
.releasetime
> 0 {
150 blockevent(s
.releasetime
-t0
, 3)
155 func semrelease(addr
*uint32) {
156 semrelease1(addr
, false)
159 func semrelease1(addr
*uint32, handoff
bool) {
160 root
:= semroot(addr
)
163 // Easy case: no waiters?
164 // This check must happen after the xadd, to avoid a missed wakeup
165 // (see loop in semacquire).
166 if atomic
.Load(&root
.nwait
) == 0 {
170 // Harder case: search for a waiter and wake it.
172 if atomic
.Load(&root
.nwait
) == 0 {
173 // The count is already consumed by another goroutine,
174 // so no need to wake up another goroutine.
178 s
, t0
:= root
.dequeue(addr
)
180 atomic
.Xadd(&root
.nwait
, -1)
183 if s
!= nil { // May be slow, so unlock first
184 acquiretime
:= s
.acquiretime
185 if acquiretime
!= 0 {
186 mutexevent(t0
-acquiretime
, 3)
189 throw("corrupted semaphore ticket")
191 if handoff
&& cansemacquire(addr
) {
198 func semroot(addr
*uint32) *semaRoot
{
199 return &semtable
[(uintptr(unsafe
.Pointer(addr
))>>3)%semTabSize
].root
202 func cansemacquire(addr
*uint32) bool {
204 v
:= atomic
.Load(addr
)
208 if atomic
.Cas(addr
, v
, v
-1) {
214 // queue adds s to the blocked goroutines in semaRoot.
215 func (root
*semaRoot
) queue(addr
*uint32, s
*sudog
, lifo
bool) {
217 s
.elem
= unsafe
.Pointer(addr
)
223 for t
:= *pt
; t
!= nil; t
= *pt
{
224 if t
.elem
== unsafe
.Pointer(addr
) {
225 // Already have addr in list.
227 // Substitute s in t's place in treap.
230 s
.acquiretime
= t
.acquiretime
240 // Add t first in s's wait list.
242 s
.waittail
= t
.waittail
243 if s
.waittail
== nil {
251 // Add s to end of t's wait list.
252 if t
.waittail
== nil {
255 t
.waittail
.waitlink
= s
263 if uintptr(unsafe
.Pointer(addr
)) < uintptr(t
.elem
) {
270 // Add s as new leaf in tree of unique addrs.
271 // The balanced tree is a treap using ticket as the random heap priority.
272 // That is, it is a binary tree ordered according to the elem addresses,
273 // but then among the space of possible binary trees respecting those
274 // addresses, it is kept balanced on average by maintaining a heap ordering
275 // on the ticket: s.ticket <= both s.prev.ticket and s.next.ticket.
276 // https://en.wikipedia.org/wiki/Treap
277 // http://faculty.washington.edu/aragon/pubs/rst89.pdf
279 // s.ticket compared with zero in couple of places, therefore set lowest bit.
280 // It will not affect treap's quality noticeably.
281 s
.ticket
= fastrand() |
1
285 // Rotate up into tree according to ticket (priority).
286 for s
.parent
!= nil && s
.parent
.ticket
> s
.ticket
{
287 if s
.parent
.prev
== s
{
288 root
.rotateRight(s
.parent
)
290 if s
.parent
.next
!= s
{
291 panic("semaRoot queue")
293 root
.rotateLeft(s
.parent
)
298 // dequeue searches for and finds the first goroutine
299 // in semaRoot blocked on addr.
300 // If the sudog was being profiled, dequeue returns the time
301 // at which it was woken up as now. Otherwise now is 0.
302 func (root
*semaRoot
) dequeue(addr
*uint32) (found
*sudog
, now
int64) {
305 for ; s
!= nil; s
= *ps
{
306 if s
.elem
== unsafe
.Pointer(addr
) {
309 if uintptr(unsafe
.Pointer(addr
)) < uintptr(s
.elem
) {
319 if s
.acquiretime
!= 0 {
322 if t
:= s
.waitlink
; t
!= nil {
323 // Substitute t, also waiting on addr, for s in root tree of unique addrs.
335 if t
.waitlink
!= nil {
336 t
.waittail
= s
.waittail
344 // Rotate s down to be leaf of tree for removal, respecting priorities.
345 for s
.next
!= nil || s
.prev
!= nil {
346 if s
.next
== nil || s
.prev
!= nil && s
.prev
.ticket
< s
.next
.ticket
{
352 // Remove s, now a leaf.
354 if s
.parent
.prev
== s
{
371 // rotateLeft rotates the tree rooted at node x.
372 // turning (x a (y b c)) into (y (x a b) c).
373 func (root
*semaRoot
) rotateLeft(x
*sudog
) {
374 // p -> (x a (y b c))
376 a
, y
:= x
.prev
, x
.next
377 b
, c
:= y
.prev
, y
.next
397 } else if p
.prev
== x
{
401 throw("semaRoot rotateLeft")
407 // rotateRight rotates the tree rooted at node y.
408 // turning (y (x a b) c) into (x a (y b c)).
409 func (root
*semaRoot
) rotateRight(y
*sudog
) {
410 // p -> (y (x a b) c)
412 x
, c
:= y
.prev
, y
.next
413 a
, b
:= x
.prev
, x
.next
433 } else if p
.prev
== y
{
437 throw("semaRoot rotateRight")
443 // notifyList is a ticket-based notification list used to implement sync.Cond.
445 // It must be kept in sync with the sync package.
446 type notifyList
struct {
447 // wait is the ticket number of the next waiter. It is atomically
448 // incremented outside the lock.
451 // notify is the ticket number of the next waiter to be notified. It can
452 // be read outside the lock, but is only written to with lock held.
454 // Both wait & notify can wrap around, and such cases will be correctly
455 // handled as long as their "unwrapped" difference is bounded by 2^31.
456 // For this not to be the case, we'd need to have 2^31+ goroutines
457 // blocked on the same condvar, which is currently not possible.
460 // List of parked waiters.
466 // less checks if a < b, considering a & b running counts that may overflow the
467 // 32-bit range, and that their "unwrapped" difference is always less than 2^31.
468 func less(a
, b
uint32) bool {
469 return int32(a
-b
) < 0
472 // notifyListAdd adds the caller to a notify list such that it can receive
473 // notifications. The caller must eventually call notifyListWait to wait for
474 // such a notification, passing the returned ticket number.
475 //go:linkname notifyListAdd sync.runtime_notifyListAdd
476 func notifyListAdd(l
*notifyList
) uint32 {
477 // This may be called concurrently, for example, when called from
478 // sync.Cond.Wait while holding a RWMutex in read mode.
479 return atomic
.Xadd(&l
.wait
, 1) - 1
482 // notifyListWait waits for a notification. If one has been sent since
483 // notifyListAdd was called, it returns immediately. Otherwise, it blocks.
484 //go:linkname notifyListWait sync.runtime_notifyListWait
485 func notifyListWait(l
*notifyList
, t
uint32) {
488 // Return right away if this ticket has already been notified.
489 if less(t
, l
.notify
) {
500 if blockprofilerate
> 0 {
510 goparkunlock(&l
.lock
, "semacquire", traceEvGoBlockCond
, 3)
512 blockevent(s
.releasetime
-t0
, 2)
517 // notifyListNotifyAll notifies all entries in the list.
518 //go:linkname notifyListNotifyAll sync.runtime_notifyListNotifyAll
519 func notifyListNotifyAll(l
*notifyList
) {
520 // Fast-path: if there are no new waiters since the last notification
521 // we don't need to acquire the lock.
522 if atomic
.Load(&l
.wait
) == atomic
.Load(&l
.notify
) {
526 // Pull the list out into a local variable, waiters will be readied
533 // Update the next ticket to be notified. We can set it to the current
534 // value of wait because any previous waiters are already in the list
535 // or will notice that they have already been notified when trying to
536 // add themselves to the list.
537 atomic
.Store(&l
.notify
, atomic
.Load(&l
.wait
))
540 // Go through the local list and ready all waiters.
549 // notifyListNotifyOne notifies one entry in the list.
550 //go:linkname notifyListNotifyOne sync.runtime_notifyListNotifyOne
551 func notifyListNotifyOne(l
*notifyList
) {
552 // Fast-path: if there are no new waiters since the last notification
553 // we don't need to acquire the lock at all.
554 if atomic
.Load(&l
.wait
) == atomic
.Load(&l
.notify
) {
560 // Re-check under the lock if we need to do anything.
562 if t
== atomic
.Load(&l
.wait
) {
567 // Update the next notify ticket number.
568 atomic
.Store(&l
.notify
, t
+1)
570 // Try to find the g that needs to be notified.
571 // If it hasn't made it to the list yet we won't find it,
572 // but it won't park itself once it sees the new notify number.
574 // This scan looks linear but essentially always stops quickly.
575 // Because g's queue separately from taking numbers,
576 // there may be minor reorderings in the list, but we
577 // expect the g we're looking for to be near the front.
578 // The g has others in front of it on the list only to the
579 // extent that it lost the race, so the iteration will not
580 // be too long. This applies even when the g is missing:
581 // it hasn't yet gotten to sleep and has lost the race to
582 // the (few) other g's that we find on the list.
583 for p
, s
:= (*sudog
)(nil), l
.head
; s
!= nil; p
, s
= s
, s
.next
{
603 //go:linkname notifyListCheck sync.runtime_notifyListCheck
604 func notifyListCheck(sz
uintptr) {
605 if sz
!= unsafe
.Sizeof(notifyList
{}) {
606 print("runtime: bad notifyList size - sync=", sz
, " runtime=", unsafe
.Sizeof(notifyList
{}), "\n")
607 throw("bad notifyList size")
611 //go:linkname sync_nanotime sync.runtime_nanotime
612 func sync_nanotime() int64 {