Source file
src/runtime/time.go
Documentation: runtime
1
2
3
4
5
6
7 package runtime
8
9 import (
10 "runtime/internal/atomic"
11 "runtime/internal/sys"
12 "unsafe"
13 )
14
15
16
17 type timer struct {
18
19
20
21 pp puintptr
22
23
24
25
26 when int64
27 period int64
28 f func(interface{}, uintptr)
29 arg interface{}
30 seq uintptr
31
32
33 nextwhen int64
34
35
36 status uint32
37 }
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117 const (
118
119 timerNoStatus = iota
120
121
122
123 timerWaiting
124
125
126
127 timerRunning
128
129
130
131 timerDeleted
132
133
134
135 timerRemoving
136
137
138
139 timerRemoved
140
141
142
143 timerModifying
144
145
146
147
148 timerModifiedEarlier
149
150
151
152
153 timerModifiedLater
154
155
156
157 timerMoving
158 )
159
160
161 const maxWhen = 1<<63 - 1
162
163
164
165 const verifyTimers = false
166
167
168
169
170
171
172
173
174 func timeSleep(ns int64) {
175 if ns <= 0 {
176 return
177 }
178
179 gp := getg()
180 t := gp.timer
181 if t == nil {
182 t = new(timer)
183 gp.timer = t
184 }
185 t.f = goroutineReady
186 t.arg = gp
187 t.nextwhen = nanotime() + ns
188 gopark(resetForSleep, unsafe.Pointer(t), waitReasonSleep, traceEvGoSleep, 1)
189 }
190
191
192
193
194
195 func resetForSleep(gp *g, ut unsafe.Pointer) bool {
196 t := (*timer)(ut)
197 resettimer(t, t.nextwhen)
198 return true
199 }
200
201
202
203 func startTimer(t *timer) {
204 if raceenabled {
205 racerelease(unsafe.Pointer(t))
206 }
207 addtimer(t)
208 }
209
210
211
212
213 func stopTimer(t *timer) bool {
214 return deltimer(t)
215 }
216
217
218
219
220 func resetTimer(t *timer, when int64) bool {
221 if raceenabled {
222 racerelease(unsafe.Pointer(t))
223 }
224 return resettimer(t, when)
225 }
226
227
228
229 func modTimer(t *timer, when, period int64, f func(interface{}, uintptr), arg interface{}, seq uintptr) {
230 modtimer(t, when, period, f, arg, seq)
231 }
232
233
234
235
236 func goroutineReady(arg interface{}, seq uintptr) {
237 goready(arg.(*g), 0)
238 }
239
240
241
242
243
244 func addtimer(t *timer) {
245
246
247 if t.when < 0 {
248 t.when = maxWhen
249 }
250 if t.status != timerNoStatus {
251 throw("addtimer called with initialized timer")
252 }
253 t.status = timerWaiting
254
255 when := t.when
256
257 pp := getg().m.p.ptr()
258 lock(&pp.timersLock)
259 cleantimers(pp)
260 doaddtimer(pp, t)
261 unlock(&pp.timersLock)
262
263 wakeNetPoller(when)
264 }
265
266
267
268 func doaddtimer(pp *p, t *timer) {
269
270
271 if netpollInited == 0 {
272 netpollGenericInit()
273 }
274
275 if t.pp != 0 {
276 throw("doaddtimer: P already set in timer")
277 }
278 t.pp.set(pp)
279 i := len(pp.timers)
280 pp.timers = append(pp.timers, t)
281 siftupTimer(pp.timers, i)
282 if t == pp.timers[0] {
283 atomic.Store64(&pp.timer0When, uint64(t.when))
284 }
285 atomic.Xadd(&pp.numTimers, 1)
286 }
287
288
289
290
291
292 func deltimer(t *timer) bool {
293 for {
294 switch s := atomic.Load(&t.status); s {
295 case timerWaiting, timerModifiedLater:
296
297
298 mp := acquirem()
299 if atomic.Cas(&t.status, s, timerModifying) {
300
301
302
303 tpp := t.pp.ptr()
304 if !atomic.Cas(&t.status, timerModifying, timerDeleted) {
305 badTimer()
306 }
307 releasem(mp)
308 atomic.Xadd(&tpp.deletedTimers, 1)
309
310 return true
311 } else {
312 releasem(mp)
313 }
314 case timerModifiedEarlier:
315
316
317 mp := acquirem()
318 if atomic.Cas(&t.status, s, timerModifying) {
319
320
321 tpp := t.pp.ptr()
322 atomic.Xadd(&tpp.adjustTimers, -1)
323 if !atomic.Cas(&t.status, timerModifying, timerDeleted) {
324 badTimer()
325 }
326 releasem(mp)
327 atomic.Xadd(&tpp.deletedTimers, 1)
328
329 return true
330 } else {
331 releasem(mp)
332 }
333 case timerDeleted, timerRemoving, timerRemoved:
334
335 return false
336 case timerRunning, timerMoving:
337
338
339 osyield()
340 case timerNoStatus:
341
342
343 return false
344 case timerModifying:
345
346
347 osyield()
348 default:
349 badTimer()
350 }
351 }
352 }
353
354
355
356
357
358 func dodeltimer(pp *p, i int) {
359 if t := pp.timers[i]; t.pp.ptr() != pp {
360 throw("dodeltimer: wrong P")
361 } else {
362 t.pp = 0
363 }
364 last := len(pp.timers) - 1
365 if i != last {
366 pp.timers[i] = pp.timers[last]
367 }
368 pp.timers[last] = nil
369 pp.timers = pp.timers[:last]
370 if i != last {
371
372
373 siftupTimer(pp.timers, i)
374 siftdownTimer(pp.timers, i)
375 }
376 if i == 0 {
377 updateTimer0When(pp)
378 }
379 atomic.Xadd(&pp.numTimers, -1)
380 }
381
382
383
384
385
386 func dodeltimer0(pp *p) {
387 if t := pp.timers[0]; t.pp.ptr() != pp {
388 throw("dodeltimer0: wrong P")
389 } else {
390 t.pp = 0
391 }
392 last := len(pp.timers) - 1
393 if last > 0 {
394 pp.timers[0] = pp.timers[last]
395 }
396 pp.timers[last] = nil
397 pp.timers = pp.timers[:last]
398 if last > 0 {
399 siftdownTimer(pp.timers, 0)
400 }
401 updateTimer0When(pp)
402 atomic.Xadd(&pp.numTimers, -1)
403 }
404
405
406
407
408 func modtimer(t *timer, when, period int64, f func(interface{}, uintptr), arg interface{}, seq uintptr) bool {
409 if when < 0 {
410 when = maxWhen
411 }
412
413 status := uint32(timerNoStatus)
414 wasRemoved := false
415 var pending bool
416 var mp *m
417 loop:
418 for {
419 switch status = atomic.Load(&t.status); status {
420 case timerWaiting, timerModifiedEarlier, timerModifiedLater:
421
422
423 mp = acquirem()
424 if atomic.Cas(&t.status, status, timerModifying) {
425 pending = true
426 break loop
427 }
428 releasem(mp)
429 case timerNoStatus, timerRemoved:
430
431
432 mp = acquirem()
433
434
435
436 if atomic.Cas(&t.status, status, timerModifying) {
437 wasRemoved = true
438 pending = false
439 break loop
440 }
441 releasem(mp)
442 case timerDeleted:
443
444
445 mp = acquirem()
446 if atomic.Cas(&t.status, status, timerModifying) {
447 atomic.Xadd(&t.pp.ptr().deletedTimers, -1)
448 pending = false
449 break loop
450 }
451 releasem(mp)
452 case timerRunning, timerRemoving, timerMoving:
453
454
455 osyield()
456 case timerModifying:
457
458
459 osyield()
460 default:
461 badTimer()
462 }
463 }
464
465 t.period = period
466 t.f = f
467 t.arg = arg
468 t.seq = seq
469
470 if wasRemoved {
471 t.when = when
472 pp := getg().m.p.ptr()
473 lock(&pp.timersLock)
474 doaddtimer(pp, t)
475 unlock(&pp.timersLock)
476 if !atomic.Cas(&t.status, timerModifying, timerWaiting) {
477 badTimer()
478 }
479 releasem(mp)
480 wakeNetPoller(when)
481 } else {
482
483
484
485
486
487 t.nextwhen = when
488
489 newStatus := uint32(timerModifiedLater)
490 if when < t.when {
491 newStatus = timerModifiedEarlier
492 }
493
494
495
496
497 adjust := int32(0)
498 if status == timerModifiedEarlier {
499 adjust--
500 }
501 if newStatus == timerModifiedEarlier {
502 adjust++
503 }
504 if adjust != 0 {
505 atomic.Xadd(&t.pp.ptr().adjustTimers, adjust)
506 }
507
508
509 if !atomic.Cas(&t.status, timerModifying, newStatus) {
510 badTimer()
511 }
512 releasem(mp)
513
514
515 if newStatus == timerModifiedEarlier {
516 wakeNetPoller(when)
517 }
518 }
519
520 return pending
521 }
522
523
524
525
526
527
528 func resettimer(t *timer, when int64) bool {
529 return modtimer(t, when, t.period, t.f, t.arg, t.seq)
530 }
531
532
533
534
535
536 func cleantimers(pp *p) {
537 gp := getg()
538 for {
539 if len(pp.timers) == 0 {
540 return
541 }
542
543
544
545
546
547 if gp.preemptStop {
548 return
549 }
550
551 t := pp.timers[0]
552 if t.pp.ptr() != pp {
553 throw("cleantimers: bad p")
554 }
555 switch s := atomic.Load(&t.status); s {
556 case timerDeleted:
557 if !atomic.Cas(&t.status, s, timerRemoving) {
558 continue
559 }
560 dodeltimer0(pp)
561 if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
562 badTimer()
563 }
564 atomic.Xadd(&pp.deletedTimers, -1)
565 case timerModifiedEarlier, timerModifiedLater:
566 if !atomic.Cas(&t.status, s, timerMoving) {
567 continue
568 }
569
570 t.when = t.nextwhen
571
572 dodeltimer0(pp)
573 doaddtimer(pp, t)
574 if s == timerModifiedEarlier {
575 atomic.Xadd(&pp.adjustTimers, -1)
576 }
577 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
578 badTimer()
579 }
580 default:
581
582 return
583 }
584 }
585 }
586
587
588
589
590
591 func moveTimers(pp *p, timers []*timer) {
592 for _, t := range timers {
593 loop:
594 for {
595 switch s := atomic.Load(&t.status); s {
596 case timerWaiting:
597 t.pp = 0
598 doaddtimer(pp, t)
599 break loop
600 case timerModifiedEarlier, timerModifiedLater:
601 if !atomic.Cas(&t.status, s, timerMoving) {
602 continue
603 }
604 t.when = t.nextwhen
605 t.pp = 0
606 doaddtimer(pp, t)
607 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
608 badTimer()
609 }
610 break loop
611 case timerDeleted:
612 if !atomic.Cas(&t.status, s, timerRemoved) {
613 continue
614 }
615 t.pp = 0
616
617 break loop
618 case timerModifying:
619
620 osyield()
621 case timerNoStatus, timerRemoved:
622
623 badTimer()
624 case timerRunning, timerRemoving, timerMoving:
625
626
627 badTimer()
628 default:
629 badTimer()
630 }
631 }
632 }
633 }
634
635
636
637
638
639
640 func adjusttimers(pp *p) {
641 if len(pp.timers) == 0 {
642 return
643 }
644 if atomic.Load(&pp.adjustTimers) == 0 {
645 if verifyTimers {
646 verifyTimerHeap(pp)
647 }
648 return
649 }
650 var moved []*timer
651 loop:
652 for i := 0; i < len(pp.timers); i++ {
653 t := pp.timers[i]
654 if t.pp.ptr() != pp {
655 throw("adjusttimers: bad p")
656 }
657 switch s := atomic.Load(&t.status); s {
658 case timerDeleted:
659 if atomic.Cas(&t.status, s, timerRemoving) {
660 dodeltimer(pp, i)
661 if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
662 badTimer()
663 }
664 atomic.Xadd(&pp.deletedTimers, -1)
665
666 i--
667 }
668 case timerModifiedEarlier, timerModifiedLater:
669 if atomic.Cas(&t.status, s, timerMoving) {
670
671 t.when = t.nextwhen
672
673
674
675
676 dodeltimer(pp, i)
677 moved = append(moved, t)
678 if s == timerModifiedEarlier {
679 if n := atomic.Xadd(&pp.adjustTimers, -1); int32(n) <= 0 {
680 break loop
681 }
682 }
683
684 i--
685 }
686 case timerNoStatus, timerRunning, timerRemoving, timerRemoved, timerMoving:
687 badTimer()
688 case timerWaiting:
689
690 case timerModifying:
691
692 osyield()
693 i--
694 default:
695 badTimer()
696 }
697 }
698
699 if len(moved) > 0 {
700 addAdjustedTimers(pp, moved)
701 }
702
703 if verifyTimers {
704 verifyTimerHeap(pp)
705 }
706 }
707
708
709
710 func addAdjustedTimers(pp *p, moved []*timer) {
711 for _, t := range moved {
712 doaddtimer(pp, t)
713 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
714 badTimer()
715 }
716 }
717 }
718
719
720
721
722
723
724
725
726 func nobarrierWakeTime(pp *p) int64 {
727 if atomic.Load(&pp.adjustTimers) > 0 {
728 return nanotime()
729 } else {
730 return int64(atomic.Load64(&pp.timer0When))
731 }
732 }
733
734
735
736
737
738
739
740
741 func runtimer(pp *p, now int64) int64 {
742 for {
743 t := pp.timers[0]
744 if t.pp.ptr() != pp {
745 throw("runtimer: bad p")
746 }
747 switch s := atomic.Load(&t.status); s {
748 case timerWaiting:
749 if t.when > now {
750
751 return t.when
752 }
753
754 if !atomic.Cas(&t.status, s, timerRunning) {
755 continue
756 }
757
758
759 runOneTimer(pp, t, now)
760 return 0
761
762 case timerDeleted:
763 if !atomic.Cas(&t.status, s, timerRemoving) {
764 continue
765 }
766 dodeltimer0(pp)
767 if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
768 badTimer()
769 }
770 atomic.Xadd(&pp.deletedTimers, -1)
771 if len(pp.timers) == 0 {
772 return -1
773 }
774
775 case timerModifiedEarlier, timerModifiedLater:
776 if !atomic.Cas(&t.status, s, timerMoving) {
777 continue
778 }
779 t.when = t.nextwhen
780 dodeltimer0(pp)
781 doaddtimer(pp, t)
782 if s == timerModifiedEarlier {
783 atomic.Xadd(&pp.adjustTimers, -1)
784 }
785 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
786 badTimer()
787 }
788
789 case timerModifying:
790
791 osyield()
792
793 case timerNoStatus, timerRemoved:
794
795 badTimer()
796 case timerRunning, timerRemoving, timerMoving:
797
798
799 badTimer()
800 default:
801 badTimer()
802 }
803 }
804 }
805
806
807
808
809
810 func runOneTimer(pp *p, t *timer, now int64) {
811 if raceenabled {
812 ppcur := getg().m.p.ptr()
813 if ppcur.timerRaceCtx == 0 {
814 ppcur.timerRaceCtx = racegostart(funcPC(runtimer) + sys.PCQuantum)
815 }
816 raceacquirectx(ppcur.timerRaceCtx, unsafe.Pointer(t))
817 }
818
819 f := t.f
820 arg := t.arg
821 seq := t.seq
822
823 if t.period > 0 {
824
825 delta := t.when - now
826 t.when += t.period * (1 + -delta/t.period)
827 siftdownTimer(pp.timers, 0)
828 if !atomic.Cas(&t.status, timerRunning, timerWaiting) {
829 badTimer()
830 }
831 updateTimer0When(pp)
832 } else {
833
834 dodeltimer0(pp)
835 if !atomic.Cas(&t.status, timerRunning, timerNoStatus) {
836 badTimer()
837 }
838 }
839
840 if raceenabled {
841
842 gp := getg()
843 if gp.racectx != 0 {
844 throw("runOneTimer: unexpected racectx")
845 }
846 gp.racectx = gp.m.p.ptr().timerRaceCtx
847 }
848
849 unlock(&pp.timersLock)
850
851 f(arg, seq)
852
853 lock(&pp.timersLock)
854
855 if raceenabled {
856 gp := getg()
857 gp.racectx = 0
858 }
859 }
860
861
862
863
864
865
866
867
868
869
870 func clearDeletedTimers(pp *p) {
871 cdel := int32(0)
872 cearlier := int32(0)
873 to := 0
874 changedHeap := false
875 timers := pp.timers
876 nextTimer:
877 for _, t := range timers {
878 for {
879 switch s := atomic.Load(&t.status); s {
880 case timerWaiting:
881 if changedHeap {
882 timers[to] = t
883 siftupTimer(timers, to)
884 }
885 to++
886 continue nextTimer
887 case timerModifiedEarlier, timerModifiedLater:
888 if atomic.Cas(&t.status, s, timerMoving) {
889 t.when = t.nextwhen
890 timers[to] = t
891 siftupTimer(timers, to)
892 to++
893 changedHeap = true
894 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
895 badTimer()
896 }
897 if s == timerModifiedEarlier {
898 cearlier++
899 }
900 continue nextTimer
901 }
902 case timerDeleted:
903 if atomic.Cas(&t.status, s, timerRemoving) {
904 t.pp = 0
905 cdel++
906 if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
907 badTimer()
908 }
909 changedHeap = true
910 continue nextTimer
911 }
912 case timerModifying:
913
914 osyield()
915 case timerNoStatus, timerRemoved:
916
917 badTimer()
918 case timerRunning, timerRemoving, timerMoving:
919
920
921 badTimer()
922 default:
923 badTimer()
924 }
925 }
926 }
927
928
929
930 for i := to; i < len(timers); i++ {
931 timers[i] = nil
932 }
933
934 atomic.Xadd(&pp.deletedTimers, -cdel)
935 atomic.Xadd(&pp.numTimers, -cdel)
936 atomic.Xadd(&pp.adjustTimers, -cearlier)
937
938 timers = timers[:to]
939 pp.timers = timers
940 updateTimer0When(pp)
941
942 if verifyTimers {
943 verifyTimerHeap(pp)
944 }
945 }
946
947
948
949
950 func verifyTimerHeap(pp *p) {
951 for i, t := range pp.timers {
952 if i == 0 {
953
954 continue
955 }
956
957
958 p := (i - 1) / 4
959 if t.when < pp.timers[p].when {
960 print("bad timer heap at ", i, ": ", p, ": ", pp.timers[p].when, ", ", i, ": ", t.when, "\n")
961 throw("bad timer heap")
962 }
963 }
964 if numTimers := int(atomic.Load(&pp.numTimers)); len(pp.timers) != numTimers {
965 println("timer heap len", len(pp.timers), "!= numTimers", numTimers)
966 throw("bad timer heap len")
967 }
968 }
969
970
971
972 func updateTimer0When(pp *p) {
973 if len(pp.timers) == 0 {
974 atomic.Store64(&pp.timer0When, 0)
975 } else {
976 atomic.Store64(&pp.timer0When, uint64(pp.timers[0].when))
977 }
978 }
979
980
981
982
983 func timeSleepUntil() (int64, *p) {
984 next := int64(maxWhen)
985 var pret *p
986
987
988 lock(&allpLock)
989 for _, pp := range allp {
990 if pp == nil {
991
992
993 continue
994 }
995
996 c := atomic.Load(&pp.adjustTimers)
997 if c == 0 {
998 w := int64(atomic.Load64(&pp.timer0When))
999 if w != 0 && w < next {
1000 next = w
1001 pret = pp
1002 }
1003 continue
1004 }
1005
1006 lock(&pp.timersLock)
1007 for _, t := range pp.timers {
1008 switch s := atomic.Load(&t.status); s {
1009 case timerWaiting:
1010 if t.when < next {
1011 next = t.when
1012 }
1013 case timerModifiedEarlier, timerModifiedLater:
1014 if t.nextwhen < next {
1015 next = t.nextwhen
1016 }
1017 if s == timerModifiedEarlier {
1018 c--
1019 }
1020 }
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033 if int32(c) <= 0 {
1034 break
1035 }
1036 }
1037 unlock(&pp.timersLock)
1038 }
1039 unlock(&allpLock)
1040
1041 return next, pret
1042 }
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052 func siftupTimer(t []*timer, i int) {
1053 if i >= len(t) {
1054 badTimer()
1055 }
1056 when := t[i].when
1057 tmp := t[i]
1058 for i > 0 {
1059 p := (i - 1) / 4
1060 if when >= t[p].when {
1061 break
1062 }
1063 t[i] = t[p]
1064 i = p
1065 }
1066 if tmp != t[i] {
1067 t[i] = tmp
1068 }
1069 }
1070
1071 func siftdownTimer(t []*timer, i int) {
1072 n := len(t)
1073 if i >= n {
1074 badTimer()
1075 }
1076 when := t[i].when
1077 tmp := t[i]
1078 for {
1079 c := i*4 + 1
1080 c3 := c + 2
1081 if c >= n {
1082 break
1083 }
1084 w := t[c].when
1085 if c+1 < n && t[c+1].when < w {
1086 w = t[c+1].when
1087 c++
1088 }
1089 if c3 < n {
1090 w3 := t[c3].when
1091 if c3+1 < n && t[c3+1].when < w3 {
1092 w3 = t[c3+1].when
1093 c3++
1094 }
1095 if w3 < w {
1096 w = w3
1097 c = c3
1098 }
1099 }
1100 if w >= when {
1101 break
1102 }
1103 t[i] = t[c]
1104 i = c
1105 }
1106 if tmp != t[i] {
1107 t[i] = tmp
1108 }
1109 }
1110
1111
1112
1113
1114
1115 func badTimer() {
1116 throw("timer data corruption")
1117 }
1118
View as plain text