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 atomic.Xadd(&tpp.adjustTimers, -1)
337 if !atomic.Cas(&t.status, timerModifying, timerDeleted) {
338 badTimer()
339 }
340 releasem(mp)
341 atomic.Xadd(&tpp.deletedTimers, 1)
342
343 return true
344 } else {
345 releasem(mp)
346 }
347 case timerDeleted, timerRemoving, timerRemoved:
348
349 return false
350 case timerRunning, timerMoving:
351
352
353 osyield()
354 case timerNoStatus:
355
356
357 return false
358 case timerModifying:
359
360
361 osyield()
362 default:
363 badTimer()
364 }
365 }
366 }
367
368
369
370
371
372 func dodeltimer(pp *p, i int) {
373 if t := pp.timers[i]; t.pp.ptr() != pp {
374 throw("dodeltimer: wrong P")
375 } else {
376 t.pp = 0
377 }
378 last := len(pp.timers) - 1
379 if i != last {
380 pp.timers[i] = pp.timers[last]
381 }
382 pp.timers[last] = nil
383 pp.timers = pp.timers[:last]
384 if i != last {
385
386
387 siftupTimer(pp.timers, i)
388 siftdownTimer(pp.timers, i)
389 }
390 if i == 0 {
391 updateTimer0When(pp)
392 }
393 atomic.Xadd(&pp.numTimers, -1)
394 }
395
396
397
398
399
400 func dodeltimer0(pp *p) {
401 if t := pp.timers[0]; t.pp.ptr() != pp {
402 throw("dodeltimer0: wrong P")
403 } else {
404 t.pp = 0
405 }
406 last := len(pp.timers) - 1
407 if last > 0 {
408 pp.timers[0] = pp.timers[last]
409 }
410 pp.timers[last] = nil
411 pp.timers = pp.timers[:last]
412 if last > 0 {
413 siftdownTimer(pp.timers, 0)
414 }
415 updateTimer0When(pp)
416 atomic.Xadd(&pp.numTimers, -1)
417 }
418
419
420
421
422 func modtimer(t *timer, when, period int64, f func(interface{}, uintptr), arg interface{}, seq uintptr) bool {
423 if when <= 0 {
424 throw("timer when must be positive")
425 }
426 if period < 0 {
427 throw("timer period must be non-negative")
428 }
429
430 status := uint32(timerNoStatus)
431 wasRemoved := false
432 var pending bool
433 var mp *m
434 loop:
435 for {
436 switch status = atomic.Load(&t.status); status {
437 case timerWaiting, timerModifiedEarlier, timerModifiedLater:
438
439
440 mp = acquirem()
441 if atomic.Cas(&t.status, status, timerModifying) {
442 pending = true
443 break loop
444 }
445 releasem(mp)
446 case timerNoStatus, timerRemoved:
447
448
449 mp = acquirem()
450
451
452
453 if atomic.Cas(&t.status, status, timerModifying) {
454 wasRemoved = true
455 pending = false
456 break loop
457 }
458 releasem(mp)
459 case timerDeleted:
460
461
462 mp = acquirem()
463 if atomic.Cas(&t.status, status, timerModifying) {
464 atomic.Xadd(&t.pp.ptr().deletedTimers, -1)
465 pending = false
466 break loop
467 }
468 releasem(mp)
469 case timerRunning, timerRemoving, timerMoving:
470
471
472 osyield()
473 case timerModifying:
474
475
476 osyield()
477 default:
478 badTimer()
479 }
480 }
481
482 t.period = period
483 t.f = f
484 t.arg = arg
485 t.seq = seq
486
487 if wasRemoved {
488 t.when = when
489 pp := getg().m.p.ptr()
490 lock(&pp.timersLock)
491 doaddtimer(pp, t)
492 unlock(&pp.timersLock)
493 if !atomic.Cas(&t.status, timerModifying, timerWaiting) {
494 badTimer()
495 }
496 releasem(mp)
497 wakeNetPoller(when)
498 } else {
499
500
501
502
503
504 t.nextwhen = when
505
506 newStatus := uint32(timerModifiedLater)
507 if when < t.when {
508 newStatus = timerModifiedEarlier
509 }
510
511 tpp := t.pp.ptr()
512
513
514
515
516 adjust := int32(0)
517 if status == timerModifiedEarlier {
518 adjust--
519 }
520 if newStatus == timerModifiedEarlier {
521 adjust++
522 updateTimerModifiedEarliest(tpp, when)
523 }
524 if adjust != 0 {
525 atomic.Xadd(&tpp.adjustTimers, adjust)
526 }
527
528
529 if !atomic.Cas(&t.status, timerModifying, newStatus) {
530 badTimer()
531 }
532 releasem(mp)
533
534
535 if newStatus == timerModifiedEarlier {
536 wakeNetPoller(when)
537 }
538 }
539
540 return pending
541 }
542
543
544
545
546
547
548 func resettimer(t *timer, when int64) bool {
549 return modtimer(t, when, t.period, t.f, t.arg, t.seq)
550 }
551
552
553
554
555
556 func cleantimers(pp *p) {
557 gp := getg()
558 for {
559 if len(pp.timers) == 0 {
560 return
561 }
562
563
564
565
566
567 if gp.preemptStop {
568 return
569 }
570
571 t := pp.timers[0]
572 if t.pp.ptr() != pp {
573 throw("cleantimers: bad p")
574 }
575 switch s := atomic.Load(&t.status); s {
576 case timerDeleted:
577 if !atomic.Cas(&t.status, s, timerRemoving) {
578 continue
579 }
580 dodeltimer0(pp)
581 if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
582 badTimer()
583 }
584 atomic.Xadd(&pp.deletedTimers, -1)
585 case timerModifiedEarlier, timerModifiedLater:
586 if !atomic.Cas(&t.status, s, timerMoving) {
587 continue
588 }
589
590 t.when = t.nextwhen
591
592 dodeltimer0(pp)
593 doaddtimer(pp, t)
594 if s == timerModifiedEarlier {
595 atomic.Xadd(&pp.adjustTimers, -1)
596 }
597 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
598 badTimer()
599 }
600 default:
601
602 return
603 }
604 }
605 }
606
607
608
609
610
611 func moveTimers(pp *p, timers []*timer) {
612 for _, t := range timers {
613 loop:
614 for {
615 switch s := atomic.Load(&t.status); s {
616 case timerWaiting:
617 if !atomic.Cas(&t.status, s, timerMoving) {
618 continue
619 }
620 t.pp = 0
621 doaddtimer(pp, t)
622 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
623 badTimer()
624 }
625 break loop
626 case timerModifiedEarlier, timerModifiedLater:
627 if !atomic.Cas(&t.status, s, timerMoving) {
628 continue
629 }
630 t.when = t.nextwhen
631 t.pp = 0
632 doaddtimer(pp, t)
633 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
634 badTimer()
635 }
636 break loop
637 case timerDeleted:
638 if !atomic.Cas(&t.status, s, timerRemoved) {
639 continue
640 }
641 t.pp = 0
642
643 break loop
644 case timerModifying:
645
646 osyield()
647 case timerNoStatus, timerRemoved:
648
649 badTimer()
650 case timerRunning, timerRemoving, timerMoving:
651
652
653 badTimer()
654 default:
655 badTimer()
656 }
657 }
658 }
659 }
660
661
662
663
664
665
666 func adjusttimers(pp *p, now int64) {
667 if atomic.Load(&pp.adjustTimers) == 0 {
668 if verifyTimers {
669 verifyTimerHeap(pp)
670 }
671
672
673
674
675 atomic.Store64(&pp.timerModifiedEarliest, 0)
676 return
677 }
678
679
680
681
682
683
684 if first := atomic.Load64(&pp.timerModifiedEarliest); first != 0 {
685 if int64(first) > now {
686 if verifyTimers {
687 verifyTimerHeap(pp)
688 }
689 return
690 }
691
692
693 atomic.Store64(&pp.timerModifiedEarliest, 0)
694 }
695
696 var moved []*timer
697 loop:
698 for i := 0; i < len(pp.timers); i++ {
699 t := pp.timers[i]
700 if t.pp.ptr() != pp {
701 throw("adjusttimers: bad p")
702 }
703 switch s := atomic.Load(&t.status); s {
704 case timerDeleted:
705 if atomic.Cas(&t.status, s, timerRemoving) {
706 dodeltimer(pp, i)
707 if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
708 badTimer()
709 }
710 atomic.Xadd(&pp.deletedTimers, -1)
711
712 i--
713 }
714 case timerModifiedEarlier, timerModifiedLater:
715 if atomic.Cas(&t.status, s, timerMoving) {
716
717 t.when = t.nextwhen
718
719
720
721
722 dodeltimer(pp, i)
723 moved = append(moved, t)
724 if s == timerModifiedEarlier {
725 if n := atomic.Xadd(&pp.adjustTimers, -1); int32(n) <= 0 {
726 break loop
727 }
728 }
729
730 i--
731 }
732 case timerNoStatus, timerRunning, timerRemoving, timerRemoved, timerMoving:
733 badTimer()
734 case timerWaiting:
735
736 case timerModifying:
737
738 osyield()
739 i--
740 default:
741 badTimer()
742 }
743 }
744
745 if len(moved) > 0 {
746 addAdjustedTimers(pp, moved)
747 }
748
749 if verifyTimers {
750 verifyTimerHeap(pp)
751 }
752 }
753
754
755
756 func addAdjustedTimers(pp *p, moved []*timer) {
757 for _, t := range moved {
758 doaddtimer(pp, t)
759 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
760 badTimer()
761 }
762 }
763 }
764
765
766
767
768
769
770 func nobarrierWakeTime(pp *p) int64 {
771 next := int64(atomic.Load64(&pp.timer0When))
772 nextAdj := int64(atomic.Load64(&pp.timerModifiedEarliest))
773 if next == 0 || (nextAdj != 0 && nextAdj < next) {
774 next = nextAdj
775 }
776 return next
777 }
778
779
780
781
782
783
784
785
786 func runtimer(pp *p, now int64) int64 {
787 for {
788 t := pp.timers[0]
789 if t.pp.ptr() != pp {
790 throw("runtimer: bad p")
791 }
792 switch s := atomic.Load(&t.status); s {
793 case timerWaiting:
794 if t.when > now {
795
796 return t.when
797 }
798
799 if !atomic.Cas(&t.status, s, timerRunning) {
800 continue
801 }
802
803
804 runOneTimer(pp, t, now)
805 return 0
806
807 case timerDeleted:
808 if !atomic.Cas(&t.status, s, timerRemoving) {
809 continue
810 }
811 dodeltimer0(pp)
812 if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
813 badTimer()
814 }
815 atomic.Xadd(&pp.deletedTimers, -1)
816 if len(pp.timers) == 0 {
817 return -1
818 }
819
820 case timerModifiedEarlier, timerModifiedLater:
821 if !atomic.Cas(&t.status, s, timerMoving) {
822 continue
823 }
824 t.when = t.nextwhen
825 dodeltimer0(pp)
826 doaddtimer(pp, t)
827 if s == timerModifiedEarlier {
828 atomic.Xadd(&pp.adjustTimers, -1)
829 }
830 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
831 badTimer()
832 }
833
834 case timerModifying:
835
836 osyield()
837
838 case timerNoStatus, timerRemoved:
839
840 badTimer()
841 case timerRunning, timerRemoving, timerMoving:
842
843
844 badTimer()
845 default:
846 badTimer()
847 }
848 }
849 }
850
851
852
853
854
855 func runOneTimer(pp *p, t *timer, now int64) {
856 if raceenabled {
857 ppcur := getg().m.p.ptr()
858 if ppcur.timerRaceCtx == 0 {
859 ppcur.timerRaceCtx = racegostart(funcPC(runtimer) + sys.PCQuantum)
860 }
861 raceacquirectx(ppcur.timerRaceCtx, unsafe.Pointer(t))
862 }
863
864 f := t.f
865 arg := t.arg
866 seq := t.seq
867
868 if t.period > 0 {
869
870 delta := t.when - now
871 t.when += t.period * (1 + -delta/t.period)
872 if t.when < 0 {
873 t.when = maxWhen
874 }
875 siftdownTimer(pp.timers, 0)
876 if !atomic.Cas(&t.status, timerRunning, timerWaiting) {
877 badTimer()
878 }
879 updateTimer0When(pp)
880 } else {
881
882 dodeltimer0(pp)
883 if !atomic.Cas(&t.status, timerRunning, timerNoStatus) {
884 badTimer()
885 }
886 }
887
888 if raceenabled {
889
890 gp := getg()
891 if gp.racectx != 0 {
892 throw("runOneTimer: unexpected racectx")
893 }
894 gp.racectx = gp.m.p.ptr().timerRaceCtx
895 }
896
897 unlock(&pp.timersLock)
898
899 f(arg, seq)
900
901 lock(&pp.timersLock)
902
903 if raceenabled {
904 gp := getg()
905 gp.racectx = 0
906 }
907 }
908
909
910
911
912
913
914
915
916
917
918 func clearDeletedTimers(pp *p) {
919
920
921 atomic.Store64(&pp.timerModifiedEarliest, 0)
922
923 cdel := int32(0)
924 cearlier := int32(0)
925 to := 0
926 changedHeap := false
927 timers := pp.timers
928 nextTimer:
929 for _, t := range timers {
930 for {
931 switch s := atomic.Load(&t.status); s {
932 case timerWaiting:
933 if changedHeap {
934 timers[to] = t
935 siftupTimer(timers, to)
936 }
937 to++
938 continue nextTimer
939 case timerModifiedEarlier, timerModifiedLater:
940 if atomic.Cas(&t.status, s, timerMoving) {
941 t.when = t.nextwhen
942 timers[to] = t
943 siftupTimer(timers, to)
944 to++
945 changedHeap = true
946 if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
947 badTimer()
948 }
949 if s == timerModifiedEarlier {
950 cearlier++
951 }
952 continue nextTimer
953 }
954 case timerDeleted:
955 if atomic.Cas(&t.status, s, timerRemoving) {
956 t.pp = 0
957 cdel++
958 if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
959 badTimer()
960 }
961 changedHeap = true
962 continue nextTimer
963 }
964 case timerModifying:
965
966 osyield()
967 case timerNoStatus, timerRemoved:
968
969 badTimer()
970 case timerRunning, timerRemoving, timerMoving:
971
972
973 badTimer()
974 default:
975 badTimer()
976 }
977 }
978 }
979
980
981
982 for i := to; i < len(timers); i++ {
983 timers[i] = nil
984 }
985
986 atomic.Xadd(&pp.deletedTimers, -cdel)
987 atomic.Xadd(&pp.numTimers, -cdel)
988 atomic.Xadd(&pp.adjustTimers, -cearlier)
989
990 timers = timers[:to]
991 pp.timers = timers
992 updateTimer0When(pp)
993
994 if verifyTimers {
995 verifyTimerHeap(pp)
996 }
997 }
998
999
1000
1001
1002 func verifyTimerHeap(pp *p) {
1003 for i, t := range pp.timers {
1004 if i == 0 {
1005
1006 continue
1007 }
1008
1009
1010 p := (i - 1) / 4
1011 if t.when < pp.timers[p].when {
1012 print("bad timer heap at ", i, ": ", p, ": ", pp.timers[p].when, ", ", i, ": ", t.when, "\n")
1013 throw("bad timer heap")
1014 }
1015 }
1016 if numTimers := int(atomic.Load(&pp.numTimers)); len(pp.timers) != numTimers {
1017 println("timer heap len", len(pp.timers), "!= numTimers", numTimers)
1018 throw("bad timer heap len")
1019 }
1020 }
1021
1022
1023
1024 func updateTimer0When(pp *p) {
1025 if len(pp.timers) == 0 {
1026 atomic.Store64(&pp.timer0When, 0)
1027 } else {
1028 atomic.Store64(&pp.timer0When, uint64(pp.timers[0].when))
1029 }
1030 }
1031
1032
1033
1034
1035 func updateTimerModifiedEarliest(pp *p, nextwhen int64) {
1036 for {
1037 old := atomic.Load64(&pp.timerModifiedEarliest)
1038 if old != 0 && int64(old) < nextwhen {
1039 return
1040 }
1041 if atomic.Cas64(&pp.timerModifiedEarliest, old, uint64(nextwhen)) {
1042 return
1043 }
1044 }
1045 }
1046
1047
1048
1049
1050 func timeSleepUntil() (int64, *p) {
1051 next := int64(maxWhen)
1052 var pret *p
1053
1054
1055 lock(&allpLock)
1056 for _, pp := range allp {
1057 if pp == nil {
1058
1059
1060 continue
1061 }
1062
1063 w := int64(atomic.Load64(&pp.timer0When))
1064 if w != 0 && w < next {
1065 next = w
1066 pret = pp
1067 }
1068
1069 w = int64(atomic.Load64(&pp.timerModifiedEarliest))
1070 if w != 0 && w < next {
1071 next = w
1072 pret = pp
1073 }
1074 }
1075 unlock(&allpLock)
1076
1077 return next, pret
1078 }
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088 func siftupTimer(t []*timer, i int) {
1089 if i >= len(t) {
1090 badTimer()
1091 }
1092 when := t[i].when
1093 if when <= 0 {
1094 badTimer()
1095 }
1096 tmp := t[i]
1097 for i > 0 {
1098 p := (i - 1) / 4
1099 if when >= t[p].when {
1100 break
1101 }
1102 t[i] = t[p]
1103 i = p
1104 }
1105 if tmp != t[i] {
1106 t[i] = tmp
1107 }
1108 }
1109
1110 func siftdownTimer(t []*timer, i int) {
1111 n := len(t)
1112 if i >= n {
1113 badTimer()
1114 }
1115 when := t[i].when
1116 if when <= 0 {
1117 badTimer()
1118 }
1119 tmp := t[i]
1120 for {
1121 c := i*4 + 1
1122 c3 := c + 2
1123 if c >= n {
1124 break
1125 }
1126 w := t[c].when
1127 if c+1 < n && t[c+1].when < w {
1128 w = t[c+1].when
1129 c++
1130 }
1131 if c3 < n {
1132 w3 := t[c3].when
1133 if c3+1 < n && t[c3+1].when < w3 {
1134 w3 = t[c3+1].when
1135 c3++
1136 }
1137 if w3 < w {
1138 w = w3
1139 c = c3
1140 }
1141 }
1142 if w >= when {
1143 break
1144 }
1145 t[i] = t[c]
1146 i = c
1147 }
1148 if tmp != t[i] {
1149 t[i] = tmp
1150 }
1151 }
1152
1153
1154
1155
1156
1157 func badTimer() {
1158 throw("timer data corruption")
1159 }
1160
View as plain text