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 ( 10 "internal/cpu" 11 "unsafe" 12 ) 13 14 // Package time knows the layout of this structure. 15 // If this struct changes, adjust ../time/sleep.go:/runtimeTimer. 16 // For GOOS=nacl, package syscall knows the layout of this structure. 17 // If this struct changes, adjust ../syscall/net_nacl.go:/runtimeTimer. 18 type timer struct { 19 tb *timersBucket // the bucket the timer lives in 20 i int // heap index 21 22 // Timer wakes up at when, and then at when+period, ... (period > 0 only) 23 // each time calling f(arg, now) in the timer goroutine, so f must be 24 // a well-behaved function and not block. 25 when int64 26 period int64 27 f func(interface{}, uintptr) 28 arg interface{} 29 seq uintptr 30 } 31 32 // timersLen is the length of timers array. 33 // 34 // Ideally, this would be set to GOMAXPROCS, but that would require 35 // dynamic reallocation 36 // 37 // The current value is a compromise between memory usage and performance 38 // that should cover the majority of GOMAXPROCS values used in the wild. 39 const timersLen = 64 40 41 // timers contains "per-P" timer heaps. 42 // 43 // Timers are queued into timersBucket associated with the current P, 44 // so each P may work with its own timers independently of other P instances. 45 // 46 // Each timersBucket may be associated with multiple P 47 // if GOMAXPROCS > timersLen. 48 var timers [timersLen]struct { 49 timersBucket 50 51 // The padding should eliminate false sharing 52 // between timersBucket values. 53 pad [cpu.CacheLinePadSize - unsafe.Sizeof(timersBucket{})%cpu.CacheLinePadSize]byte 54 } 55 56 func (t *timer) assignBucket() *timersBucket { 57 id := uint8(getg().m.p.ptr().id) % timersLen 58 t.tb = &timers[id].timersBucket 59 return t.tb 60 } 61 62 //go:notinheap 63 type timersBucket struct { 64 lock mutex 65 gp *g 66 created bool 67 sleeping bool 68 rescheduling bool 69 sleepUntil int64 70 waitnote note 71 t []*timer 72 } 73 74 // nacl fake time support - time in nanoseconds since 1970 75 var faketime int64 76 77 // Package time APIs. 78 // Godoc uses the comments in package time, not these. 79 80 // time.now is implemented in assembly. 81 82 // timeSleep puts the current goroutine to sleep for at least ns nanoseconds. 83 //go:linkname timeSleep time.Sleep 84 func timeSleep(ns int64) { 85 if ns <= 0 { 86 return 87 } 88 89 gp := getg() 90 t := gp.timer 91 if t == nil { 92 t = new(timer) 93 gp.timer = t 94 } 95 *t = timer{} 96 t.when = nanotime() + ns 97 t.f = goroutineReady 98 t.arg = gp 99 tb := t.assignBucket() 100 lock(&tb.lock) 101 if !tb.addtimerLocked(t) { 102 unlock(&tb.lock) 103 badTimer() 104 } 105 goparkunlock(&tb.lock, waitReasonSleep, traceEvGoSleep, 2) 106 } 107 108 // startTimer adds t to the timer heap. 109 //go:linkname startTimer time.startTimer 110 func startTimer(t *timer) { 111 if raceenabled { 112 racerelease(unsafe.Pointer(t)) 113 } 114 addtimer(t) 115 } 116 117 // stopTimer removes t from the timer heap if it is there. 118 // It returns true if t was removed, false if t wasn't even there. 119 //go:linkname stopTimer time.stopTimer 120 func stopTimer(t *timer) bool { 121 return deltimer(t) 122 } 123 124 // Go runtime. 125 126 // Ready the goroutine arg. 127 func goroutineReady(arg interface{}, seq uintptr) { 128 goready(arg.(*g), 0) 129 } 130 131 func addtimer(t *timer) { 132 tb := t.assignBucket() 133 lock(&tb.lock) 134 ok := tb.addtimerLocked(t) 135 unlock(&tb.lock) 136 if !ok { 137 badTimer() 138 } 139 } 140 141 // Add a timer to the heap and start or kick timerproc if the new timer is 142 // earlier than any of the others. 143 // Timers are locked. 144 // Returns whether all is well: false if the data structure is corrupt 145 // due to user-level races. 146 func (tb *timersBucket) addtimerLocked(t *timer) bool { 147 // when must never be negative; otherwise timerproc will overflow 148 // during its delta calculation and never expire other runtime timers. 149 if t.when < 0 { 150 t.when = 1<<63 - 1 151 } 152 t.i = len(tb.t) 153 tb.t = append(tb.t, t) 154 if !siftupTimer(tb.t, t.i) { 155 return false 156 } 157 if t.i == 0 { 158 // siftup moved to top: new earliest deadline. 159 if tb.sleeping && tb.sleepUntil > t.when { 160 tb.sleeping = false 161 notewakeup(&tb.waitnote) 162 } 163 if tb.rescheduling { 164 tb.rescheduling = false 165 goready(tb.gp, 0) 166 } 167 if !tb.created { 168 tb.created = true 169 go timerproc(tb) 170 } 171 } 172 return true 173 } 174 175 // Delete timer t from the heap. 176 // Do not need to update the timerproc: if it wakes up early, no big deal. 177 func deltimer(t *timer) bool { 178 if t.tb == nil { 179 // t.tb can be nil if the user created a timer 180 // directly, without invoking startTimer e.g 181 // time.Ticker{C: c} 182 // In this case, return early without any deletion. 183 // See Issue 21874. 184 return false 185 } 186 187 tb := t.tb 188 189 lock(&tb.lock) 190 removed, ok := tb.deltimerLocked(t) 191 unlock(&tb.lock) 192 if !ok { 193 badTimer() 194 } 195 return removed 196 } 197 198 func (tb *timersBucket) deltimerLocked(t *timer) (removed, ok bool) { 199 // t may not be registered anymore and may have 200 // a bogus i (typically 0, if generated by Go). 201 // Verify it before proceeding. 202 i := t.i 203 last := len(tb.t) - 1 204 if i < 0 || i > last || tb.t[i] != t { 205 return false, true 206 } 207 if i != last { 208 tb.t[i] = tb.t[last] 209 tb.t[i].i = i 210 } 211 tb.t[last] = nil 212 tb.t = tb.t[:last] 213 ok = true 214 if i != last { 215 if !siftupTimer(tb.t, i) { 216 ok = false 217 } 218 if !siftdownTimer(tb.t, i) { 219 ok = false 220 } 221 } 222 return true, ok 223 } 224 225 func modtimer(t *timer, when, period int64, f func(interface{}, uintptr), arg interface{}, seq uintptr) { 226 tb := t.tb 227 228 lock(&tb.lock) 229 _, ok := tb.deltimerLocked(t) 230 if ok { 231 t.when = when 232 t.period = period 233 t.f = f 234 t.arg = arg 235 t.seq = seq 236 ok = tb.addtimerLocked(t) 237 } 238 unlock(&tb.lock) 239 if !ok { 240 badTimer() 241 } 242 } 243 244 // Timerproc runs the time-driven events. 245 // It sleeps until the next event in the tb heap. 246 // If addtimer inserts a new earlier event, it wakes timerproc early. 247 func timerproc(tb *timersBucket) { 248 tb.gp = getg() 249 for { 250 lock(&tb.lock) 251 tb.sleeping = false 252 now := nanotime() 253 delta := int64(-1) 254 for { 255 if len(tb.t) == 0 { 256 delta = -1 257 break 258 } 259 t := tb.t[0] 260 delta = t.when - now 261 if delta > 0 { 262 break 263 } 264 ok := true 265 if t.period > 0 { 266 // leave in heap but adjust next time to fire 267 t.when += t.period * (1 + -delta/t.period) 268 if !siftdownTimer(tb.t, 0) { 269 ok = false 270 } 271 } else { 272 // remove from heap 273 last := len(tb.t) - 1 274 if last > 0 { 275 tb.t[0] = tb.t[last] 276 tb.t[0].i = 0 277 } 278 tb.t[last] = nil 279 tb.t = tb.t[:last] 280 if last > 0 { 281 if !siftdownTimer(tb.t, 0) { 282 ok = false 283 } 284 } 285 t.i = -1 // mark as removed 286 } 287 f := t.f 288 arg := t.arg 289 seq := t.seq 290 unlock(&tb.lock) 291 if !ok { 292 badTimer() 293 } 294 if raceenabled { 295 raceacquire(unsafe.Pointer(t)) 296 } 297 f(arg, seq) 298 lock(&tb.lock) 299 } 300 if delta < 0 || faketime > 0 { 301 // No timers left - put goroutine to sleep. 302 tb.rescheduling = true 303 goparkunlock(&tb.lock, waitReasonTimerGoroutineIdle, traceEvGoBlock, 1) 304 continue 305 } 306 // At least one timer pending. Sleep until then. 307 tb.sleeping = true 308 tb.sleepUntil = now + delta 309 noteclear(&tb.waitnote) 310 unlock(&tb.lock) 311 notetsleepg(&tb.waitnote, delta) 312 } 313 } 314 315 func timejump() *g { 316 if faketime == 0 { 317 return nil 318 } 319 320 for i := range timers { 321 lock(&timers[i].lock) 322 } 323 gp := timejumpLocked() 324 for i := range timers { 325 unlock(&timers[i].lock) 326 } 327 328 return gp 329 } 330 331 func timejumpLocked() *g { 332 // Determine a timer bucket with minimum when. 333 var minT *timer 334 for i := range timers { 335 tb := &timers[i] 336 if !tb.created || len(tb.t) == 0 { 337 continue 338 } 339 t := tb.t[0] 340 if minT == nil || t.when < minT.when { 341 minT = t 342 } 343 } 344 if minT == nil || minT.when <= faketime { 345 return nil 346 } 347 348 faketime = minT.when 349 tb := minT.tb 350 if !tb.rescheduling { 351 return nil 352 } 353 tb.rescheduling = false 354 return tb.gp 355 } 356 357 func timeSleepUntil() int64 { 358 next := int64(1<<63 - 1) 359 360 // Determine minimum sleepUntil across all the timer buckets. 361 // 362 // The function can not return a precise answer, 363 // as another timer may pop in as soon as timers have been unlocked. 364 // So lock the timers one by one instead of all at once. 365 for i := range timers { 366 tb := &timers[i] 367 368 lock(&tb.lock) 369 if tb.sleeping && tb.sleepUntil < next { 370 next = tb.sleepUntil 371 } 372 unlock(&tb.lock) 373 } 374 375 return next 376 } 377 378 // Heap maintenance algorithms. 379 // These algorithms check for slice index errors manually. 380 // Slice index error can happen if the program is using racy 381 // access to timers. We don't want to panic here, because 382 // it will cause the program to crash with a mysterious 383 // "panic holding locks" message. Instead, we panic while not 384 // holding a lock. 385 // The races can occur despite the bucket locks because assignBucket 386 // itself is called without locks, so racy calls can cause a timer to 387 // change buckets while executing these functions. 388 389 func siftupTimer(t []*timer, i int) bool { 390 if i >= len(t) { 391 return false 392 } 393 when := t[i].when 394 tmp := t[i] 395 for i > 0 { 396 p := (i - 1) / 4 // parent 397 if when >= t[p].when { 398 break 399 } 400 t[i] = t[p] 401 t[i].i = i 402 i = p 403 } 404 if tmp != t[i] { 405 t[i] = tmp 406 t[i].i = i 407 } 408 return true 409 } 410 411 func siftdownTimer(t []*timer, i int) bool { 412 n := len(t) 413 if i >= n { 414 return false 415 } 416 when := t[i].when 417 tmp := t[i] 418 for { 419 c := i*4 + 1 // left child 420 c3 := c + 2 // mid child 421 if c >= n { 422 break 423 } 424 w := t[c].when 425 if c+1 < n && t[c+1].when < w { 426 w = t[c+1].when 427 c++ 428 } 429 if c3 < n { 430 w3 := t[c3].when 431 if c3+1 < n && t[c3+1].when < w3 { 432 w3 = t[c3+1].when 433 c3++ 434 } 435 if w3 < w { 436 w = w3 437 c = c3 438 } 439 } 440 if w >= when { 441 break 442 } 443 t[i] = t[c] 444 t[i].i = i 445 i = c 446 } 447 if tmp != t[i] { 448 t[i] = tmp 449 t[i].i = i 450 } 451 return true 452 } 453 454 // badTimer is called if the timer data structures have been corrupted, 455 // presumably due to racy use by the program. We panic here rather than 456 // panicing due to invalid slice access while holding locks. 457 // See issue #25686. 458 func badTimer() { 459 panic(errorString("racy use of timers")) 460 } 461
View as plain text