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. 4 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. 11 // 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. 16 // 17 // See Mullender and Cox, ``Semaphores in Plan 9,'' 18 // http://swtch.com/semaphore.pdf 19 20 package runtime 21 22 import "unsafe" 23 24 // Asynchronous semaphore for sync.Mutex. 25 26 type semaRoot struct { 27 lock mutex 28 head *sudog 29 tail *sudog 30 nwait uint32 // Number of waiters. Read w/o the lock. 31 } 32 33 // Prime to not correlate with any user patterns. 34 const semTabSize = 251 35 36 var semtable [semTabSize]struct { 37 root semaRoot 38 pad [_CacheLineSize - unsafe.Sizeof(semaRoot{})]byte 39 } 40 41 //go:linkname sync_runtime_Semacquire sync.runtime_Semacquire 42 func sync_runtime_Semacquire(addr *uint32) { 43 semacquire(addr, true) 44 } 45 46 //go:linkname net_runtime_Semacquire net.runtime_Semacquire 47 func net_runtime_Semacquire(addr *uint32) { 48 semacquire(addr, true) 49 } 50 51 //go:linkname sync_runtime_Semrelease sync.runtime_Semrelease 52 func sync_runtime_Semrelease(addr *uint32) { 53 semrelease(addr) 54 } 55 56 //go:linkname net_runtime_Semrelease net.runtime_Semrelease 57 func net_runtime_Semrelease(addr *uint32) { 58 semrelease(addr) 59 } 60 61 // Called from runtime. 62 func semacquire(addr *uint32, profile bool) { 63 gp := getg() 64 if gp != gp.m.curg { 65 throw("semacquire not on the G stack") 66 } 67 68 // Easy case. 69 if cansemacquire(addr) { 70 return 71 } 72 73 // Harder case: 74 // increment waiter count 75 // try cansemacquire one more time, return if succeeded 76 // enqueue itself as a waiter 77 // sleep 78 // (waiter descriptor is dequeued by signaler) 79 s := acquireSudog() 80 root := semroot(addr) 81 t0 := int64(0) 82 s.releasetime = 0 83 if profile && blockprofilerate > 0 { 84 t0 = cputicks() 85 s.releasetime = -1 86 } 87 for { 88 lock(&root.lock) 89 // Add ourselves to nwait to disable "easy case" in semrelease. 90 xadd(&root.nwait, 1) 91 // Check cansemacquire to avoid missed wakeup. 92 if cansemacquire(addr) { 93 xadd(&root.nwait, -1) 94 unlock(&root.lock) 95 break 96 } 97 // Any semrelease after the cansemacquire knows we're waiting 98 // (we set nwait above), so go to sleep. 99 root.queue(addr, s) 100 goparkunlock(&root.lock, "semacquire", traceEvGoBlockSync, 4) 101 if cansemacquire(addr) { 102 break 103 } 104 } 105 if s.releasetime > 0 { 106 blockevent(int64(s.releasetime)-t0, 3) 107 } 108 releaseSudog(s) 109 } 110 111 func semrelease(addr *uint32) { 112 root := semroot(addr) 113 xadd(addr, 1) 114 115 // Easy case: no waiters? 116 // This check must happen after the xadd, to avoid a missed wakeup 117 // (see loop in semacquire). 118 if atomicload(&root.nwait) == 0 { 119 return 120 } 121 122 // Harder case: search for a waiter and wake it. 123 lock(&root.lock) 124 if atomicload(&root.nwait) == 0 { 125 // The count is already consumed by another goroutine, 126 // so no need to wake up another goroutine. 127 unlock(&root.lock) 128 return 129 } 130 s := root.head 131 for ; s != nil; s = s.next { 132 if s.elem == unsafe.Pointer(addr) { 133 xadd(&root.nwait, -1) 134 root.dequeue(s) 135 break 136 } 137 } 138 unlock(&root.lock) 139 if s != nil { 140 if s.releasetime != 0 { 141 s.releasetime = cputicks() 142 } 143 goready(s.g, 4) 144 } 145 } 146 147 func semroot(addr *uint32) *semaRoot { 148 return &semtable[(uintptr(unsafe.Pointer(addr))>>3)%semTabSize].root 149 } 150 151 func cansemacquire(addr *uint32) bool { 152 for { 153 v := atomicload(addr) 154 if v == 0 { 155 return false 156 } 157 if cas(addr, v, v-1) { 158 return true 159 } 160 } 161 } 162 163 func (root *semaRoot) queue(addr *uint32, s *sudog) { 164 s.g = getg() 165 s.elem = unsafe.Pointer(addr) 166 s.next = nil 167 s.prev = root.tail 168 if root.tail != nil { 169 root.tail.next = s 170 } else { 171 root.head = s 172 } 173 root.tail = s 174 } 175 176 func (root *semaRoot) dequeue(s *sudog) { 177 if s.next != nil { 178 s.next.prev = s.prev 179 } else { 180 root.tail = s.prev 181 } 182 if s.prev != nil { 183 s.prev.next = s.next 184 } else { 185 root.head = s.next 186 } 187 s.elem = nil 188 s.next = nil 189 s.prev = nil 190 } 191 192 // Synchronous semaphore for sync.Cond. 193 type syncSema struct { 194 lock mutex 195 head *sudog 196 tail *sudog 197 } 198 199 // syncsemacquire waits for a pairing syncsemrelease on the same semaphore s. 200 //go:linkname syncsemacquire sync.runtime_Syncsemacquire 201 func syncsemacquire(s *syncSema) { 202 lock(&s.lock) 203 if s.head != nil && s.head.nrelease > 0 { 204 // Have pending release, consume it. 205 var wake *sudog 206 s.head.nrelease-- 207 if s.head.nrelease == 0 { 208 wake = s.head 209 s.head = wake.next 210 if s.head == nil { 211 s.tail = nil 212 } 213 } 214 unlock(&s.lock) 215 if wake != nil { 216 wake.next = nil 217 goready(wake.g, 4) 218 } 219 } else { 220 // Enqueue itself. 221 w := acquireSudog() 222 w.g = getg() 223 w.nrelease = -1 224 w.next = nil 225 w.releasetime = 0 226 t0 := int64(0) 227 if blockprofilerate > 0 { 228 t0 = cputicks() 229 w.releasetime = -1 230 } 231 if s.tail == nil { 232 s.head = w 233 } else { 234 s.tail.next = w 235 } 236 s.tail = w 237 goparkunlock(&s.lock, "semacquire", traceEvGoBlockCond, 3) 238 if t0 != 0 { 239 blockevent(int64(w.releasetime)-t0, 2) 240 } 241 releaseSudog(w) 242 } 243 } 244 245 // syncsemrelease waits for n pairing syncsemacquire on the same semaphore s. 246 //go:linkname syncsemrelease sync.runtime_Syncsemrelease 247 func syncsemrelease(s *syncSema, n uint32) { 248 lock(&s.lock) 249 for n > 0 && s.head != nil && s.head.nrelease < 0 { 250 // Have pending acquire, satisfy it. 251 wake := s.head 252 s.head = wake.next 253 if s.head == nil { 254 s.tail = nil 255 } 256 if wake.releasetime != 0 { 257 wake.releasetime = cputicks() 258 } 259 wake.next = nil 260 goready(wake.g, 4) 261 n-- 262 } 263 if n > 0 { 264 // enqueue itself 265 w := acquireSudog() 266 w.g = getg() 267 w.nrelease = int32(n) 268 w.next = nil 269 w.releasetime = 0 270 if s.tail == nil { 271 s.head = w 272 } else { 273 s.tail.next = w 274 } 275 s.tail = w 276 goparkunlock(&s.lock, "semarelease", traceEvGoBlockCond, 3) 277 releaseSudog(w) 278 } else { 279 unlock(&s.lock) 280 } 281 } 282 283 //go:linkname syncsemcheck sync.runtime_Syncsemcheck 284 func syncsemcheck(sz uintptr) { 285 if sz != unsafe.Sizeof(syncSema{}) { 286 print("runtime: bad syncSema size - sync=", sz, " runtime=", unsafe.Sizeof(syncSema{}), "\n") 287 throw("bad syncSema size") 288 } 289 } 290
