1 // Copyright 2009 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // Time-related runtime and pieces of package time. 6 7 package runtime 8 9 import "unsafe" 10 11 // Package time knows the layout of this structure. 12 // If this struct changes, adjust ../time/sleep.go:/runtimeTimer. 13 // For GOOS=nacl, package syscall knows the layout of this structure. 14 // If this struct changes, adjust ../syscall/net_nacl.go:/runtimeTimer. 15 type timer struct { 16 i int // heap index 17 18 // Timer wakes up at when, and then at when+period, ... (period > 0 only) 19 // each time calling f(now, arg) in the timer goroutine, so f must be 20 // a well-behaved function and not block. 21 when int64 22 period int64 23 f func(interface{}, uintptr) 24 arg interface{} 25 seq uintptr 26 } 27 28 var timers struct { 29 lock mutex 30 gp *g 31 created bool 32 sleeping bool 33 rescheduling bool 34 waitnote note 35 t []*timer 36 } 37 38 // nacl fake time support - time in nanoseconds since 1970 39 var faketime int64 40 41 // Package time APIs. 42 // Godoc uses the comments in package time, not these. 43 44 // time.now is implemented in assembly. 45 46 // timeSleep puts the current goroutine to sleep for at least ns nanoseconds. 47 //go:linkname timeSleep time.Sleep 48 func timeSleep(ns int64) { 49 if ns <= 0 { 50 return 51 } 52 53 t := new(timer) 54 t.when = nanotime() + ns 55 t.f = goroutineReady 56 t.arg = getg() 57 lock(&timers.lock) 58 addtimerLocked(t) 59 goparkunlock(&timers.lock, "sleep", traceEvGoSleep, 2) 60 } 61 62 // startTimer adds t to the timer heap. 63 //go:linkname startTimer time.startTimer 64 func startTimer(t *timer) { 65 if raceenabled { 66 racerelease(unsafe.Pointer(t)) 67 } 68 addtimer(t) 69 } 70 71 // stopTimer removes t from the timer heap if it is there. 72 // It returns true if t was removed, false if t wasn't even there. 73 //go:linkname stopTimer time.stopTimer 74 func stopTimer(t *timer) bool { 75 return deltimer(t) 76 } 77 78 // Go runtime. 79 80 // Ready the goroutine arg. 81 func goroutineReady(arg interface{}, seq uintptr) { 82 goready(arg.(*g), 0) 83 } 84 85 func addtimer(t *timer) { 86 lock(&timers.lock) 87 addtimerLocked(t) 88 unlock(&timers.lock) 89 } 90 91 // Add a timer to the heap and start or kick the timer proc. 92 // If the new timer is earlier than any of the others. 93 // Timers are locked. 94 func addtimerLocked(t *timer) { 95 // when must never be negative; otherwise timerproc will overflow 96 // during its delta calculation and never expire other runtimetimers. 97 if t.when < 0 { 98 t.when = 1<<63 - 1 99 } 100 t.i = len(timers.t) 101 timers.t = append(timers.t, t) 102 siftupTimer(t.i) 103 if t.i == 0 { 104 // siftup moved to top: new earliest deadline. 105 if timers.sleeping { 106 timers.sleeping = false 107 notewakeup(&timers.waitnote) 108 } 109 if timers.rescheduling { 110 timers.rescheduling = false 111 goready(timers.gp, 0) 112 } 113 } 114 if !timers.created { 115 timers.created = true 116 go timerproc() 117 } 118 } 119 120 // Delete timer t from the heap. 121 // Do not need to update the timerproc: if it wakes up early, no big deal. 122 func deltimer(t *timer) bool { 123 // Dereference t so that any panic happens before the lock is held. 124 // Discard result, because t might be moving in the heap. 125 _ = t.i 126 127 lock(&timers.lock) 128 // t may not be registered anymore and may have 129 // a bogus i (typically 0, if generated by Go). 130 // Verify it before proceeding. 131 i := t.i 132 last := len(timers.t) - 1 133 if i < 0 || i > last || timers.t[i] != t { 134 unlock(&timers.lock) 135 return false 136 } 137 if i != last { 138 timers.t[i] = timers.t[last] 139 timers.t[i].i = i 140 } 141 timers.t[last] = nil 142 timers.t = timers.t[:last] 143 if i != last { 144 siftupTimer(i) 145 siftdownTimer(i) 146 } 147 unlock(&timers.lock) 148 return true 149 } 150 151 // Timerproc runs the time-driven events. 152 // It sleeps until the next event in the timers heap. 153 // If addtimer inserts a new earlier event, addtimer1 wakes timerproc early. 154 func timerproc() { 155 timers.gp = getg() 156 for { 157 lock(&timers.lock) 158 timers.sleeping = false 159 now := nanotime() 160 delta := int64(-1) 161 for { 162 if len(timers.t) == 0 { 163 delta = -1 164 break 165 } 166 t := timers.t[0] 167 delta = t.when - now 168 if delta > 0 { 169 break 170 } 171 if t.period > 0 { 172 // leave in heap but adjust next time to fire 173 t.when += t.period * (1 + -delta/t.period) 174 siftdownTimer(0) 175 } else { 176 // remove from heap 177 last := len(timers.t) - 1 178 if last > 0 { 179 timers.t[0] = timers.t[last] 180 timers.t[0].i = 0 181 } 182 timers.t[last] = nil 183 timers.t = timers.t[:last] 184 if last > 0 { 185 siftdownTimer(0) 186 } 187 t.i = -1 // mark as removed 188 } 189 f := t.f 190 arg := t.arg 191 seq := t.seq 192 unlock(&timers.lock) 193 if raceenabled { 194 raceacquire(unsafe.Pointer(t)) 195 } 196 f(arg, seq) 197 lock(&timers.lock) 198 } 199 if delta < 0 || faketime > 0 { 200 // No timers left - put goroutine to sleep. 201 timers.rescheduling = true 202 goparkunlock(&timers.lock, "timer goroutine (idle)", traceEvGoBlock, 1) 203 continue 204 } 205 // At least one timer pending. Sleep until then. 206 timers.sleeping = true 207 noteclear(&timers.waitnote) 208 unlock(&timers.lock) 209 notetsleepg(&timers.waitnote, delta) 210 } 211 } 212 213 func timejump() *g { 214 if faketime == 0 { 215 return nil 216 } 217 218 lock(&timers.lock) 219 if !timers.created || len(timers.t) == 0 { 220 unlock(&timers.lock) 221 return nil 222 } 223 224 var gp *g 225 if faketime < timers.t[0].when { 226 faketime = timers.t[0].when 227 if timers.rescheduling { 228 timers.rescheduling = false 229 gp = timers.gp 230 } 231 } 232 unlock(&timers.lock) 233 return gp 234 } 235 236 // Heap maintenance algorithms. 237 238 func siftupTimer(i int) { 239 t := timers.t 240 when := t[i].when 241 tmp := t[i] 242 for i > 0 { 243 p := (i - 1) / 4 // parent 244 if when >= t[p].when { 245 break 246 } 247 t[i] = t[p] 248 t[i].i = i 249 t[p] = tmp 250 t[p].i = p 251 i = p 252 } 253 } 254 255 func siftdownTimer(i int) { 256 t := timers.t 257 n := len(t) 258 when := t[i].when 259 tmp := t[i] 260 for { 261 c := i*4 + 1 // left child 262 c3 := c + 2 // mid child 263 if c >= n { 264 break 265 } 266 w := t[c].when 267 if c+1 < n && t[c+1].when < w { 268 w = t[c+1].when 269 c++ 270 } 271 if c3 < n { 272 w3 := t[c3].when 273 if c3+1 < n && t[c3+1].when < w3 { 274 w3 = t[c3+1].when 275 c3++ 276 } 277 if w3 < w { 278 w = w3 279 c = c3 280 } 281 } 282 if w >= when { 283 break 284 } 285 t[i] = t[c] 286 t[i].i = i 287 t[c] = tmp 288 t[c].i = c 289 i = c 290 } 291 } 292 293 // Entry points for net, time to call nanotime. 294 295 //go:linkname net_runtimeNano net.runtimeNano 296 func net_runtimeNano() int64 { 297 return nanotime() 298 } 299 300 //go:linkname time_runtimeNano time.runtimeNano 301 func time_runtimeNano() int64 { 302 return nanotime() 303 } 304
