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