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