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