Source file src/runtime/time.go
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/abi" 11 "internal/runtime/atomic" 12 "runtime/internal/sys" 13 "unsafe" 14 ) 15 16 // A timer is a potentially repeating trigger for calling t.f(t.arg, t.seq). 17 // Timers are allocated by client code, often as part of other data structures. 18 // Each P has a heap of pointers to timers that it manages. 19 // 20 // A timer is expected to be used by only one client goroutine at a time, 21 // but there will be concurrent access by the P managing that timer. 22 // Timer accesses are protected by the lock t.mu, with a snapshot of 23 // t's state bits published in t.astate to enable certain fast paths to make 24 // decisions about a timer without acquiring the lock. 25 type timer struct { 26 // mu protects reads and writes to all fields, with exceptions noted below. 27 mu mutex 28 29 astate atomic.Uint8 // atomic copy of state bits at last unlock 30 state uint8 // state bits 31 isChan bool // timer has a channel; immutable; can be read without lock 32 blocked uint32 // number of goroutines blocked on timer's channel 33 34 // Timer wakes up at when, and then at when+period, ... (period > 0 only) 35 // each time calling f(arg, seq, delay) in the timer goroutine, so f must be 36 // a well-behaved function and not block. 37 // 38 // The arg and seq are client-specified opaque arguments passed back to f. 39 // When used from netpoll, arg and seq have meanings defined by netpoll 40 // and are completely opaque to this code; in that context, seq is a sequence 41 // number to recognize and squech stale function invocations. 42 // When used from package time, arg is a channel (for After, NewTicker) 43 // or the function to call (for AfterFunc) and seq is unused (0). 44 // 45 // Package time does not know about seq, but if this is a channel timer (t.isChan == true), 46 // this file uses t.seq as a sequence number to recognize and squelch 47 // sends that correspond to an earlier (stale) timer configuration, 48 // similar to its use in netpoll. In this usage (that is, when t.isChan == true), 49 // writes to seq are protected by both t.mu and t.sendLock, 50 // so reads are allowed when holding either of the two mutexes. 51 // 52 // The delay argument is nanotime() - t.when, meaning the delay in ns between 53 // when the timer should have gone off and now. Normally that amount is 54 // small enough not to matter, but for channel timers that are fed lazily, 55 // the delay can be arbitrarily long; package time subtracts it out to make 56 // it look like the send happened earlier than it actually did. 57 // (No one looked at the channel since then, or the send would have 58 // not happened so late, so no one can tell the difference.) 59 when int64 60 period int64 61 f func(arg any, seq uintptr, delay int64) 62 arg any 63 seq uintptr 64 65 // If non-nil, the timers containing t. 66 ts *timers 67 68 // whenHeap is a (perhaps outdated) copy of t.when for use 69 // ordering t within t.ts.heap. 70 // When t is in a heap but t.whenHeap is outdated, 71 // the timerModified state bit is set. 72 // The actual update t.whenHeap = t.when must be 73 // delayed until the heap can be reordered at the same time 74 // (meaning t's lock must be held for whenHeap, 75 // and t.ts's lock must be held for the heap reordering). 76 // Since writes to whenHeap are protected by two locks (t.mu and t.ts.mu), 77 // it is permitted to read whenHeap when holding either one. 78 whenHeap int64 79 80 // sendLock protects sends on the timer's channel. 81 // Not used for async (pre-Go 1.23) behavior when debug.asynctimerchan.Load() != 0. 82 sendLock mutex 83 } 84 85 // init initializes a newly allocated timer t. 86 // Any code that allocates a timer must call t.init before using it. 87 // The arg and f can be set during init, or they can be nil in init 88 // and set by a future call to t.modify. 89 func (t *timer) init(f func(arg any, seq uintptr, delay int64), arg any) { 90 lockInit(&t.mu, lockRankTimer) 91 t.f = f 92 t.arg = arg 93 } 94 95 // A timers is a per-P set of timers. 96 type timers struct { 97 // mu protects timers; timers are per-P, but the scheduler can 98 // access the timers of another P, so we have to lock. 99 mu mutex 100 101 // heap is the set of timers, ordered by t.whenHeap. 102 // Must hold lock to access. 103 heap []*timer 104 105 // len is an atomic copy of len(heap). 106 len atomic.Uint32 107 108 // zombies is the number of timers in the heap 109 // that are marked for removal. 110 zombies atomic.Int32 111 112 // raceCtx is the race context used while executing timer functions. 113 raceCtx uintptr 114 115 // minWhenHeap is the minimum heap[i].whenHeap value (= heap[0].whenHeap). 116 // The wakeTime method uses minWhenHeap and minWhenModified 117 // to determine the next wake time. 118 // If minWhenHeap = 0, it means there are no timers in the heap. 119 minWhenHeap atomic.Int64 120 121 // minWhenModified is a lower bound on the minimum 122 // heap[i].when over timers with the timerModified bit set. 123 // If minWhenModified = 0, it means there are no timerModified timers in the heap. 124 minWhenModified atomic.Int64 125 } 126 127 func (ts *timers) lock() { 128 lock(&ts.mu) 129 } 130 131 func (ts *timers) unlock() { 132 // Update atomic copy of len(ts.heap). 133 // We only update at unlock so that the len is always 134 // the most recent unlocked length, not an ephemeral length. 135 // This matters if we lock ts, delete the only timer from the heap, 136 // add it back, and unlock. We want ts.len.Load to return 1 the 137 // entire time, never 0. This is important for pidleput deciding 138 // whether ts is empty. 139 ts.len.Store(uint32(len(ts.heap))) 140 141 unlock(&ts.mu) 142 } 143 144 // Timer state field. 145 const ( 146 // timerHeaped is set when the timer is stored in some P's heap. 147 timerHeaped uint8 = 1 << iota 148 149 // timerModified is set when t.when has been modified but 150 // t.whenHeap still needs to be updated as well. 151 // The change to t.whenHeap waits until the heap in which 152 // the timer appears can be locked and rearranged. 153 // timerModified is only set when timerHeaped is also set. 154 timerModified 155 156 // timerZombie is set when the timer has been stopped 157 // but is still present in some P's heap. 158 // Only set when timerHeaped is also set. 159 // It is possible for timerModified and timerZombie to both 160 // be set, meaning that the timer was modified and then stopped. 161 // A timer sending to a channel may be placed in timerZombie 162 // to take it out of the heap even though the timer is not stopped, 163 // as long as nothing is reading from the channel. 164 timerZombie 165 ) 166 167 // timerDebug enables printing a textual debug trace of all timer operations to stderr. 168 const timerDebug = false 169 170 func (t *timer) trace(op string) { 171 if timerDebug { 172 t.trace1(op) 173 } 174 } 175 176 func (t *timer) trace1(op string) { 177 if !timerDebug { 178 return 179 } 180 bits := [4]string{"h", "m", "z", "c"} 181 for i := range 3 { 182 if t.state&(1<<i) == 0 { 183 bits[i] = "-" 184 } 185 } 186 if !t.isChan { 187 bits[3] = "-" 188 } 189 print("T ", t, " ", bits[0], bits[1], bits[2], bits[3], " b=", t.blocked, " ", op, "\n") 190 } 191 192 func (ts *timers) trace(op string) { 193 if timerDebug { 194 println("TS", ts, op) 195 } 196 } 197 198 // lock locks the timer, allowing reading or writing any of the timer fields. 199 func (t *timer) lock() { 200 lock(&t.mu) 201 t.trace("lock") 202 } 203 204 // unlock updates t.astate and unlocks the timer. 205 func (t *timer) unlock() { 206 t.trace("unlock") 207 // Let heap fast paths know whether t.whenHeap is accurate. 208 // Also let maybeRunChan know whether channel is in heap. 209 t.astate.Store(t.state) 210 unlock(&t.mu) 211 } 212 213 // hchan returns the channel in t.arg. 214 // t must be a timer with a channel. 215 func (t *timer) hchan() *hchan { 216 if !t.isChan { 217 badTimer() 218 } 219 // Note: t.arg is a chan time.Time, 220 // and runtime cannot refer to that type, 221 // so we cannot use a type assertion. 222 return (*hchan)(efaceOf(&t.arg).data) 223 } 224 225 // updateHeap updates t.whenHeap as directed by t.state, updating t.state 226 // and returning a bool indicating whether the state (and t.whenHeap) changed. 227 // The caller must hold t's lock, or the world can be stopped instead. 228 // If ts != nil, then ts must be locked, t must be ts.heap[0], and updateHeap 229 // takes care of moving t within the timers heap to preserve the heap invariants. 230 // If ts == nil, then t must not be in a heap (or is in a heap that is 231 // temporarily not maintaining its invariant, such as during timers.adjust). 232 func (t *timer) updateHeap(ts *timers) (updated bool) { 233 assertWorldStoppedOrLockHeld(&t.mu) 234 t.trace("updateHeap") 235 if ts != nil { 236 if t.ts != ts || t != ts.heap[0] { 237 badTimer() 238 } 239 assertLockHeld(&ts.mu) 240 } 241 if t.state&timerZombie != 0 { 242 // Take timer out of heap. 243 t.state &^= timerHeaped | timerZombie | timerModified 244 if ts != nil { 245 ts.zombies.Add(-1) 246 ts.deleteMin() 247 } 248 return true 249 } 250 251 if t.state&timerModified != 0 { 252 // Apply t.whenHeap update and move within heap. 253 t.state &^= timerModified 254 t.whenHeap = t.when 255 // Move t to the right position. 256 if ts != nil { 257 ts.siftDown(0) 258 ts.updateMinWhenHeap() 259 } 260 return true 261 } 262 263 return false 264 } 265 266 // maxWhen is the maximum value for timer's when field. 267 const maxWhen = 1<<63 - 1 268 269 // verifyTimers can be set to true to add debugging checks that the 270 // timer heaps are valid. 271 const verifyTimers = false 272 273 // Package time APIs. 274 // Godoc uses the comments in package time, not these. 275 276 // time.now is implemented in assembly. 277 278 // timeSleep puts the current goroutine to sleep for at least ns nanoseconds. 279 // 280 //go:linkname timeSleep time.Sleep 281 func timeSleep(ns int64) { 282 if ns <= 0 { 283 return 284 } 285 286 gp := getg() 287 t := gp.timer 288 if t == nil { 289 t = new(timer) 290 t.init(goroutineReady, gp) 291 gp.timer = t 292 } 293 when := nanotime() + ns 294 if when < 0 { // check for overflow. 295 when = maxWhen 296 } 297 gp.sleepWhen = when 298 gopark(resetForSleep, nil, waitReasonSleep, traceBlockSleep, 1) 299 } 300 301 // resetForSleep is called after the goroutine is parked for timeSleep. 302 // We can't call timer.reset in timeSleep itself because if this is a short 303 // sleep and there are many goroutines then the P can wind up running the 304 // timer function, goroutineReady, before the goroutine has been parked. 305 func resetForSleep(gp *g, _ unsafe.Pointer) bool { 306 gp.timer.reset(gp.sleepWhen, 0) 307 return true 308 } 309 310 // A timeTimer is a runtime-allocated time.Timer or time.Ticker 311 // with the additional runtime state following it. 312 // The runtime state is inaccessible to package time. 313 type timeTimer struct { 314 c unsafe.Pointer // <-chan time.Time 315 init bool 316 timer 317 } 318 319 // newTimer allocates and returns a new time.Timer or time.Ticker (same layout) 320 // with the given parameters. 321 // 322 //go:linkname newTimer time.newTimer 323 func newTimer(when, period int64, f func(arg any, seq uintptr, delay int64), arg any, c *hchan) *timeTimer { 324 t := new(timeTimer) 325 t.timer.init(nil, nil) 326 t.trace("new") 327 if raceenabled { 328 racerelease(unsafe.Pointer(&t.timer)) 329 } 330 if c != nil { 331 lockInit(&t.sendLock, lockRankTimerSend) 332 t.isChan = true 333 c.timer = &t.timer 334 if c.dataqsiz == 0 { 335 throw("invalid timer channel: no capacity") 336 } 337 } 338 t.modify(when, period, f, arg, 0) 339 t.init = true 340 return t 341 } 342 343 // stopTimer stops a timer. 344 // It reports whether t was stopped before being run. 345 // 346 //go:linkname stopTimer time.stopTimer 347 func stopTimer(t *timeTimer) bool { 348 return t.stop() 349 } 350 351 // resetTimer resets an inactive timer, adding it to the timer heap. 352 // 353 // Reports whether the timer was modified before it was run. 354 // 355 //go:linkname resetTimer time.resetTimer 356 func resetTimer(t *timeTimer, when, period int64) bool { 357 if raceenabled { 358 racerelease(unsafe.Pointer(&t.timer)) 359 } 360 return t.reset(when, period) 361 } 362 363 // Go runtime. 364 365 // Ready the goroutine arg. 366 func goroutineReady(arg any, _ uintptr, _ int64) { 367 goready(arg.(*g), 0) 368 } 369 370 // addHeap adds t to the timers heap. 371 // The caller must hold ts.lock or the world must be stopped. 372 // The caller must also have checked that t belongs in the heap. 373 // Callers that are not sure can call t.maybeAdd instead, 374 // but note that maybeAdd has different locking requirements. 375 func (ts *timers) addHeap(t *timer) { 376 assertWorldStoppedOrLockHeld(&ts.mu) 377 // Timers rely on the network poller, so make sure the poller 378 // has started. 379 if netpollInited.Load() == 0 { 380 netpollGenericInit() 381 } 382 383 if t.ts != nil { 384 throw("ts set in timer") 385 } 386 t.ts = ts 387 t.whenHeap = t.when 388 ts.heap = append(ts.heap, t) 389 ts.siftUp(len(ts.heap) - 1) 390 if t == ts.heap[0] { 391 ts.updateMinWhenHeap() 392 } 393 } 394 395 // maybeRunAsync checks whether t needs to be triggered and runs it if so. 396 // The caller is responsible for locking the timer and for checking that we 397 // are running timers in async mode. If the timer needs to be run, 398 // maybeRunAsync will unlock and re-lock it. 399 // The timer is always locked on return. 400 func (t *timer) maybeRunAsync() { 401 assertLockHeld(&t.mu) 402 if t.state&timerHeaped == 0 && t.isChan && t.when > 0 { 403 // If timer should have triggered already (but nothing looked at it yet), 404 // trigger now, so that a receive after the stop sees the "old" value 405 // that should be there. 406 // (It is possible to have t.blocked > 0 if there is a racing receive 407 // in blockTimerChan, but timerHeaped not being set means 408 // it hasn't run t.maybeAdd yet; in that case, running the 409 // timer ourselves now is fine.) 410 if now := nanotime(); t.when <= now { 411 systemstack(func() { 412 t.unlockAndRun(now) // resets t.when 413 }) 414 t.lock() 415 } 416 } 417 } 418 419 // stop stops the timer t. It may be on some other P, so we can't 420 // actually remove it from the timers heap. We can only mark it as stopped. 421 // It will be removed in due course by the P whose heap it is on. 422 // Reports whether the timer was stopped before it was run. 423 func (t *timer) stop() bool { 424 async := debug.asynctimerchan.Load() != 0 425 if !async && t.isChan { 426 lock(&t.sendLock) 427 } 428 429 t.lock() 430 t.trace("stop") 431 if async { 432 t.maybeRunAsync() 433 } 434 if t.state&timerHeaped != 0 { 435 t.state |= timerModified 436 if t.state&timerZombie == 0 { 437 t.state |= timerZombie 438 t.ts.zombies.Add(1) 439 } 440 } 441 pending := t.when > 0 442 t.when = 0 443 444 if !async && t.isChan { 445 // Stop any future sends with stale values. 446 // See timer.unlockAndRun. 447 t.seq++ 448 } 449 t.unlock() 450 if !async && t.isChan { 451 unlock(&t.sendLock) 452 if timerchandrain(t.hchan()) { 453 pending = true 454 } 455 } 456 457 return pending 458 } 459 460 // deleteMin removes timer 0 from ts. 461 // ts must be locked. 462 func (ts *timers) deleteMin() { 463 assertLockHeld(&ts.mu) 464 t := ts.heap[0] 465 if t.ts != ts { 466 throw("wrong timers") 467 } 468 t.ts = nil 469 last := len(ts.heap) - 1 470 if last > 0 { 471 ts.heap[0] = ts.heap[last] 472 } 473 ts.heap[last] = nil 474 ts.heap = ts.heap[:last] 475 if last > 0 { 476 ts.siftDown(0) 477 } 478 ts.updateMinWhenHeap() 479 if last == 0 { 480 // If there are no timers, then clearly there are no timerModified timers. 481 ts.minWhenModified.Store(0) 482 } 483 } 484 485 // modify modifies an existing timer. 486 // This is called by the netpoll code or time.Ticker.Reset or time.Timer.Reset. 487 // Reports whether the timer was modified before it was run. 488 // If f == nil, then t.f, t.arg, and t.seq are not modified. 489 func (t *timer) modify(when, period int64, f func(arg any, seq uintptr, delay int64), arg any, seq uintptr) bool { 490 if when <= 0 { 491 throw("timer when must be positive") 492 } 493 if period < 0 { 494 throw("timer period must be non-negative") 495 } 496 async := debug.asynctimerchan.Load() != 0 497 498 if !async && t.isChan { 499 lock(&t.sendLock) 500 } 501 502 t.lock() 503 if async { 504 t.maybeRunAsync() 505 } 506 t.trace("modify") 507 t.period = period 508 if f != nil { 509 t.f = f 510 t.arg = arg 511 t.seq = seq 512 } 513 514 wake := false 515 pending := t.when > 0 516 t.when = when 517 if t.state&timerHeaped != 0 { 518 t.state |= timerModified 519 if t.state&timerZombie != 0 { 520 // In the heap but marked for removal (by a Stop). 521 // Unmark it, since it has been Reset and will be running again. 522 t.ts.zombies.Add(-1) 523 t.state &^= timerZombie 524 } 525 // Cannot modify t.whenHeap until t.ts is locked. 526 // See comment in type timer above and in timers.adjust below. 527 if when < t.whenHeap { 528 wake = true 529 // Force timerModified bit out to t.astate before updating t.minWhenModified, 530 // to synchronize with t.ts.adjust. See comment in adjust. 531 t.astate.Store(t.state) 532 t.ts.updateMinWhenModified(when) 533 } 534 } 535 536 add := t.needsAdd() 537 538 if !async && t.isChan { 539 // Stop any future sends with stale values. 540 // See timer.unlockAndRun. 541 t.seq++ 542 } 543 t.unlock() 544 if !async && t.isChan { 545 if timerchandrain(t.hchan()) { 546 pending = true 547 } 548 unlock(&t.sendLock) 549 } 550 551 if add { 552 t.maybeAdd() 553 } 554 if wake { 555 wakeNetPoller(when) 556 } 557 558 return pending 559 } 560 561 // needsAdd reports whether t needs to be added to a timers heap. 562 // t must be locked. 563 func (t *timer) needsAdd() bool { 564 assertLockHeld(&t.mu) 565 need := t.state&timerHeaped == 0 && t.when > 0 && (!t.isChan || t.blocked > 0) 566 if need { 567 t.trace("needsAdd+") 568 } else { 569 t.trace("needsAdd-") 570 } 571 return need 572 } 573 574 // maybeAdd adds t to the local timers heap if it needs to be in a heap. 575 // The caller must not hold t's lock nor any timers heap lock. 576 // The caller probably just unlocked t, but that lock must be dropped 577 // in order to acquire a ts.lock, to avoid lock inversions. 578 // (timers.adjust holds ts.lock while acquiring each t's lock, 579 // so we cannot hold any t's lock while acquiring ts.lock). 580 // 581 // Strictly speaking it *might* be okay to hold t.lock and 582 // acquire ts.lock at the same time, because we know that 583 // t is not in any ts.heap, so nothing holding a ts.lock would 584 // be acquiring the t.lock at the same time, meaning there 585 // isn't a possible deadlock. But it is easier and safer not to be 586 // too clever and respect the static ordering. 587 // (If we don't, we have to change the static lock checking of t and ts.) 588 // 589 // Concurrent calls to time.Timer.Reset or blockTimerChan 590 // may result in concurrent calls to t.maybeAdd, 591 // so we cannot assume that t is not in a heap on entry to t.maybeAdd. 592 func (t *timer) maybeAdd() { 593 // Note: Not holding any locks on entry to t.maybeAdd, 594 // so the current g can be rescheduled to a different M and P 595 // at any time, including between the ts := assignment and the 596 // call to ts.lock. If a reschedule happened then, we would be 597 // adding t to some other P's timers, perhaps even a P that the scheduler 598 // has marked as idle with no timers, in which case the timer could 599 // go unnoticed until long after t.when. 600 // Calling acquirem instead of using getg().m makes sure that 601 // we end up locking and inserting into the current P's timers. 602 mp := acquirem() 603 ts := &mp.p.ptr().timers 604 ts.lock() 605 ts.cleanHead() 606 t.lock() 607 t.trace("maybeAdd") 608 when := int64(0) 609 wake := false 610 if t.needsAdd() { 611 t.state |= timerHeaped 612 when = t.when 613 wakeTime := ts.wakeTime() 614 wake = wakeTime == 0 || when < wakeTime 615 ts.addHeap(t) 616 } 617 t.unlock() 618 ts.unlock() 619 releasem(mp) 620 if wake { 621 wakeNetPoller(when) 622 } 623 } 624 625 // reset resets the time when a timer should fire. 626 // If used for an inactive timer, the timer will become active. 627 // Reports whether the timer was active and was stopped. 628 func (t *timer) reset(when, period int64) bool { 629 return t.modify(when, period, nil, nil, 0) 630 } 631 632 // cleanHead cleans up the head of the timer queue. This speeds up 633 // programs that create and delete timers; leaving them in the heap 634 // slows down heap operations. 635 // The caller must have locked ts. 636 func (ts *timers) cleanHead() { 637 ts.trace("cleanHead") 638 assertLockHeld(&ts.mu) 639 gp := getg() 640 for { 641 if len(ts.heap) == 0 { 642 return 643 } 644 645 // This loop can theoretically run for a while, and because 646 // it is holding timersLock it cannot be preempted. 647 // If someone is trying to preempt us, just return. 648 // We can clean the timers later. 649 if gp.preemptStop { 650 return 651 } 652 653 // Delete zombies from tail of heap. It requires no heap adjustments at all, 654 // and doing so increases the chances that when we swap out a zombie 655 // in heap[0] for the tail of the heap, we'll get a non-zombie timer, 656 // shortening this loop. 657 n := len(ts.heap) 658 if t := ts.heap[n-1]; t.astate.Load()&timerZombie != 0 { 659 t.lock() 660 if t.state&timerZombie != 0 { 661 t.state &^= timerHeaped | timerZombie | timerModified 662 t.ts = nil 663 ts.zombies.Add(-1) 664 ts.heap[n-1] = nil 665 ts.heap = ts.heap[:n-1] 666 } 667 t.unlock() 668 continue 669 } 670 671 t := ts.heap[0] 672 if t.ts != ts { 673 throw("bad ts") 674 } 675 676 if t.astate.Load()&(timerModified|timerZombie) == 0 { 677 // Fast path: head of timers does not need adjustment. 678 return 679 } 680 681 t.lock() 682 updated := t.updateHeap(ts) 683 t.unlock() 684 if !updated { 685 // Head of timers does not need adjustment. 686 return 687 } 688 } 689 } 690 691 // take moves any timers from src into ts 692 // and then clears the timer state from src, 693 // because src is being destroyed. 694 // The caller must not have locked either timers. 695 // For now this is only called when the world is stopped. 696 func (ts *timers) take(src *timers) { 697 ts.trace("take") 698 assertWorldStopped() 699 if len(src.heap) > 0 { 700 // The world is stopped, so we ignore the locking of ts and src here. 701 // That would introduce a sched < timers lock ordering, 702 // which we'd rather avoid in the static ranking. 703 ts.move(src.heap) 704 src.heap = nil 705 src.zombies.Store(0) 706 src.minWhenHeap.Store(0) 707 src.minWhenModified.Store(0) 708 src.len.Store(0) 709 ts.len.Store(uint32(len(ts.heap))) 710 } 711 } 712 713 // moveTimers moves a slice of timers to pp. The slice has been taken 714 // from a different P. 715 // The world must be stopped so that ts is safe to modify. 716 func (ts *timers) move(timers []*timer) { 717 assertWorldStopped() 718 for _, t := range timers { 719 t.ts = nil 720 t.updateHeap(nil) 721 if t.state&timerHeaped != 0 { 722 ts.addHeap(t) 723 } 724 } 725 } 726 727 // adjust looks through the timers in ts.heap for 728 // any timers that have been modified to run earlier, and puts them in 729 // the correct place in the heap. While looking for those timers, 730 // it also moves timers that have been modified to run later, 731 // and removes deleted timers. The caller must have locked ts. 732 func (ts *timers) adjust(now int64, force bool) { 733 ts.trace("adjust") 734 assertLockHeld(&ts.mu) 735 // If we haven't yet reached the time of the earliest modified 736 // timer, don't do anything. This speeds up programs that adjust 737 // a lot of timers back and forth if the timers rarely expire. 738 // We'll postpone looking through all the adjusted timers until 739 // one would actually expire. 740 if !force { 741 first := ts.minWhenModified.Load() 742 if first == 0 || first > now { 743 if verifyTimers { 744 ts.verify() 745 } 746 return 747 } 748 } 749 750 // minWhenModified is a lower bound on the earliest t.when 751 // among the timerModified timers. We want to make it more precise: 752 // we are going to scan the heap and clean out all the timerModified bits, 753 // at which point minWhenModified can be set to 0 (indicating none at all). 754 // 755 // Other P's can be calling ts.wakeTime concurrently, and we'd like to 756 // keep ts.wakeTime returning an accurate value throughout this entire process. 757 // 758 // Setting minWhenModified = 0 *before* the scan could make wakeTime 759 // return an incorrect value: if minWhenModified < minWhenHeap, then clearing 760 // it to 0 will make wakeTime return minWhenHeap (too late) until the scan finishes. 761 // To avoid that, we want to set minWhenModified to 0 *after* the scan. 762 // 763 // Setting minWhenModified = 0 *after* the scan could result in missing 764 // concurrent timer modifications in other goroutines; those will lock 765 // the specific timer, set the timerModified bit, and set t.when. 766 // To avoid that, we want to set minWhenModified to 0 *before* the scan. 767 // 768 // The way out of this dilemma is to preserve wakeTime a different way. 769 // wakeTime is min(minWhenHeap, minWhenModified), and minWhenHeap 770 // is protected by ts.lock, which we hold, so we can modify it however we like 771 // in service of keeping wakeTime accurate. 772 // 773 // So we can: 774 // 775 // 1. Set minWhenHeap = min(minWhenHeap, minWhenModified) 776 // 2. Set minWhenModified = 0 777 // (Other goroutines may modify timers and update minWhenModified now.) 778 // 3. Scan timers 779 // 4. Set minWhenHeap = heap[0].whenHeap 780 // 781 // That order preserves a correct value of wakeTime throughout the entire 782 // operation: 783 // Step 1 “locks in” an accurate wakeTime even with minWhenModified cleared. 784 // Step 2 makes sure concurrent t.when updates are not lost during the scan. 785 // Step 3 processes all modified timer values, justifying minWhenModified = 0. 786 // Step 4 corrects minWhenHeap to a precise value. 787 // 788 // The wakeTime method implementation reads minWhenModified *before* minWhenHeap, 789 // so that if the minWhenModified is observed to be 0, that means the minWhenHeap that 790 // follows will include the information that was zeroed out of it. 791 // 792 // Originally Step 3 locked every timer, which made sure any timer update that was 793 // already in progress during Steps 1+2 completed and was observed by Step 3. 794 // All that locking was too expensive, so now we do an atomic load of t.astate to 795 // decide whether we need to do a full lock. To make sure that we still observe any 796 // timer update already in progress during Steps 1+2, t.modify sets timerModified 797 // in t.astate *before* calling t.updateMinWhenModified. That ensures that the 798 // overwrite in Step 2 cannot lose an update: if it does overwrite an update, Step 3 799 // will see the timerModified and do a full lock. 800 ts.minWhenHeap.Store(ts.wakeTime()) 801 ts.minWhenModified.Store(0) 802 803 changed := false 804 for i := 0; i < len(ts.heap); i++ { 805 t := ts.heap[i] 806 if t.ts != ts { 807 throw("bad ts") 808 } 809 810 if t.astate.Load()&(timerModified|timerZombie) == 0 { 811 // Does not need adjustment. 812 continue 813 } 814 815 t.lock() 816 if t.state&timerHeaped == 0 { 817 badTimer() 818 } 819 if t.state&timerZombie != 0 { 820 ts.zombies.Add(-1) // updateHeap will return updated=true and we will delete t 821 } 822 if t.updateHeap(nil) { 823 changed = true 824 if t.state&timerHeaped == 0 { 825 n := len(ts.heap) 826 ts.heap[i] = ts.heap[n-1] 827 ts.heap[n-1] = nil 828 ts.heap = ts.heap[:n-1] 829 t.ts = nil 830 i-- 831 } 832 } 833 t.unlock() 834 } 835 836 if changed { 837 ts.initHeap() 838 } 839 ts.updateMinWhenHeap() 840 841 if verifyTimers { 842 ts.verify() 843 } 844 } 845 846 // wakeTime looks at ts's timers and returns the time when we 847 // should wake up the netpoller. It returns 0 if there are no timers. 848 // This function is invoked when dropping a P, so it must run without 849 // any write barriers. 850 // 851 //go:nowritebarrierrec 852 func (ts *timers) wakeTime() int64 { 853 // Note that the order of these two loads matters: 854 // adjust updates minWhen to make it safe to clear minNextWhen. 855 // We read minWhen after reading minNextWhen so that 856 // if we see a cleared minNextWhen, we are guaranteed to see 857 // the updated minWhen. 858 nextWhen := ts.minWhenModified.Load() 859 when := ts.minWhenHeap.Load() 860 if when == 0 || (nextWhen != 0 && nextWhen < when) { 861 when = nextWhen 862 } 863 return when 864 } 865 866 // check runs any timers in ts that are ready. 867 // If now is not 0 it is the current time. 868 // It returns the passed time or the current time if now was passed as 0. 869 // and the time when the next timer should run or 0 if there is no next timer, 870 // and reports whether it ran any timers. 871 // If the time when the next timer should run is not 0, 872 // it is always larger than the returned time. 873 // We pass now in and out to avoid extra calls of nanotime. 874 // 875 //go:yeswritebarrierrec 876 func (ts *timers) check(now int64) (rnow, pollUntil int64, ran bool) { 877 ts.trace("check") 878 // If it's not yet time for the first timer, or the first adjusted 879 // timer, then there is nothing to do. 880 next := ts.wakeTime() 881 if next == 0 { 882 // No timers to run or adjust. 883 return now, 0, false 884 } 885 886 if now == 0 { 887 now = nanotime() 888 } 889 890 // If this is the local P, and there are a lot of deleted timers, 891 // clear them out. We only do this for the local P to reduce 892 // lock contention on timersLock. 893 zombies := ts.zombies.Load() 894 if zombies < 0 { 895 badTimer() 896 } 897 force := ts == &getg().m.p.ptr().timers && int(zombies) > int(ts.len.Load())/4 898 899 if now < next && !force { 900 // Next timer is not ready to run, and we don't need to clear deleted timers. 901 return now, next, false 902 } 903 904 ts.lock() 905 if len(ts.heap) > 0 { 906 ts.adjust(now, false) 907 for len(ts.heap) > 0 { 908 // Note that runtimer may temporarily unlock ts. 909 if tw := ts.run(now); tw != 0 { 910 if tw > 0 { 911 pollUntil = tw 912 } 913 break 914 } 915 ran = true 916 } 917 918 // Note: Delaying the forced adjustment until after the ts.run 919 // (as opposed to calling ts.adjust(now, force) above) 920 // is significantly faster under contention, such as in 921 // package time's BenchmarkTimerAdjust10000, 922 // though we do not fully understand why. 923 force = ts == &getg().m.p.ptr().timers && int(ts.zombies.Load()) > int(ts.len.Load())/4 924 if force { 925 ts.adjust(now, true) 926 } 927 } 928 ts.unlock() 929 930 return now, pollUntil, ran 931 } 932 933 // run examines the first timer in ts. If it is ready based on now, 934 // it runs the timer and removes or updates it. 935 // Returns 0 if it ran a timer, -1 if there are no more timers, or the time 936 // when the first timer should run. 937 // The caller must have locked ts. 938 // If a timer is run, this will temporarily unlock ts. 939 // 940 //go:systemstack 941 func (ts *timers) run(now int64) int64 { 942 ts.trace("run") 943 assertLockHeld(&ts.mu) 944 Redo: 945 if len(ts.heap) == 0 { 946 return -1 947 } 948 t := ts.heap[0] 949 if t.ts != ts { 950 throw("bad ts") 951 } 952 953 if t.astate.Load()&(timerModified|timerZombie) == 0 && t.whenHeap > now { 954 // Fast path: not ready to run. 955 // The access of t.whenHeap is protected by the caller holding 956 // ts.lock, even though t itself is unlocked. 957 return t.whenHeap 958 } 959 960 t.lock() 961 if t.updateHeap(ts) { 962 t.unlock() 963 goto Redo 964 } 965 966 if t.state&timerHeaped == 0 || t.state&timerModified != 0 { 967 badTimer() 968 } 969 970 if t.when > now { 971 // Not ready to run. 972 t.unlock() 973 return t.when 974 } 975 976 t.unlockAndRun(now) 977 assertLockHeld(&ts.mu) // t is unlocked now, but not ts 978 return 0 979 } 980 981 // unlockAndRun unlocks and runs the timer t (which must be locked). 982 // If t is in a timer set (t.ts != nil), the caller must also have locked the timer set, 983 // and this call will temporarily unlock the timer set while running the timer function. 984 // unlockAndRun returns with t unlocked and t.ts (re-)locked. 985 // 986 //go:systemstack 987 func (t *timer) unlockAndRun(now int64) { 988 t.trace("unlockAndRun") 989 assertLockHeld(&t.mu) 990 if t.ts != nil { 991 assertLockHeld(&t.ts.mu) 992 } 993 if raceenabled { 994 // Note that we are running on a system stack, 995 // so there is no chance of getg().m being reassigned 996 // out from under us while this function executes. 997 tsLocal := &getg().m.p.ptr().timers 998 if tsLocal.raceCtx == 0 { 999 tsLocal.raceCtx = racegostart(abi.FuncPCABIInternal((*timers).run) + sys.PCQuantum) 1000 } 1001 raceacquirectx(tsLocal.raceCtx, unsafe.Pointer(t)) 1002 } 1003 1004 if t.state&(timerModified|timerZombie) != 0 { 1005 badTimer() 1006 } 1007 1008 f := t.f 1009 arg := t.arg 1010 seq := t.seq 1011 var next int64 1012 delay := now - t.when 1013 if t.period > 0 { 1014 // Leave in heap but adjust next time to fire. 1015 next = t.when + t.period*(1+delay/t.period) 1016 if next < 0 { // check for overflow. 1017 next = maxWhen 1018 } 1019 } else { 1020 next = 0 1021 } 1022 if t.state&timerHeaped != 0 { 1023 t.when = next 1024 t.state |= timerModified 1025 if next == 0 { 1026 t.state |= timerZombie 1027 t.ts.zombies.Add(1) 1028 } 1029 } else { 1030 t.when = next 1031 } 1032 ts := t.ts 1033 t.updateHeap(ts) 1034 t.unlock() 1035 1036 if raceenabled { 1037 // Temporarily use the current P's racectx for g0. 1038 gp := getg() 1039 if gp.racectx != 0 { 1040 throw("unexpected racectx") 1041 } 1042 gp.racectx = gp.m.p.ptr().timers.raceCtx 1043 } 1044 1045 if ts != nil { 1046 ts.unlock() 1047 } 1048 1049 async := debug.asynctimerchan.Load() != 0 1050 if !async && t.isChan { 1051 // For a timer channel, we want to make sure that no stale sends 1052 // happen after a t.stop or t.modify, but we cannot hold t.mu 1053 // during the actual send (which f does) due to lock ordering. 1054 // It can happen that we are holding t's lock above, we decide 1055 // it's time to send a time value (by calling f), grab the parameters, 1056 // unlock above, and then a t.stop or t.modify changes the timer 1057 // and returns. At that point, the send needs not to happen after all. 1058 // The way we arrange for it not to happen is that t.stop and t.modify 1059 // both increment t.seq while holding both t.mu and t.sendLock. 1060 // We copied the seq value above while holding t.mu. 1061 // Now we can acquire t.sendLock (which will be held across the send) 1062 // and double-check that t.seq is still the seq value we saw above. 1063 // If not, the timer has been updated and we should skip the send. 1064 // We skip the send by reassigning f to a no-op function. 1065 lock(&t.sendLock) 1066 if t.seq != seq { 1067 f = func(any, uintptr, int64) {} 1068 } 1069 } 1070 1071 f(arg, seq, delay) 1072 1073 if !async && t.isChan { 1074 unlock(&t.sendLock) 1075 } 1076 1077 if ts != nil { 1078 ts.lock() 1079 } 1080 1081 if raceenabled { 1082 gp := getg() 1083 gp.racectx = 0 1084 } 1085 } 1086 1087 // verifyTimerHeap verifies that the timers is in a valid state. 1088 // This is only for debugging, and is only called if verifyTimers is true. 1089 // The caller must have locked ts. 1090 func (ts *timers) verify() { 1091 assertLockHeld(&ts.mu) 1092 for i, t := range ts.heap { 1093 if i == 0 { 1094 // First timer has no parent. 1095 continue 1096 } 1097 1098 // The heap is 4-ary. See siftupTimer and siftdownTimer. 1099 p := (i - 1) / 4 1100 if t.whenHeap < ts.heap[p].whenHeap { 1101 print("bad timer heap at ", i, ": ", p, ": ", ts.heap[p].whenHeap, ", ", i, ": ", t.whenHeap, "\n") 1102 throw("bad timer heap") 1103 } 1104 } 1105 if n := int(ts.len.Load()); len(ts.heap) != n { 1106 println("timer heap len", len(ts.heap), "!= atomic len", n) 1107 throw("bad timer heap len") 1108 } 1109 } 1110 1111 // updateMinWhenHeap sets ts.minWhenHeap to ts.heap[0].whenHeap. 1112 // The caller must have locked ts or the world must be stopped. 1113 func (ts *timers) updateMinWhenHeap() { 1114 assertWorldStoppedOrLockHeld(&ts.mu) 1115 if len(ts.heap) == 0 { 1116 ts.minWhenHeap.Store(0) 1117 } else { 1118 ts.minWhenHeap.Store(ts.heap[0].whenHeap) 1119 } 1120 } 1121 1122 // updateMinWhenModified updates ts.minWhenModified to be <= when. 1123 // ts need not be (and usually is not) locked. 1124 func (ts *timers) updateMinWhenModified(when int64) { 1125 for { 1126 old := ts.minWhenModified.Load() 1127 if old != 0 && old < when { 1128 return 1129 } 1130 if ts.minWhenModified.CompareAndSwap(old, when) { 1131 return 1132 } 1133 } 1134 } 1135 1136 // timeSleepUntil returns the time when the next timer should fire. Returns 1137 // maxWhen if there are no timers. 1138 // This is only called by sysmon and checkdead. 1139 func timeSleepUntil() int64 { 1140 next := int64(maxWhen) 1141 1142 // Prevent allp slice changes. This is like retake. 1143 lock(&allpLock) 1144 for _, pp := range allp { 1145 if pp == nil { 1146 // This can happen if procresize has grown 1147 // allp but not yet created new Ps. 1148 continue 1149 } 1150 1151 if w := pp.timers.wakeTime(); w != 0 { 1152 next = min(next, w) 1153 } 1154 } 1155 unlock(&allpLock) 1156 1157 return next 1158 } 1159 1160 // Heap maintenance algorithms. 1161 // These algorithms check for slice index errors manually. 1162 // Slice index error can happen if the program is using racy 1163 // access to timers. We don't want to panic here, because 1164 // it will cause the program to crash with a mysterious 1165 // "panic holding locks" message. Instead, we panic while not 1166 // holding a lock. 1167 1168 // siftUp puts the timer at position i in the right place 1169 // in the heap by moving it up toward the top of the heap. 1170 func (ts *timers) siftUp(i int) { 1171 t := ts.heap 1172 if i >= len(t) { 1173 badTimer() 1174 } 1175 when := t[i].whenHeap 1176 if when <= 0 { 1177 badTimer() 1178 } 1179 tmp := t[i] 1180 for i > 0 { 1181 p := (i - 1) / 4 // parent 1182 if when >= t[p].whenHeap { 1183 break 1184 } 1185 t[i] = t[p] 1186 i = p 1187 } 1188 if tmp != t[i] { 1189 t[i] = tmp 1190 } 1191 } 1192 1193 // siftDown puts the timer at position i in the right place 1194 // in the heap by moving it down toward the bottom of the heap. 1195 func (ts *timers) siftDown(i int) { 1196 t := ts.heap 1197 n := len(t) 1198 if i >= n { 1199 badTimer() 1200 } 1201 when := t[i].whenHeap 1202 if when <= 0 { 1203 badTimer() 1204 } 1205 tmp := t[i] 1206 for { 1207 c := i*4 + 1 // left child 1208 c3 := c + 2 // mid child 1209 if c >= n { 1210 break 1211 } 1212 w := t[c].whenHeap 1213 if c+1 < n && t[c+1].whenHeap < w { 1214 w = t[c+1].whenHeap 1215 c++ 1216 } 1217 if c3 < n { 1218 w3 := t[c3].whenHeap 1219 if c3+1 < n && t[c3+1].whenHeap < w3 { 1220 w3 = t[c3+1].whenHeap 1221 c3++ 1222 } 1223 if w3 < w { 1224 w = w3 1225 c = c3 1226 } 1227 } 1228 if w >= when { 1229 break 1230 } 1231 t[i] = t[c] 1232 i = c 1233 } 1234 if tmp != t[i] { 1235 t[i] = tmp 1236 } 1237 } 1238 1239 // initHeap reestablishes the heap order in the slice ts.heap. 1240 // It takes O(n) time for n=len(ts.heap), not the O(n log n) of n repeated add operations. 1241 func (ts *timers) initHeap() { 1242 // Last possible element that needs sifting down is parent of last element; 1243 // last element is len(t)-1; parent of last element is (len(t)-1-1)/4. 1244 if len(ts.heap) <= 1 { 1245 return 1246 } 1247 for i := (len(ts.heap) - 1 - 1) / 4; i >= 0; i-- { 1248 ts.siftDown(i) 1249 } 1250 } 1251 1252 // badTimer is called if the timer data structures have been corrupted, 1253 // presumably due to racy use by the program. We panic here rather than 1254 // panicking due to invalid slice access while holding locks. 1255 // See issue #25686. 1256 func badTimer() { 1257 throw("timer data corruption") 1258 } 1259 1260 // Timer channels. 1261 1262 // maybeRunChan checks whether the timer needs to run 1263 // to send a value to its associated channel. If so, it does. 1264 // The timer must not be locked. 1265 func (t *timer) maybeRunChan() { 1266 if t.astate.Load()&timerHeaped != 0 { 1267 // If the timer is in the heap, the ordinary timer code 1268 // is in charge of sending when appropriate. 1269 return 1270 } 1271 1272 t.lock() 1273 now := nanotime() 1274 if t.state&timerHeaped != 0 || t.when == 0 || t.when > now { 1275 t.trace("maybeRunChan-") 1276 // Timer in the heap, or not running at all, or not triggered. 1277 t.unlock() 1278 return 1279 } 1280 t.trace("maybeRunChan+") 1281 systemstack(func() { 1282 t.unlockAndRun(now) 1283 }) 1284 } 1285 1286 // blockTimerChan is called when a channel op has decided to block on c. 1287 // The caller holds the channel lock for c and possibly other channels. 1288 // blockTimerChan makes sure that c is in a timer heap, 1289 // adding it if needed. 1290 func blockTimerChan(c *hchan) { 1291 t := c.timer 1292 t.lock() 1293 t.trace("blockTimerChan") 1294 if !t.isChan { 1295 badTimer() 1296 } 1297 1298 t.blocked++ 1299 1300 // If this is the first enqueue after a recent dequeue, 1301 // the timer may still be in the heap but marked as a zombie. 1302 // Unmark it in this case, if the timer is still pending. 1303 if t.state&timerHeaped != 0 && t.state&timerZombie != 0 && t.when > 0 { 1304 t.state &^= timerZombie 1305 t.ts.zombies.Add(-1) 1306 } 1307 1308 // t.maybeAdd must be called with t unlocked, 1309 // because it needs to lock t.ts before t. 1310 // Then it will do nothing if t.needsAdd(state) is false. 1311 // Check that now before the unlock, 1312 // avoiding the extra lock-lock-unlock-unlock 1313 // inside maybeAdd when t does not need to be added. 1314 add := t.needsAdd() 1315 t.unlock() 1316 if add { 1317 t.maybeAdd() 1318 } 1319 } 1320 1321 // unblockTimerChan is called when a channel op that was blocked on c 1322 // is no longer blocked. Every call to blockTimerChan must be paired with 1323 // a call to unblockTimerChan. 1324 // The caller holds the channel lock for c and possibly other channels. 1325 // unblockTimerChan removes c from the timer heap when nothing is 1326 // blocked on it anymore. 1327 func unblockTimerChan(c *hchan) { 1328 t := c.timer 1329 t.lock() 1330 t.trace("unblockTimerChan") 1331 if !t.isChan || t.blocked == 0 { 1332 badTimer() 1333 } 1334 t.blocked-- 1335 if t.blocked == 0 && t.state&timerHeaped != 0 && t.state&timerZombie == 0 { 1336 // Last goroutine that was blocked on this timer. 1337 // Mark for removal from heap but do not clear t.when, 1338 // so that we know what time it is still meant to trigger. 1339 t.state |= timerZombie 1340 t.ts.zombies.Add(1) 1341 } 1342 t.unlock() 1343 } 1344