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         "runtime/internal/atomic"
  12         "runtime/internal/sys"
  13         "unsafe"
  14 )
  15
  16 // Package time knows the layout of this structure.
  17 // If this struct changes, adjust ../time/sleep.go:/runtimeTimer.
  18 type timer struct {
  19         // If this timer is on a heap, which P's heap it is on.
  20         // puintptr rather than *p to match uintptr in the versions
  21         // of this struct defined in other packages.
  22         pp puintptr
  23
  24         // Timer wakes up at when, and then at when+period, ... (period > 0 only)
  25         // each time calling f(arg, now) in the timer goroutine, so f must be
  26         // a well-behaved function and not block.
  27         //
  28         // when must be positive on an active timer.
  29         when   int64
  30         period int64
  31         f      func(any, uintptr)
  32         arg    any
  33         seq    uintptr
  34
  35         // What to set the when field to in timerModifiedXX status.
  36         nextwhen int64
  37
  38         // The status field holds one of the values below.
  39         status atomic.Uint32
  40 }
  41
  42 // Code outside this file has to be careful in using a timer value.
  43 //
  44 // The pp, status, and nextwhen fields may only be used by code in this file.
  45 //
  46 // Code that creates a new timer value can set the when, period, f,
  47 // arg, and seq fields.
  48 // A new timer value may be passed to addtimer (called by time.startTimer).
  49 // After doing that no fields may be touched.
  50 //
  51 // An active timer (one that has been passed to addtimer) may be
  52 // passed to deltimer (time.stopTimer), after which it is no longer an
  53 // active timer. It is an inactive timer.
  54 // In an inactive timer the period, f, arg, and seq fields may be modified,
  55 // but not the when field.
  56 // It's OK to just drop an inactive timer and let the GC collect it.
  57 // It's not OK to pass an inactive timer to addtimer.
  58 // Only newly allocated timer values may be passed to addtimer.
  59 //
  60 // An active timer may be passed to modtimer. No fields may be touched.
  61 // It remains an active timer.
  62 //
  63 // An inactive timer may be passed to resettimer to turn into an
  64 // active timer with an updated when field.
  65 // It's OK to pass a newly allocated timer value to resettimer.
  66 //
  67 // Timer operations are addtimer, deltimer, modtimer, resettimer,
  68 // cleantimers, adjusttimers, and runtimer.
  69 //
  70 // We don't permit calling addtimer/deltimer/modtimer/resettimer simultaneously,
  71 // but adjusttimers and runtimer can be called at the same time as any of those.
  72 //
  73 // Active timers live in heaps attached to P, in the timers field.
  74 // Inactive timers live there too temporarily, until they are removed.
  75 //
  76 // addtimer:
  77 //   timerNoStatus   -> timerWaiting
  78 //   anything else   -> panic: invalid value
  79 // deltimer:
  80 //   timerWaiting         -> timerModifying -> timerDeleted
  81 //   timerModifiedEarlier -> timerModifying -> timerDeleted
  82 //   timerModifiedLater   -> timerModifying -> timerDeleted
  83 //   timerNoStatus        -> do nothing
  84 //   timerDeleted         -> do nothing
  85 //   timerRemoving        -> do nothing
  86 //   timerRemoved         -> do nothing
  87 //   timerRunning         -> wait until status changes
  88 //   timerMoving          -> wait until status changes
  89 //   timerModifying       -> wait until status changes
  90 // modtimer:
  91 //   timerWaiting    -> timerModifying -> timerModifiedXX
  92 //   timerModifiedXX -> timerModifying -> timerModifiedYY
  93 //   timerNoStatus   -> timerModifying -> timerWaiting
  94 //   timerRemoved    -> timerModifying -> timerWaiting
  95 //   timerDeleted    -> timerModifying -> timerModifiedXX
  96 //   timerRunning    -> wait until status changes
  97 //   timerMoving     -> wait until status changes
  98 //   timerRemoving   -> wait until status changes
  99 //   timerModifying  -> wait until status changes
 100 // cleantimers (looks in P's timer heap):
 101 //   timerDeleted    -> timerRemoving -> timerRemoved
 102 //   timerModifiedXX -> timerMoving -> timerWaiting
 103 // adjusttimers (looks in P's timer heap):
 104 //   timerDeleted    -> timerRemoving -> timerRemoved
 105 //   timerModifiedXX -> timerMoving -> timerWaiting
 106 // runtimer (looks in P's timer heap):
 107 //   timerNoStatus   -> panic: uninitialized timer
 108 //   timerWaiting    -> timerWaiting or
 109 //   timerWaiting    -> timerRunning -> timerNoStatus or
 110 //   timerWaiting    -> timerRunning -> timerWaiting
 111 //   timerModifying  -> wait until status changes
 112 //   timerModifiedXX -> timerMoving -> timerWaiting
 113 //   timerDeleted    -> timerRemoving -> timerRemoved
 114 //   timerRunning    -> panic: concurrent runtimer calls
 115 //   timerRemoved    -> panic: inconsistent timer heap
 116 //   timerRemoving   -> panic: inconsistent timer heap
 117 //   timerMoving     -> panic: inconsistent timer heap
 118
 119 // Values for the timer status field.
 120 const (
 121         // Timer has no status set yet.
 122         timerNoStatus = iota
 123
 124         // Waiting for timer to fire.
 125         // The timer is in some P's heap.
 126         timerWaiting
 127
 128         // Running the timer function.
 129         // A timer will only have this status briefly.
 130         timerRunning
 131
 132         // The timer is deleted and should be removed.
 133         // It should not be run, but it is still in some P's heap.
 134         timerDeleted
 135
 136         // The timer is being removed.
 137         // The timer will only have this status briefly.
 138         timerRemoving
 139
 140         // The timer has been stopped.
 141         // It is not in any P's heap.
 142         timerRemoved
 143
 144         // The timer is being modified.
 145         // The timer will only have this status briefly.
 146         timerModifying
 147
 148         // The timer has been modified to an earlier time.
 149         // The new when value is in the nextwhen field.
 150         // The timer is in some P's heap, possibly in the wrong place.
 151         timerModifiedEarlier
 152
 153         // The timer has been modified to the same or a later time.
 154         // The new when value is in the nextwhen field.
 155         // The timer is in some P's heap, possibly in the wrong place.
 156         timerModifiedLater
 157
 158         // The timer has been modified and is being moved.
 159         // The timer will only have this status briefly.
 160         timerMoving
 161 )
 162
 163 // maxWhen is the maximum value for timer's when field.
 164 const maxWhen = 1<<63 - 1
 165
 166 // verifyTimers can be set to true to add debugging checks that the
 167 // timer heaps are valid.
 168 const verifyTimers = false
 169
 170 // Package time APIs.
 171 // Godoc uses the comments in package time, not these.
 172
 173 // time.now is implemented in assembly.
 174
 175 // timeSleep puts the current goroutine to sleep for at least ns nanoseconds.
 176 //
 177 //go:linkname timeSleep time.Sleep
 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 { // check for overflow.
 193                 t.nextwhen = maxWhen
 194         }
 195         gopark(resetForSleep, unsafe.Pointer(t), waitReasonSleep, traceBlockSleep, 1)
 196 }
 197
 198 // resetForSleep is called after the goroutine is parked for timeSleep.
 199 // We can't call resettimer in timeSleep itself because if this is a short
 200 // sleep and there are many goroutines then the P can wind up running the
 201 // timer function, goroutineReady, before the goroutine has been parked.
 202 func resetForSleep(gp *g, ut unsafe.Pointer) bool {
 203         t := (*timer)(ut)
 204         resettimer(t, t.nextwhen)
 205         return true
 206 }
 207
 208 // startTimer adds t to the timer heap.
 209 //
 210 //go:linkname startTimer time.startTimer
 211 func startTimer(t *timer) {
 212         if raceenabled {
 213                 racerelease(unsafe.Pointer(t))
 214         }
 215         addtimer(t)
 216 }
 217
 218 // stopTimer stops a timer.
 219 // It reports whether t was stopped before being run.
 220 //
 221 //go:linkname stopTimer time.stopTimer
 222 func stopTimer(t *timer) bool {
 223         return deltimer(t)
 224 }
 225
 226 // resetTimer resets an inactive timer, adding it to the heap.
 227 //
 228 // Reports whether the timer was modified before it was run.
 229 //
 230 //go:linkname resetTimer time.resetTimer
 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 // modTimer modifies an existing timer.
 239 //
 240 //go:linkname modTimer time.modTimer
 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 // Go runtime.
 246
 247 // Ready the goroutine arg.
 248 func goroutineReady(arg any, seq uintptr) {
 249         goready(arg.(*g), 0)
 250 }
 251
 252 // Note: this changes some unsynchronized operations to synchronized operations
 253 // addtimer adds a timer to the current P.
 254 // This should only be called with a newly created timer.
 255 // That avoids the risk of changing the when field of a timer in some P's heap,
 256 // which could cause the heap to become unsorted.
 257 func addtimer(t *timer) {
 258         // when must be positive. A negative value will cause runtimer to
 259         // overflow during its delta calculation and never expire other runtime
 260         // timers. Zero will cause checkTimers to fail to notice the timer.
 261         if t.when <= 0 {
 262                 throw("timer when must be positive")
 263         }
 264         if t.period < 0 {
 265                 throw("timer period must be non-negative")
 266         }
 267         if t.status.Load() != timerNoStatus {
 268                 throw("addtimer called with initialized timer")
 269         }
 270         t.status.Store(timerWaiting)
 271
 272         when := t.when
 273
 274         // Disable preemption while using pp to avoid changing another P's heap.
 275         mp := acquirem()
 276
 277         pp := getg().m.p.ptr()
 278         lock(&pp.timersLock)
 279         cleantimers(pp)
 280         doaddtimer(pp, t)
 281         unlock(&pp.timersLock)
 282
 283         wakeNetPoller(when)
 284
 285         releasem(mp)
 286 }
 287
 288 // doaddtimer adds t to the current P's heap.
 289 // The caller must have locked the timers for pp.
 290 func doaddtimer(pp *p, t *timer) {
 291         // Timers rely on the network poller, so make sure the poller
 292         // has started.
 293         if netpollInited.Load() == 0 {
 294                 netpollGenericInit()
 295         }
 296
 297         if t.pp != 0 {
 298                 throw("doaddtimer: P already set in timer")
 299         }
 300         t.pp.set(pp)
 301         i := len(pp.timers)
 302         pp.timers = append(pp.timers, t)
 303         siftupTimer(pp.timers, i)
 304         if t == pp.timers[0] {
 305                 pp.timer0When.Store(t.when)
 306         }
 307         pp.numTimers.Add(1)
 308 }
 309
 310 // deltimer deletes the timer t. It may be on some other P, so we can't
 311 // actually remove it from the timers heap. We can only mark it as deleted.
 312 // It will be removed in due course by the P whose heap it is on.
 313 // Reports whether the timer was removed before it was run.
 314 func deltimer(t *timer) bool {
 315         for {
 316                 switch s := t.status.Load(); s {
 317                 case timerWaiting, timerModifiedLater:
 318                         // Prevent preemption while the timer is in timerModifying.
 319                         // This could lead to a self-deadlock. See #38070.
 320                         mp := acquirem()
 321                         if t.status.CompareAndSwap(s, timerModifying) {
 322                                 // Must fetch t.pp before changing status,
 323                                 // as cleantimers in another goroutine
 324                                 // can clear t.pp of a timerDeleted timer.
 325                                 tpp := t.pp.ptr()
 326                                 if !t.status.CompareAndSwap(timerModifying, timerDeleted) {
 327                                         badTimer()
 328                                 }
 329                                 releasem(mp)
 330                                 tpp.deletedTimers.Add(1)
 331                                 // Timer was not yet run.
 332                                 return true
 333                         } else {
 334                                 releasem(mp)
 335                         }
 336                 case timerModifiedEarlier:
 337                         // Prevent preemption while the timer is in timerModifying.
 338                         // This could lead to a self-deadlock. See #38070.
 339                         mp := acquirem()
 340                         if t.status.CompareAndSwap(s, timerModifying) {
 341                                 // Must fetch t.pp before setting status
 342                                 // to timerDeleted.
 343                                 tpp := t.pp.ptr()
 344                                 if !t.status.CompareAndSwap(timerModifying, timerDeleted) {
 345                                         badTimer()
 346                                 }
 347                                 releasem(mp)
 348                                 tpp.deletedTimers.Add(1)
 349                                 // Timer was not yet run.
 350                                 return true
 351                         } else {
 352                                 releasem(mp)
 353                         }
 354                 case timerDeleted, timerRemoving, timerRemoved:
 355                         // Timer was already run.
 356                         return false
 357                 case timerRunning, timerMoving:
 358                         // The timer is being run or moved, by a different P.
 359                         // Wait for it to complete.
 360                         osyield()
 361                 case timerNoStatus:
 362                         // Removing timer that was never added or
 363                         // has already been run. Also see issue 21874.
 364                         return false
 365                 case timerModifying:
 366                         // Simultaneous calls to deltimer and modtimer.
 367                         // Wait for the other call to complete.
 368                         osyield()
 369                 default:
 370                         badTimer()
 371                 }
 372         }
 373 }
 374
 375 // dodeltimer removes timer i from the current P's heap.
 376 // We are locked on the P when this is called.
 377 // It returns the smallest changed index in pp.timers.
 378 // The caller must have locked the timers for pp.
 379 func dodeltimer(pp *p, i int) int {
 380         if t := pp.timers[i]; t.pp.ptr() != pp {
 381                 throw("dodeltimer: wrong P")
 382         } else {
 383                 t.pp = 0
 384         }
 385         last := len(pp.timers) - 1
 386         if i != last {
 387                 pp.timers[i] = pp.timers[last]
 388         }
 389         pp.timers[last] = nil
 390         pp.timers = pp.timers[:last]
 391         smallestChanged := i
 392         if i != last {
 393                 // Moving to i may have moved the last timer to a new parent,
 394                 // so sift up to preserve the heap guarantee.
 395                 smallestChanged = siftupTimer(pp.timers, i)
 396                 siftdownTimer(pp.timers, i)
 397         }
 398         if i == 0 {
 399                 updateTimer0When(pp)
 400         }
 401         n := pp.numTimers.Add(-1)
 402         if n == 0 {
 403                 // If there are no timers, then clearly none are modified.
 404                 pp.timerModifiedEarliest.Store(0)
 405         }
 406         return smallestChanged
 407 }
 408
 409 // dodeltimer0 removes timer 0 from the current P's heap.
 410 // We are locked on the P when this is called.
 411 // It reports whether it saw no problems due to races.
 412 // The caller must have locked the timers for pp.
 413 func dodeltimer0(pp *p) {
 414         if t := pp.timers[0]; t.pp.ptr() != pp {
 415                 throw("dodeltimer0: wrong P")
 416         } else {
 417                 t.pp = 0
 418         }
 419         last := len(pp.timers) - 1
 420         if last > 0 {
 421                 pp.timers[0] = pp.timers[last]
 422         }
 423         pp.timers[last] = nil
 424         pp.timers = pp.timers[:last]
 425         if last > 0 {
 426                 siftdownTimer(pp.timers, 0)
 427         }
 428         updateTimer0When(pp)
 429         n := pp.numTimers.Add(-1)
 430         if n == 0 {
 431                 // If there are no timers, then clearly none are modified.
 432                 pp.timerModifiedEarliest.Store(0)
 433         }
 434 }
 435
 436 // modtimer modifies an existing timer.
 437 // This is called by the netpoll code or time.Ticker.Reset or time.Timer.Reset.
 438 // Reports whether the timer was modified before it was run.
 439 func modtimer(t *timer, when, period int64, f func(any, uintptr), arg any, seq uintptr) bool {
 440         if when <= 0 {
 441                 throw("timer when must be positive")
 442         }
 443         if period < 0 {
 444                 throw("timer period must be non-negative")
 445         }
 446
 447         status := uint32(timerNoStatus)
 448         wasRemoved := false
 449         var pending bool
 450         var mp *m
 451 loop:
 452         for {
 453                 switch status = t.status.Load(); status {
 454                 case timerWaiting, timerModifiedEarlier, timerModifiedLater:
 455                         // Prevent preemption while the timer is in timerModifying.
 456                         // This could lead to a self-deadlock. See #38070.
 457                         mp = acquirem()
 458                         if t.status.CompareAndSwap(status, timerModifying) {
 459                                 pending = true // timer not yet run
 460                                 break loop
 461                         }
 462                         releasem(mp)
 463                 case timerNoStatus, timerRemoved:
 464                         // Prevent preemption while the timer is in timerModifying.
 465                         // This could lead to a self-deadlock. See #38070.
 466                         mp = acquirem()
 467
 468                         // Timer was already run and t is no longer in a heap.
 469                         // Act like addtimer.
 470                         if t.status.CompareAndSwap(status, timerModifying) {
 471                                 wasRemoved = true
 472                                 pending = false // timer already run or stopped
 473                                 break loop
 474                         }
 475                         releasem(mp)
 476                 case timerDeleted:
 477                         // Prevent preemption while the timer is in timerModifying.
 478                         // This could lead to a self-deadlock. See #38070.
 479                         mp = acquirem()
 480                         if t.status.CompareAndSwap(status, timerModifying) {
 481                                 t.pp.ptr().deletedTimers.Add(-1)
 482                                 pending = false // timer already stopped
 483                                 break loop
 484                         }
 485                         releasem(mp)
 486                 case timerRunning, timerRemoving, timerMoving:
 487                         // The timer is being run or moved, by a different P.
 488                         // Wait for it to complete.
 489                         osyield()
 490                 case timerModifying:
 491                         // Multiple simultaneous calls to modtimer.
 492                         // Wait for the other call to complete.
 493                         osyield()
 494                 default:
 495                         badTimer()
 496                 }
 497         }
 498
 499         t.period = period
 500         t.f = f
 501         t.arg = arg
 502         t.seq = seq
 503
 504         if wasRemoved {
 505                 t.when = when
 506                 pp := getg().m.p.ptr()
 507                 lock(&pp.timersLock)
 508                 doaddtimer(pp, t)
 509                 unlock(&pp.timersLock)
 510                 if !t.status.CompareAndSwap(timerModifying, timerWaiting) {
 511                         badTimer()
 512                 }
 513                 releasem(mp)
 514                 wakeNetPoller(when)
 515         } else {
 516                 // The timer is in some other P's heap, so we can't change
 517                 // the when field. If we did, the other P's heap would
 518                 // be out of order. So we put the new when value in the
 519                 // nextwhen field, and let the other P set the when field
 520                 // when it is prepared to resort the heap.
 521                 t.nextwhen = when
 522
 523                 newStatus := uint32(timerModifiedLater)
 524                 if when < t.when {
 525                         newStatus = timerModifiedEarlier
 526                 }
 527
 528                 tpp := t.pp.ptr()
 529
 530                 if newStatus == timerModifiedEarlier {
 531                         updateTimerModifiedEarliest(tpp, when)
 532                 }
 533
 534                 // Set the new status of the timer.
 535                 if !t.status.CompareAndSwap(timerModifying, newStatus) {
 536                         badTimer()
 537                 }
 538                 releasem(mp)
 539
 540                 // If the new status is earlier, wake up the poller.
 541                 if newStatus == timerModifiedEarlier {
 542                         wakeNetPoller(when)
 543                 }
 544         }
 545
 546         return pending
 547 }
 548
 549 // resettimer resets the time when a timer should fire.
 550 // If used for an inactive timer, the timer will become active.
 551 // This should be called instead of addtimer if the timer value has been,
 552 // or may have been, used previously.
 553 // Reports whether the timer was modified before it was run.
 554 func resettimer(t *timer, when int64) bool {
 555         return modtimer(t, when, t.period, t.f, t.arg, t.seq)
 556 }
 557
 558 // cleantimers cleans up the head of the timer queue. This speeds up
 559 // programs that create and delete timers; leaving them in the heap
 560 // slows down addtimer. Reports whether no timer problems were found.
 561 // The caller must have locked the timers for pp.
 562 func cleantimers(pp *p) {
 563         gp := getg()
 564         for {
 565                 if len(pp.timers) == 0 {
 566                         return
 567                 }
 568
 569                 // This loop can theoretically run for a while, and because
 570                 // it is holding timersLock it cannot be preempted.
 571                 // If someone is trying to preempt us, just return.
 572                 // We can clean the timers later.
 573                 if gp.preemptStop {
 574                         return
 575                 }
 576
 577                 t := pp.timers[0]
 578                 if t.pp.ptr() != pp {
 579                         throw("cleantimers: bad p")
 580                 }
 581                 switch s := t.status.Load(); s {
 582                 case timerDeleted:
 583                         if !t.status.CompareAndSwap(s, timerRemoving) {
 584                                 continue
 585                         }
 586                         dodeltimer0(pp)
 587                         if !t.status.CompareAndSwap(timerRemoving, timerRemoved) {
 588                                 badTimer()
 589                         }
 590                         pp.deletedTimers.Add(-1)
 591                 case timerModifiedEarlier, timerModifiedLater:
 592                         if !t.status.CompareAndSwap(s, timerMoving) {
 593                                 continue
 594                         }
 595                         // Now we can change the when field.
 596                         t.when = t.nextwhen
 597                         // Move t to the right position.
 598                         dodeltimer0(pp)
 599                         doaddtimer(pp, t)
 600                         if !t.status.CompareAndSwap(timerMoving, timerWaiting) {
 601                                 badTimer()
 602                         }
 603                 default:
 604                         // Head of timers does not need adjustment.
 605                         return
 606                 }
 607         }
 608 }
 609
 610 // moveTimers moves a slice of timers to pp. The slice has been taken
 611 // from a different P.
 612 // This is currently called when the world is stopped, but the caller
 613 // is expected to have locked the timers for pp.
 614 func moveTimers(pp *p, timers []*timer) {
 615         for _, t := range timers {
 616         loop:
 617                 for {
 618                         switch s := t.status.Load(); s {
 619                         case timerWaiting:
 620                                 if !t.status.CompareAndSwap(s, timerMoving) {
 621                                         continue
 622                                 }
 623                                 t.pp = 0
 624                                 doaddtimer(pp, t)
 625                                 if !t.status.CompareAndSwap(timerMoving, timerWaiting) {
 626                                         badTimer()
 627                                 }
 628                                 break loop
 629                         case timerModifiedEarlier, timerModifiedLater:
 630                                 if !t.status.CompareAndSwap(s, timerMoving) {
 631                                         continue
 632                                 }
 633                                 t.when = t.nextwhen
 634                                 t.pp = 0
 635                                 doaddtimer(pp, t)
 636                                 if !t.status.CompareAndSwap(timerMoving, timerWaiting) {
 637                                         badTimer()
 638                                 }
 639                                 break loop
 640                         case timerDeleted:
 641                                 if !t.status.CompareAndSwap(s, timerRemoved) {
 642                                         continue
 643                                 }
 644                                 t.pp = 0
 645                                 // We no longer need this timer in the heap.
 646                                 break loop
 647                         case timerModifying:
 648                                 // Loop until the modification is complete.
 649                                 osyield()
 650                         case timerNoStatus, timerRemoved:
 651                                 // We should not see these status values in a timers heap.
 652                                 badTimer()
 653                         case timerRunning, timerRemoving, timerMoving:
 654                                 // Some other P thinks it owns this timer,
 655                                 // which should not happen.
 656                                 badTimer()
 657                         default:
 658                                 badTimer()
 659                         }
 660                 }
 661         }
 662 }
 663
 664 // adjusttimers looks through the timers in the current P's heap for
 665 // any timers that have been modified to run earlier, and puts them in
 666 // the correct place in the heap. While looking for those timers,
 667 // it also moves timers that have been modified to run later,
 668 // and removes deleted timers. The caller must have locked the timers for pp.
 669 func adjusttimers(pp *p, now int64) {
 670         // If we haven't yet reached the time of the first timerModifiedEarlier
 671         // timer, don't do anything. This speeds up programs that adjust
 672         // a lot of timers back and forth if the timers rarely expire.
 673         // We'll postpone looking through all the adjusted timers until
 674         // one would actually expire.
 675         first := pp.timerModifiedEarliest.Load()
 676         if first == 0 || first > now {
 677                 if verifyTimers {
 678                         verifyTimerHeap(pp)
 679                 }
 680                 return
 681         }
 682
 683         // We are going to clear all timerModifiedEarlier timers.
 684         pp.timerModifiedEarliest.Store(0)
 685
 686         var moved []*timer
 687         for i := 0; i < len(pp.timers); i++ {
 688                 t := pp.timers[i]
 689                 if t.pp.ptr() != pp {
 690                         throw("adjusttimers: bad p")
 691                 }
 692                 switch s := t.status.Load(); s {
 693                 case timerDeleted:
 694                         if t.status.CompareAndSwap(s, timerRemoving) {
 695                                 changed := dodeltimer(pp, i)
 696                                 if !t.status.CompareAndSwap(timerRemoving, timerRemoved) {
 697                                         badTimer()
 698                                 }
 699                                 pp.deletedTimers.Add(-1)
 700                                 // Go back to the earliest changed heap entry.
 701                                 // "- 1" because the loop will add 1.
 702                                 i = changed - 1
 703                         }
 704                 case timerModifiedEarlier, timerModifiedLater:
 705                         if t.status.CompareAndSwap(s, timerMoving) {
 706                                 // Now we can change the when field.
 707                                 t.when = t.nextwhen
 708                                 // Take t off the heap, and hold onto it.
 709                                 // We don't add it back yet because the
 710                                 // heap manipulation could cause our
 711                                 // loop to skip some other timer.
 712                                 changed := dodeltimer(pp, i)
 713                                 moved = append(moved, t)
 714                                 // Go back to the earliest changed heap entry.
 715                                 // "- 1" because the loop will add 1.
 716                                 i = changed - 1
 717                         }
 718                 case timerNoStatus, timerRunning, timerRemoving, timerRemoved, timerMoving:
 719                         badTimer()
 720                 case timerWaiting:
 721                         // OK, nothing to do.
 722                 case timerModifying:
 723                         // Check again after modification is complete.
 724                         osyield()
 725                         i--
 726                 default:
 727                         badTimer()
 728                 }
 729         }
 730
 731         if len(moved) > 0 {
 732                 addAdjustedTimers(pp, moved)
 733         }
 734
 735         if verifyTimers {
 736                 verifyTimerHeap(pp)
 737         }
 738 }
 739
 740 // addAdjustedTimers adds any timers we adjusted in adjusttimers
 741 // back to the timer heap.
 742 func addAdjustedTimers(pp *p, moved []*timer) {
 743         for _, t := range moved {
 744                 doaddtimer(pp, t)
 745                 if !t.status.CompareAndSwap(timerMoving, timerWaiting) {
 746                         badTimer()
 747                 }
 748         }
 749 }
 750
 751 // nobarrierWakeTime looks at P's timers and returns the time when we
 752 // should wake up the netpoller. It returns 0 if there are no timers.
 753 // This function is invoked when dropping a P, and must run without
 754 // any write barriers.
 755 //
 756 //go:nowritebarrierrec
 757 func nobarrierWakeTime(pp *p) int64 {
 758         next := pp.timer0When.Load()
 759         nextAdj := pp.timerModifiedEarliest.Load()
 760         if next == 0 || (nextAdj != 0 && nextAdj < next) {
 761                 next = nextAdj
 762         }
 763         return next
 764 }
 765
 766 // runtimer examines the first timer in timers. If it is ready based on now,
 767 // it runs the timer and removes or updates it.
 768 // Returns 0 if it ran a timer, -1 if there are no more timers, or the time
 769 // when the first timer should run.
 770 // The caller must have locked the timers for pp.
 771 // If a timer is run, this will temporarily unlock the timers.
 772 //
 773 //go:systemstack
 774 func runtimer(pp *p, now int64) int64 {
 775         for {
 776                 t := pp.timers[0]
 777                 if t.pp.ptr() != pp {
 778                         throw("runtimer: bad p")
 779                 }
 780                 switch s := t.status.Load(); s {
 781                 case timerWaiting:
 782                         if t.when > now {
 783                                 // Not ready to run.
 784                                 return t.when
 785                         }
 786
 787                         if !t.status.CompareAndSwap(s, timerRunning) {
 788                                 continue
 789                         }
 790                         // Note that runOneTimer may temporarily unlock
 791                         // pp.timersLock.
 792                         runOneTimer(pp, t, now)
 793                         return 0
 794
 795                 case timerDeleted:
 796                         if !t.status.CompareAndSwap(s, timerRemoving) {
 797                                 continue
 798                         }
 799                         dodeltimer0(pp)
 800                         if !t.status.CompareAndSwap(timerRemoving, timerRemoved) {
 801                                 badTimer()
 802                         }
 803                         pp.deletedTimers.Add(-1)
 804                         if len(pp.timers) == 0 {
 805                                 return -1
 806                         }
 807
 808                 case timerModifiedEarlier, timerModifiedLater:
 809                         if !t.status.CompareAndSwap(s, timerMoving) {
 810                                 continue
 811                         }
 812                         t.when = t.nextwhen
 813                         dodeltimer0(pp)
 814                         doaddtimer(pp, t)
 815                         if !t.status.CompareAndSwap(timerMoving, timerWaiting) {
 816                                 badTimer()
 817                         }
 818
 819                 case timerModifying:
 820                         // Wait for modification to complete.
 821                         osyield()
 822
 823                 case timerNoStatus, timerRemoved:
 824                         // Should not see a new or inactive timer on the heap.
 825                         badTimer()
 826                 case timerRunning, timerRemoving, timerMoving:
 827                         // These should only be set when timers are locked,
 828                         // and we didn't do it.
 829                         badTimer()
 830                 default:
 831                         badTimer()
 832                 }
 833         }
 834 }
 835
 836 // runOneTimer runs a single timer.
 837 // The caller must have locked the timers for pp.
 838 // This will temporarily unlock the timers while running the timer function.
 839 //
 840 //go:systemstack
 841 func runOneTimer(pp *p, t *timer, now int64) {
 842         if raceenabled {
 843                 ppcur := getg().m.p.ptr()
 844                 if ppcur.timerRaceCtx == 0 {
 845                         ppcur.timerRaceCtx = racegostart(abi.FuncPCABIInternal(runtimer) + sys.PCQuantum)
 846                 }
 847                 raceacquirectx(ppcur.timerRaceCtx, unsafe.Pointer(t))
 848         }
 849
 850         f := t.f
 851         arg := t.arg
 852         seq := t.seq
 853
 854         if t.period > 0 {
 855                 // Leave in heap but adjust next time to fire.
 856                 delta := t.when - now
 857                 t.when += t.period * (1 + -delta/t.period)
 858                 if t.when < 0 { // check for overflow.
 859                         t.when = maxWhen
 860                 }
 861                 siftdownTimer(pp.timers, 0)
 862                 if !t.status.CompareAndSwap(timerRunning, timerWaiting) {
 863                         badTimer()
 864                 }
 865                 updateTimer0When(pp)
 866         } else {
 867                 // Remove from heap.
 868                 dodeltimer0(pp)
 869                 if !t.status.CompareAndSwap(timerRunning, timerNoStatus) {
 870                         badTimer()
 871                 }
 872         }
 873
 874         if raceenabled {
 875                 // Temporarily use the current P's racectx for g0.
 876                 gp := getg()
 877                 if gp.racectx != 0 {
 878                         throw("runOneTimer: unexpected racectx")
 879                 }
 880                 gp.racectx = gp.m.p.ptr().timerRaceCtx
 881         }
 882
 883         unlock(&pp.timersLock)
 884
 885         f(arg, seq)
 886
 887         lock(&pp.timersLock)
 888
 889         if raceenabled {
 890                 gp := getg()
 891                 gp.racectx = 0
 892         }
 893 }
 894
 895 // clearDeletedTimers removes all deleted timers from the P's timer heap.
 896 // This is used to avoid clogging up the heap if the program
 897 // starts a lot of long-running timers and then stops them.
 898 // For example, this can happen via context.WithTimeout.
 899 //
 900 // This is the only function that walks through the entire timer heap,
 901 // other than moveTimers which only runs when the world is stopped.
 902 //
 903 // The caller must have locked the timers for pp.
 904 func clearDeletedTimers(pp *p) {
 905         // We are going to clear all timerModifiedEarlier timers.
 906         // Do this now in case new ones show up while we are looping.
 907         pp.timerModifiedEarliest.Store(0)
 908
 909         cdel := int32(0)
 910         to := 0
 911         changedHeap := false
 912         timers := pp.timers
 913 nextTimer:
 914         for _, t := range timers {
 915                 for {
 916                         switch s := t.status.Load(); s {
 917                         case timerWaiting:
 918                                 if changedHeap {
 919                                         timers[to] = t
 920                                         siftupTimer(timers, to)
 921                                 }
 922                                 to++
 923                                 continue nextTimer
 924                         case timerModifiedEarlier, timerModifiedLater:
 925                                 if t.status.CompareAndSwap(s, timerMoving) {
 926                                         t.when = t.nextwhen
 927                                         timers[to] = t
 928                                         siftupTimer(timers, to)
 929                                         to++
 930                                         changedHeap = true
 931                                         if !t.status.CompareAndSwap(timerMoving, timerWaiting) {
 932                                                 badTimer()
 933                                         }
 934                                         continue nextTimer
 935                                 }
 936                         case timerDeleted:
 937                                 if t.status.CompareAndSwap(s, timerRemoving) {
 938                                         t.pp = 0
 939                                         cdel++
 940                                         if !t.status.CompareAndSwap(timerRemoving, timerRemoved) {
 941                                                 badTimer()
 942                                         }
 943                                         changedHeap = true
 944                                         continue nextTimer
 945                                 }
 946                         case timerModifying:
 947                                 // Loop until modification complete.
 948                                 osyield()
 949                         case timerNoStatus, timerRemoved:
 950                                 // We should not see these status values in a timer heap.
 951                                 badTimer()
 952                         case timerRunning, timerRemoving, timerMoving:
 953                                 // Some other P thinks it owns this timer,
 954                                 // which should not happen.
 955                                 badTimer()
 956                         default:
 957                                 badTimer()
 958                         }
 959                 }
 960         }
 961
 962         // Set remaining slots in timers slice to nil,
 963         // so that the timer values can be garbage collected.
 964         for i := to; i < len(timers); i++ {
 965                 timers[i] = nil
 966         }
 967
 968         pp.deletedTimers.Add(-cdel)
 969         pp.numTimers.Add(-cdel)
 970
 971         timers = timers[:to]
 972         pp.timers = timers
 973         updateTimer0When(pp)
 974
 975         if verifyTimers {
 976                 verifyTimerHeap(pp)
 977         }
 978 }
 979
 980 // verifyTimerHeap verifies that the timer heap is in a valid state.
 981 // This is only for debugging, and is only called if verifyTimers is true.
 982 // The caller must have locked the timers.
 983 func verifyTimerHeap(pp *p) {
 984         for i, t := range pp.timers {
 985                 if i == 0 {
 986                         // First timer has no parent.
 987                         continue
 988                 }
 989
 990                 // The heap is 4-ary. See siftupTimer and siftdownTimer.
 991                 p := (i - 1) / 4
 992                 if t.when < pp.timers[p].when {
 993                         print("bad timer heap at ", i, ": ", p, ": ", pp.timers[p].when, ", ", i, ": ", t.when, "\n")
 994                         throw("bad timer heap")
 995                 }
 996         }
 997         if numTimers := int(pp.numTimers.Load()); len(pp.timers) != numTimers {
 998                 println("timer heap len", len(pp.timers), "!= numTimers", numTimers)
 999                 throw("bad timer heap len")
1000         }
1001 }
1002
1003 // updateTimer0When sets the P's timer0When field.
1004 // The caller must have locked the timers for pp.
1005 func updateTimer0When(pp *p) {
1006         if len(pp.timers) == 0 {
1007                 pp.timer0When.Store(0)
1008         } else {
1009                 pp.timer0When.Store(pp.timers[0].when)
1010         }
1011 }
1012
1013 // updateTimerModifiedEarliest updates the recorded nextwhen field of the
1014 // earlier timerModifiedEarier value.
1015 // The timers for pp will not be locked.
1016 func updateTimerModifiedEarliest(pp *p, nextwhen int64) {
1017         for {
1018                 old := pp.timerModifiedEarliest.Load()
1019                 if old != 0 && old < nextwhen {
1020                         return
1021                 }
1022
1023                 if pp.timerModifiedEarliest.CompareAndSwap(old, nextwhen) {
1024                         return
1025                 }
1026         }
1027 }
1028
1029 // timeSleepUntil returns the time when the next timer should fire. Returns
1030 // maxWhen if there are no timers.
1031 // This is only called by sysmon and checkdead.
1032 func timeSleepUntil() int64 {
1033         next := int64(maxWhen)
1034
1035         // Prevent allp slice changes. This is like retake.
1036         lock(&allpLock)
1037         for _, pp := range allp {
1038                 if pp == nil {
1039                         // This can happen if procresize has grown
1040                         // allp but not yet created new Ps.
1041                         continue
1042                 }
1043
1044                 w := pp.timer0When.Load()
1045                 if w != 0 && w < next {
1046                         next = w
1047                 }
1048
1049                 w = pp.timerModifiedEarliest.Load()
1050                 if w != 0 && w < next {
1051                         next = w
1052                 }
1053         }
1054         unlock(&allpLock)
1055
1056         return next
1057 }
1058
1059 // Heap maintenance algorithms.
1060 // These algorithms check for slice index errors manually.
1061 // Slice index error can happen if the program is using racy
1062 // access to timers. We don't want to panic here, because
1063 // it will cause the program to crash with a mysterious
1064 // "panic holding locks" message. Instead, we panic while not
1065 // holding a lock.
1066
1067 // siftupTimer puts the timer at position i in the right place
1068 // in the heap by moving it up toward the top of the heap.
1069 // It returns the smallest changed index.
1070 func siftupTimer(t []*timer, i int) int {
1071         if i >= len(t) {
1072                 badTimer()
1073         }
1074         when := t[i].when
1075         if when <= 0 {
1076                 badTimer()
1077         }
1078         tmp := t[i]
1079         for i > 0 {
1080                 p := (i - 1) / 4 // parent
1081                 if when >= t[p].when {
1082                         break
1083                 }
1084                 t[i] = t[p]
1085                 i = p
1086         }
1087         if tmp != t[i] {
1088                 t[i] = tmp
1089         }
1090         return i
1091 }
1092
1093 // siftdownTimer puts the timer at position i in the right place
1094 // in the heap by moving it down toward the bottom of the heap.
1095 func siftdownTimer(t []*timer, i int) {
1096         n := len(t)
1097         if i >= n {
1098                 badTimer()
1099         }
1100         when := t[i].when
1101         if when <= 0 {
1102                 badTimer()
1103         }
1104         tmp := t[i]
1105         for {
1106                 c := i*4 + 1 // left child
1107                 c3 := c + 2  // mid child
1108                 if c >= n {
1109                         break
1110                 }
1111                 w := t[c].when
1112                 if c+1 < n && t[c+1].when < w {
1113                         w = t[c+1].when
1114                         c++
1115                 }
1116                 if c3 < n {
1117                         w3 := t[c3].when
1118                         if c3+1 < n && t[c3+1].when < w3 {
1119                                 w3 = t[c3+1].when
1120                                 c3++
1121                         }
1122                         if w3 < w {
1123                                 w = w3
1124                                 c = c3
1125                         }
1126                 }
1127                 if w >= when {
1128                         break
1129                 }
1130                 t[i] = t[c]
1131                 i = c
1132         }
1133         if tmp != t[i] {
1134                 t[i] = tmp
1135         }
1136 }
1137
1138 // badTimer is called if the timer data structures have been corrupted,
1139 // presumably due to racy use by the program. We panic here rather than
1140 // panicking due to invalid slice access while holding locks.
1141 // See issue #25686.
1142 func badTimer() {
1143         throw("timer data corruption")
1144 }