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