Source file
src/runtime/sema.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package runtime
21
22 import (
23 "internal/cpu"
24 "runtime/internal/atomic"
25 "unsafe"
26 )
27
28
29
30
31
32
33
34
35
36
37
38
39
40 type semaRoot struct {
41 lock mutex
42 treap *sudog
43 nwait uint32
44 }
45
46
47 const semTabSize = 251
48
49 var semtable [semTabSize]struct {
50 root semaRoot
51 pad [cpu.CacheLinePadSize - unsafe.Sizeof(semaRoot{})]byte
52 }
53
54
55 func sync_runtime_Semacquire(addr *uint32) {
56 semacquire1(addr, false, semaBlockProfile, 0)
57 }
58
59
60 func poll_runtime_Semacquire(addr *uint32) {
61 semacquire1(addr, false, semaBlockProfile, 0)
62 }
63
64
65 func sync_runtime_Semrelease(addr *uint32, handoff bool, skipframes int) {
66 semrelease1(addr, handoff, skipframes)
67 }
68
69
70 func sync_runtime_SemacquireMutex(addr *uint32, lifo bool, skipframes int) {
71 semacquire1(addr, lifo, semaBlockProfile|semaMutexProfile, skipframes)
72 }
73
74
75 func poll_runtime_Semrelease(addr *uint32) {
76 semrelease(addr)
77 }
78
79 func readyWithTime(s *sudog, traceskip int) {
80 if s.releasetime != 0 {
81 s.releasetime = cputicks()
82 }
83 goready(s.g, traceskip)
84 }
85
86 type semaProfileFlags int
87
88 const (
89 semaBlockProfile semaProfileFlags = 1 << iota
90 semaMutexProfile
91 )
92
93
94 func semacquire(addr *uint32) {
95 semacquire1(addr, false, 0, 0)
96 }
97
98 func semacquire1(addr *uint32, lifo bool, profile semaProfileFlags, skipframes int) {
99 gp := getg()
100 if gp != gp.m.curg {
101 throw("semacquire not on the G stack")
102 }
103
104
105 if cansemacquire(addr) {
106 return
107 }
108
109
110
111
112
113
114
115 s := acquireSudog()
116 root := semroot(addr)
117 t0 := int64(0)
118 s.releasetime = 0
119 s.acquiretime = 0
120 s.ticket = 0
121 if profile&semaBlockProfile != 0 && blockprofilerate > 0 {
122 t0 = cputicks()
123 s.releasetime = -1
124 }
125 if profile&semaMutexProfile != 0 && mutexprofilerate > 0 {
126 if t0 == 0 {
127 t0 = cputicks()
128 }
129 s.acquiretime = t0
130 }
131 for {
132 lockWithRank(&root.lock, lockRankRoot)
133
134 atomic.Xadd(&root.nwait, 1)
135
136 if cansemacquire(addr) {
137 atomic.Xadd(&root.nwait, -1)
138 unlock(&root.lock)
139 break
140 }
141
142
143 root.queue(addr, s, lifo)
144 goparkunlock(&root.lock, waitReasonSemacquire, traceEvGoBlockSync, 4+skipframes)
145 if s.ticket != 0 || cansemacquire(addr) {
146 break
147 }
148 }
149 if s.releasetime > 0 {
150 blockevent(s.releasetime-t0, 3+skipframes)
151 }
152 releaseSudog(s)
153 }
154
155 func semrelease(addr *uint32) {
156 semrelease1(addr, false, 0)
157 }
158
159 func semrelease1(addr *uint32, handoff bool, skipframes int) {
160 root := semroot(addr)
161 atomic.Xadd(addr, 1)
162
163
164
165
166 if atomic.Load(&root.nwait) == 0 {
167 return
168 }
169
170
171 lockWithRank(&root.lock, lockRankRoot)
172 if atomic.Load(&root.nwait) == 0 {
173
174
175 unlock(&root.lock)
176 return
177 }
178 s, t0 := root.dequeue(addr)
179 if s != nil {
180 atomic.Xadd(&root.nwait, -1)
181 }
182 unlock(&root.lock)
183 if s != nil {
184 acquiretime := s.acquiretime
185 if acquiretime != 0 {
186 mutexevent(t0-acquiretime, 3+skipframes)
187 }
188 if s.ticket != 0 {
189 throw("corrupted semaphore ticket")
190 }
191 if handoff && cansemacquire(addr) {
192 s.ticket = 1
193 }
194 readyWithTime(s, 5+skipframes)
195 if s.ticket == 1 && getg().m.locks == 0 {
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212 goyield()
213 }
214 }
215 }
216
217 func semroot(addr *uint32) *semaRoot {
218 return &semtable[(uintptr(unsafe.Pointer(addr))>>3)%semTabSize].root
219 }
220
221 func cansemacquire(addr *uint32) bool {
222 for {
223 v := atomic.Load(addr)
224 if v == 0 {
225 return false
226 }
227 if atomic.Cas(addr, v, v-1) {
228 return true
229 }
230 }
231 }
232
233
234 func (root *semaRoot) queue(addr *uint32, s *sudog, lifo bool) {
235 s.g = getg()
236 s.elem = unsafe.Pointer(addr)
237 s.next = nil
238 s.prev = nil
239
240 var last *sudog
241 pt := &root.treap
242 for t := *pt; t != nil; t = *pt {
243 if t.elem == unsafe.Pointer(addr) {
244
245 if lifo {
246
247 *pt = s
248 s.ticket = t.ticket
249 s.acquiretime = t.acquiretime
250 s.parent = t.parent
251 s.prev = t.prev
252 s.next = t.next
253 if s.prev != nil {
254 s.prev.parent = s
255 }
256 if s.next != nil {
257 s.next.parent = s
258 }
259
260 s.waitlink = t
261 s.waittail = t.waittail
262 if s.waittail == nil {
263 s.waittail = t
264 }
265 t.parent = nil
266 t.prev = nil
267 t.next = nil
268 t.waittail = nil
269 } else {
270
271 if t.waittail == nil {
272 t.waitlink = s
273 } else {
274 t.waittail.waitlink = s
275 }
276 t.waittail = s
277 s.waitlink = nil
278 }
279 return
280 }
281 last = t
282 if uintptr(unsafe.Pointer(addr)) < uintptr(t.elem) {
283 pt = &t.prev
284 } else {
285 pt = &t.next
286 }
287 }
288
289
290
291
292
293
294
295
296
297
298
299
300 s.ticket = fastrand() | 1
301 s.parent = last
302 *pt = s
303
304
305 for s.parent != nil && s.parent.ticket > s.ticket {
306 if s.parent.prev == s {
307 root.rotateRight(s.parent)
308 } else {
309 if s.parent.next != s {
310 panic("semaRoot queue")
311 }
312 root.rotateLeft(s.parent)
313 }
314 }
315 }
316
317
318
319
320
321 func (root *semaRoot) dequeue(addr *uint32) (found *sudog, now int64) {
322 ps := &root.treap
323 s := *ps
324 for ; s != nil; s = *ps {
325 if s.elem == unsafe.Pointer(addr) {
326 goto Found
327 }
328 if uintptr(unsafe.Pointer(addr)) < uintptr(s.elem) {
329 ps = &s.prev
330 } else {
331 ps = &s.next
332 }
333 }
334 return nil, 0
335
336 Found:
337 now = int64(0)
338 if s.acquiretime != 0 {
339 now = cputicks()
340 }
341 if t := s.waitlink; t != nil {
342
343 *ps = t
344 t.ticket = s.ticket
345 t.parent = s.parent
346 t.prev = s.prev
347 if t.prev != nil {
348 t.prev.parent = t
349 }
350 t.next = s.next
351 if t.next != nil {
352 t.next.parent = t
353 }
354 if t.waitlink != nil {
355 t.waittail = s.waittail
356 } else {
357 t.waittail = nil
358 }
359 t.acquiretime = now
360 s.waitlink = nil
361 s.waittail = nil
362 } else {
363
364 for s.next != nil || s.prev != nil {
365 if s.next == nil || s.prev != nil && s.prev.ticket < s.next.ticket {
366 root.rotateRight(s)
367 } else {
368 root.rotateLeft(s)
369 }
370 }
371
372 if s.parent != nil {
373 if s.parent.prev == s {
374 s.parent.prev = nil
375 } else {
376 s.parent.next = nil
377 }
378 } else {
379 root.treap = nil
380 }
381 }
382 s.parent = nil
383 s.elem = nil
384 s.next = nil
385 s.prev = nil
386 s.ticket = 0
387 return s, now
388 }
389
390
391
392 func (root *semaRoot) rotateLeft(x *sudog) {
393
394 p := x.parent
395 y := x.next
396 b := y.prev
397
398 y.prev = x
399 x.parent = y
400 x.next = b
401 if b != nil {
402 b.parent = x
403 }
404
405 y.parent = p
406 if p == nil {
407 root.treap = y
408 } else if p.prev == x {
409 p.prev = y
410 } else {
411 if p.next != x {
412 throw("semaRoot rotateLeft")
413 }
414 p.next = y
415 }
416 }
417
418
419
420 func (root *semaRoot) rotateRight(y *sudog) {
421
422 p := y.parent
423 x := y.prev
424 b := x.next
425
426 x.next = y
427 y.parent = x
428 y.prev = b
429 if b != nil {
430 b.parent = y
431 }
432
433 x.parent = p
434 if p == nil {
435 root.treap = x
436 } else if p.prev == y {
437 p.prev = x
438 } else {
439 if p.next != y {
440 throw("semaRoot rotateRight")
441 }
442 p.next = x
443 }
444 }
445
446
447
448
449 type notifyList struct {
450
451
452 wait uint32
453
454
455
456
457
458
459
460
461 notify uint32
462
463
464 lock mutex
465 head *sudog
466 tail *sudog
467 }
468
469
470
471 func less(a, b uint32) bool {
472 return int32(a-b) < 0
473 }
474
475
476
477
478
479 func notifyListAdd(l *notifyList) uint32 {
480
481
482 return atomic.Xadd(&l.wait, 1) - 1
483 }
484
485
486
487
488 func notifyListWait(l *notifyList, t uint32) {
489 lockWithRank(&l.lock, lockRankNotifyList)
490
491
492 if less(t, l.notify) {
493 unlock(&l.lock)
494 return
495 }
496
497
498 s := acquireSudog()
499 s.g = getg()
500 s.ticket = t
501 s.releasetime = 0
502 t0 := int64(0)
503 if blockprofilerate > 0 {
504 t0 = cputicks()
505 s.releasetime = -1
506 }
507 if l.tail == nil {
508 l.head = s
509 } else {
510 l.tail.next = s
511 }
512 l.tail = s
513 goparkunlock(&l.lock, waitReasonSyncCondWait, traceEvGoBlockCond, 3)
514 if t0 != 0 {
515 blockevent(s.releasetime-t0, 2)
516 }
517 releaseSudog(s)
518 }
519
520
521
522 func notifyListNotifyAll(l *notifyList) {
523
524
525 if atomic.Load(&l.wait) == atomic.Load(&l.notify) {
526 return
527 }
528
529
530
531 lockWithRank(&l.lock, lockRankNotifyList)
532 s := l.head
533 l.head = nil
534 l.tail = nil
535
536
537
538
539
540 atomic.Store(&l.notify, atomic.Load(&l.wait))
541 unlock(&l.lock)
542
543
544 for s != nil {
545 next := s.next
546 s.next = nil
547 readyWithTime(s, 4)
548 s = next
549 }
550 }
551
552
553
554 func notifyListNotifyOne(l *notifyList) {
555
556
557 if atomic.Load(&l.wait) == atomic.Load(&l.notify) {
558 return
559 }
560
561 lockWithRank(&l.lock, lockRankNotifyList)
562
563
564 t := l.notify
565 if t == atomic.Load(&l.wait) {
566 unlock(&l.lock)
567 return
568 }
569
570
571 atomic.Store(&l.notify, t+1)
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586 for p, s := (*sudog)(nil), l.head; s != nil; p, s = s, s.next {
587 if s.ticket == t {
588 n := s.next
589 if p != nil {
590 p.next = n
591 } else {
592 l.head = n
593 }
594 if n == nil {
595 l.tail = p
596 }
597 unlock(&l.lock)
598 s.next = nil
599 readyWithTime(s, 4)
600 return
601 }
602 }
603 unlock(&l.lock)
604 }
605
606
607 func notifyListCheck(sz uintptr) {
608 if sz != unsafe.Sizeof(notifyList{}) {
609 print("runtime: bad notifyList size - sync=", sz, " runtime=", unsafe.Sizeof(notifyList{}), "\n")
610 throw("bad notifyList size")
611 }
612 }
613
614
615 func sync_nanotime() int64 {
616 return nanotime()
617 }
618
View as plain text