Source: time.go in package runtime

Time-related runtime and pieces of package time.


package runtime

import (
	"runtime/internal/atomic"
	"runtime/internal/sys"
	"unsafe"
)

Package time knows the layout of this structure. If this struct changes, adjust ../time/sleep.go:/runtimeTimer.

If this timer is on a heap, which P's heap it is on. puintptr rather than *p to match uintptr in the versions of this struct defined in other packages.

	pp puintptr

Timer wakes up at when, and then at when+period, ... (period > 0 only) each time calling f(arg, now) in the timer goroutine, so f must be a well-behaved function and not block. when must be positive on an active timer.

	when   int64
	period int64
	f      func(interface{}, uintptr)
	arg    interface{}
	seq    uintptr

What to set the when field to in timerModifiedXX status.

	nextwhen int64

The status field holds one of the values below.

	status uint32
}

Code outside this file has to be careful in using a timer value. The pp, status, and nextwhen fields may only be used by code in this file. Code that creates a new timer value can set the when, period, f, arg, and seq fields. A new timer value may be passed to addtimer (called by time.startTimer). After doing that no fields may be touched. An active timer (one that has been passed to addtimer) may be passed to deltimer (time.stopTimer), after which it is no longer an active timer. It is an inactive timer. In an inactive timer the period, f, arg, and seq fields may be modified, but not the when field. It's OK to just drop an inactive timer and let the GC collect it. It's not OK to pass an inactive timer to addtimer. Only newly allocated timer values may be passed to addtimer. An active timer may be passed to modtimer. No fields may be touched. It remains an active timer. An inactive timer may be passed to resettimer to turn into an active timer with an updated when field. It's OK to pass a newly allocated timer value to resettimer. Timer operations are addtimer, deltimer, modtimer, resettimer, cleantimers, adjusttimers, and runtimer. We don't permit calling addtimer/deltimer/modtimer/resettimer simultaneously, but adjusttimers and runtimer can be called at the same time as any of those. Active timers live in heaps attached to P, in the timers field. Inactive timers live there too temporarily, until they are removed. addtimer: timerNoStatus -> timerWaiting anything else -> panic: invalid value deltimer: timerWaiting -> timerModifying -> timerDeleted timerModifiedEarlier -> timerModifying -> timerDeleted timerModifiedLater -> timerModifying -> timerDeleted timerNoStatus -> do nothing timerDeleted -> do nothing timerRemoving -> do nothing timerRemoved -> do nothing timerRunning -> wait until status changes timerMoving -> wait until status changes timerModifying -> wait until status changes modtimer: timerWaiting -> timerModifying -> timerModifiedXX timerModifiedXX -> timerModifying -> timerModifiedYY timerNoStatus -> timerModifying -> timerWaiting timerRemoved -> timerModifying -> timerWaiting timerDeleted -> timerModifying -> timerModifiedXX timerRunning -> wait until status changes timerMoving -> wait until status changes timerRemoving -> wait until status changes timerModifying -> wait until status changes cleantimers (looks in P's timer heap): timerDeleted -> timerRemoving -> timerRemoved timerModifiedXX -> timerMoving -> timerWaiting adjusttimers (looks in P's timer heap): timerDeleted -> timerRemoving -> timerRemoved timerModifiedXX -> timerMoving -> timerWaiting runtimer (looks in P's timer heap): timerNoStatus -> panic: uninitialized timer timerWaiting -> timerWaiting or timerWaiting -> timerRunning -> timerNoStatus or timerWaiting -> timerRunning -> timerWaiting timerModifying -> wait until status changes timerModifiedXX -> timerMoving -> timerWaiting timerDeleted -> timerRemoving -> timerRemoved timerRunning -> panic: concurrent runtimer calls timerRemoved -> panic: inconsistent timer heap timerRemoving -> panic: inconsistent timer heap timerMoving -> panic: inconsistent timer heap

Values for the timer status field.

Timer has no status set yet.

	timerNoStatus = iota

Waiting for timer to fire. The timer is in some P's heap.

	timerWaiting

Running the timer function. A timer will only have this status briefly.

	timerRunning

The timer is deleted and should be removed. It should not be run, but it is still in some P's heap.

	timerDeleted

The timer is being removed. The timer will only have this status briefly.

	timerRemoving

The timer has been stopped. It is not in any P's heap.

	timerRemoved

The timer is being modified. The timer will only have this status briefly.

	timerModifying

The timer has been modified to an earlier time. The new when value is in the nextwhen field. The timer is in some P's heap, possibly in the wrong place.

	timerModifiedEarlier

The timer has been modified to the same or a later time. The new when value is in the nextwhen field. The timer is in some P's heap, possibly in the wrong place.

	timerModifiedLater

The timer has been modified and is being moved. The timer will only have this status briefly.

	timerMoving
)

maxWhen is the maximum value for timer's when field.

const maxWhen = 1<<63 - 1

verifyTimers can be set to true to add debugging checks that the timer heaps are valid.

const verifyTimers = false

Package time APIs. Godoc uses the comments in package time, not these.

time.now is implemented in assembly.

timeSleep puts the current goroutine to sleep for at least ns nanoseconds.go:linkname timeSleep time.Sleep

func timeSleep(ns int64) {
	if ns <= 0 {
		return
	}

	gp := getg()
	t := gp.timer
	if t == nil {
		t = new(timer)
		gp.timer = t
	}
	t.f = goroutineReady
	t.arg = gp
	t.nextwhen = nanotime() + ns
	if t.nextwhen < 0 { // check for overflow.
		t.nextwhen = maxWhen
	}
	gopark(resetForSleep, unsafe.Pointer(t), waitReasonSleep, traceEvGoSleep, 1)
}

resetForSleep is called after the goroutine is parked for timeSleep. We can't call resettimer in timeSleep itself because if this is a short sleep and there are many goroutines then the P can wind up running the timer function, goroutineReady, before the goroutine has been parked.

func resetForSleep(gp *g, ut unsafe.Pointer) bool {
	t := (*timer)(ut)
	resettimer(t, t.nextwhen)
	return true
}

startTimer adds t to the timer heap.go:linkname startTimer time.startTimer

func startTimer(t *timer) {
	if raceenabled {
		racerelease(unsafe.Pointer(t))
	}
	addtimer(t)
}

stopTimer stops a timer. It reports whether t was stopped before being run.go:linkname stopTimer time.stopTimer

func stopTimer(t *timer) bool {
	return deltimer(t)
}

resetTimer resets an inactive timer, adding it to the heap.go:linkname resetTimer time.resetTimer Reports whether the timer was modified before it was run.

func resetTimer(t *timer, when int64) bool {
	if raceenabled {
		racerelease(unsafe.Pointer(t))
	}
	return resettimer(t, when)
}

modTimer modifies an existing timer.go:linkname modTimer time.modTimer

func modTimer(t *timer, when, period int64, f func(interface{}, uintptr), arg interface{}, seq uintptr) {
	modtimer(t, when, period, f, arg, seq)
}

Go runtime.

Ready the goroutine arg.

func goroutineReady(arg interface{}, seq uintptr) {
	goready(arg.(*g), 0)
}

addtimer adds a timer to the current P. This should only be called with a newly created timer. That avoids the risk of changing the when field of a timer in some P's heap, which could cause the heap to become unsorted.

when must be positive. A negative value will cause runtimer to overflow during its delta calculation and never expire other runtime timers. Zero will cause checkTimers to fail to notice the timer.

	if t.when <= 0 {
		throw("timer when must be positive")
	}
	if t.period < 0 {
		throw("timer period must be non-negative")
	}
	if t.status != timerNoStatus {
		throw("addtimer called with initialized timer")
	}
	t.status = timerWaiting

	when := t.when

Disable preemption while using pp to avoid changing another P's heap.

	mp := acquirem()

	pp := getg().m.p.ptr()
	lock(&pp.timersLock)
	cleantimers(pp)
	doaddtimer(pp, t)
	unlock(&pp.timersLock)

	wakeNetPoller(when)

	releasem(mp)
}

doaddtimer adds t to the current P's heap. The caller must have locked the timers for pp.

Timers rely on the network poller, so make sure the poller has started.

	if netpollInited == 0 {
		netpollGenericInit()
	}

	if t.pp != 0 {
		throw("doaddtimer: P already set in timer")
	}
	t.pp.set(pp)
	i := len(pp.timers)
	pp.timers = append(pp.timers, t)
	siftupTimer(pp.timers, i)
	if t == pp.timers[0] {
		atomic.Store64(&pp.timer0When, uint64(t.when))
	}
	atomic.Xadd(&pp.numTimers, 1)
}

deltimer deletes the timer t. It may be on some other P, so we can't actually remove it from the timers heap. We can only mark it as deleted. It will be removed in due course by the P whose heap it is on. Reports whether the timer was removed before it was run.

func deltimer(t *timer) bool {
	for {
		switch s := atomic.Load(&t.status); s {

Prevent preemption while the timer is in timerModifying. This could lead to a self-deadlock. See #38070.

			mp := acquirem()

Must fetch t.pp before changing status, as cleantimers in another goroutine can clear t.pp of a timerDeleted timer.

				tpp := t.pp.ptr()
				if !atomic.Cas(&t.status, timerModifying, timerDeleted) {
					badTimer()
				}
				releasem(mp)

Timer was not yet run.

				return true
			} else {
				releasem(mp)
			}

Prevent preemption while the timer is in timerModifying. This could lead to a self-deadlock. See #38070.

			mp := acquirem()

Must fetch t.pp before setting status to timerDeleted.

				tpp := t.pp.ptr()
				atomic.Xadd(&tpp.adjustTimers, -1)
				if !atomic.Cas(&t.status, timerModifying, timerDeleted) {
					badTimer()
				}
				releasem(mp)

Timer was not yet run.

				return true
			} else {
				releasem(mp)
			}

Timer was already run.

			return false

The timer is being run or moved, by a different P. Wait for it to complete.

			osyield()

Removing timer that was never added or has already been run. Also see issue 21874.

			return false

Simultaneous calls to deltimer and modtimer. Wait for the other call to complete.

			osyield()
		default:
			badTimer()
		}
	}
}

dodeltimer removes timer i from the current P's heap. We are locked on the P when this is called. It reports whether it saw no problems due to races. The caller must have locked the timers for pp.

func dodeltimer(pp *p, i int) {
	if t := pp.timers[i]; t.pp.ptr() != pp {
		throw("dodeltimer: wrong P")
	} else {
		t.pp = 0
	}
	last := len(pp.timers) - 1
	if i != last {
		pp.timers[i] = pp.timers[last]
	}
	pp.timers[last] = nil
	pp.timers = pp.timers[:last]

Moving to i may have moved the last timer to a new parent, so sift up to preserve the heap guarantee.

		siftupTimer(pp.timers, i)
		siftdownTimer(pp.timers, i)
	}
	if i == 0 {
		updateTimer0When(pp)
	}
	atomic.Xadd(&pp.numTimers, -1)
}

dodeltimer0 removes timer 0 from the current P's heap. We are locked on the P when this is called. It reports whether it saw no problems due to races. The caller must have locked the timers for pp.

func dodeltimer0(pp *p) {
	if t := pp.timers[0]; t.pp.ptr() != pp {
		throw("dodeltimer0: wrong P")
	} else {
		t.pp = 0
	}
	last := len(pp.timers) - 1
	if last > 0 {
		pp.timers[0] = pp.timers[last]
	}
	pp.timers[last] = nil
	pp.timers = pp.timers[:last]
	if last > 0 {
		siftdownTimer(pp.timers, 0)
	}
	updateTimer0When(pp)
	atomic.Xadd(&pp.numTimers, -1)
}

modtimer modifies an existing timer. This is called by the netpoll code or time.Ticker.Reset or time.Timer.Reset. Reports whether the timer was modified before it was run.

func modtimer(t *timer, when, period int64, f func(interface{}, uintptr), arg interface{}, seq uintptr) bool {
	if when <= 0 {
		throw("timer when must be positive")
	}
	if period < 0 {
		throw("timer period must be non-negative")
	}

	status := uint32(timerNoStatus)
	wasRemoved := false
	var pending bool
	var mp *m
loop:
	for {
		switch status = atomic.Load(&t.status); status {

Prevent preemption while the timer is in timerModifying. This could lead to a self-deadlock. See #38070.

			mp = acquirem()
			if atomic.Cas(&t.status, status, timerModifying) {
				pending = true // timer not yet run
				break loop
			}
			releasem(mp)

Prevent preemption while the timer is in timerModifying. This could lead to a self-deadlock. See #38070.

			mp = acquirem()

Timer was already run and t is no longer in a heap. Act like addtimer.

			if atomic.Cas(&t.status, status, timerModifying) {
				wasRemoved = true
				pending = false // timer already run or stopped
				break loop
			}
			releasem(mp)

Prevent preemption while the timer is in timerModifying. This could lead to a self-deadlock. See #38070.

			mp = acquirem()
			if atomic.Cas(&t.status, status, timerModifying) {
				atomic.Xadd(&t.pp.ptr().deletedTimers, -1)
				pending = false // timer already stopped
				break loop
			}
			releasem(mp)

The timer is being run or moved, by a different P. Wait for it to complete.

			osyield()

Multiple simultaneous calls to modtimer. Wait for the other call to complete.

			osyield()
		default:
			badTimer()
		}
	}

	t.period = period
	t.f = f
	t.arg = arg
	t.seq = seq

	if wasRemoved {
		t.when = when
		pp := getg().m.p.ptr()
		lock(&pp.timersLock)
		doaddtimer(pp, t)
		unlock(&pp.timersLock)
		if !atomic.Cas(&t.status, timerModifying, timerWaiting) {
			badTimer()
		}
		releasem(mp)
		wakeNetPoller(when)

The timer is in some other P's heap, so we can't change the when field. If we did, the other P's heap would be out of order. So we put the new when value in the nextwhen field, and let the other P set the when field when it is prepared to resort the heap.

		t.nextwhen = when

		newStatus := uint32(timerModifiedLater)
		if when < t.when {
			newStatus = timerModifiedEarlier
		}

		tpp := t.pp.ptr()

Update the adjustTimers field. Subtract one if we are removing a timerModifiedEarlier, add one if we are adding a timerModifiedEarlier.

		adjust := int32(0)
		if status == timerModifiedEarlier {
			adjust--
		}
		if newStatus == timerModifiedEarlier {
			adjust++
			updateTimerModifiedEarliest(tpp, when)
		}
		if adjust != 0 {
			atomic.Xadd(&tpp.adjustTimers, adjust)
		}

Set the new status of the timer.

		if !atomic.Cas(&t.status, timerModifying, newStatus) {
			badTimer()
		}
		releasem(mp)

If the new status is earlier, wake up the poller.

		if newStatus == timerModifiedEarlier {
			wakeNetPoller(when)
		}
	}

	return pending
}

resettimer resets the time when a timer should fire. If used for an inactive timer, the timer will become active. This should be called instead of addtimer if the timer value has been, or may have been, used previously. Reports whether the timer was modified before it was run.

func resettimer(t *timer, when int64) bool {
	return modtimer(t, when, t.period, t.f, t.arg, t.seq)
}

cleantimers cleans up the head of the timer queue. This speeds up programs that create and delete timers; leaving them in the heap slows down addtimer. Reports whether no timer problems were found. The caller must have locked the timers for pp.

func cleantimers(pp *p) {
	gp := getg()
	for {
		if len(pp.timers) == 0 {
			return
		}

This loop can theoretically run for a while, and because it is holding timersLock it cannot be preempted. If someone is trying to preempt us, just return. We can clean the timers later.

		if gp.preemptStop {
			return
		}

		t := pp.timers[0]
		if t.pp.ptr() != pp {
			throw("cleantimers: bad p")
		}
		switch s := atomic.Load(&t.status); s {
		case timerDeleted:
			if !atomic.Cas(&t.status, s, timerRemoving) {
				continue
			}
			dodeltimer0(pp)
			if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
				badTimer()
			}
			atomic.Xadd(&pp.deletedTimers, -1)
		case timerModifiedEarlier, timerModifiedLater:
			if !atomic.Cas(&t.status, s, timerMoving) {
				continue

Now we can change the when field.

Move t to the right position.

			dodeltimer0(pp)
			doaddtimer(pp, t)
			if s == timerModifiedEarlier {
				atomic.Xadd(&pp.adjustTimers, -1)
			}
			if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
				badTimer()
			}

Head of timers does not need adjustment.

			return
		}
	}
}

moveTimers moves a slice of timers to pp. The slice has been taken from a different P. This is currently called when the world is stopped, but the caller is expected to have locked the timers for pp.

func moveTimers(pp *p, timers []*timer) {
	for _, t := range timers {
	loop:
		for {
			switch s := atomic.Load(&t.status); s {
			case timerWaiting:
				if !atomic.Cas(&t.status, s, timerMoving) {
					continue
				}
				t.pp = 0
				doaddtimer(pp, t)
				if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
					badTimer()
				}
				break loop
			case timerModifiedEarlier, timerModifiedLater:
				if !atomic.Cas(&t.status, s, timerMoving) {
					continue
				}
				t.when = t.nextwhen
				t.pp = 0
				doaddtimer(pp, t)
				if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
					badTimer()
				}
				break loop
			case timerDeleted:
				if !atomic.Cas(&t.status, s, timerRemoved) {
					continue
				}

We no longer need this timer in the heap.

				break loop

Loop until the modification is complete.

				osyield()

We should not see these status values in a timers heap.

				badTimer()

Some other P thinks it owns this timer, which should not happen.

				badTimer()
			default:
				badTimer()
			}
		}
	}
}

adjusttimers looks through the timers in the current P's heap for any timers that have been modified to run earlier, and puts them in the correct place in the heap. While looking for those timers, it also moves timers that have been modified to run later, and removes deleted timers. The caller must have locked the timers for pp.

func adjusttimers(pp *p, now int64) {
	if atomic.Load(&pp.adjustTimers) == 0 {
		if verifyTimers {
			verifyTimerHeap(pp)

There are no timers to adjust, so it is safe to clear timerModifiedEarliest. Do so in case it is stale. Everything will work if we don't do this, but clearing here may save future calls to adjusttimers.

		atomic.Store64(&pp.timerModifiedEarliest, 0)
		return
	}

If we haven't yet reached the time of the first timerModifiedEarlier timer, don't do anything. This speeds up programs that adjust a lot of timers back and forth if the timers rarely expire. We'll postpone looking through all the adjusted timers until one would actually expire.

	if first := atomic.Load64(&pp.timerModifiedEarliest); first != 0 {
		if int64(first) > now {
			if verifyTimers {
				verifyTimerHeap(pp)
			}
			return
		}

We are going to clear all timerModifiedEarlier timers.

		atomic.Store64(&pp.timerModifiedEarliest, 0)
	}

	var moved []*timer
loop:
	for i := 0; i < len(pp.timers); i++ {
		t := pp.timers[i]
		if t.pp.ptr() != pp {
			throw("adjusttimers: bad p")
		}
		switch s := atomic.Load(&t.status); s {
		case timerDeleted:
			if atomic.Cas(&t.status, s, timerRemoving) {
				dodeltimer(pp, i)
				if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
					badTimer()
				}

Look at this heap position again.

				i--
			}
		case timerModifiedEarlier, timerModifiedLater:

Now we can change the when field.

Take t off the heap, and hold onto it. We don't add it back yet because the heap manipulation could cause our loop to skip some other timer.

				dodeltimer(pp, i)
				moved = append(moved, t)
				if s == timerModifiedEarlier {
					if n := atomic.Xadd(&pp.adjustTimers, -1); int32(n) <= 0 {
						break loop
					}

Look at this heap position again.

				i--
			}
		case timerNoStatus, timerRunning, timerRemoving, timerRemoved, timerMoving:
			badTimer()

OK, nothing to do.

Check again after modification is complete.

			osyield()
			i--
		default:
			badTimer()
		}
	}

	if len(moved) > 0 {
		addAdjustedTimers(pp, moved)
	}

	if verifyTimers {
		verifyTimerHeap(pp)
	}
}

addAdjustedTimers adds any timers we adjusted in adjusttimers back to the timer heap.

func addAdjustedTimers(pp *p, moved []*timer) {
	for _, t := range moved {
		doaddtimer(pp, t)
		if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
			badTimer()
		}
	}
}

nobarrierWakeTime looks at P's timers and returns the time when we should wake up the netpoller. It returns 0 if there are no timers. This function is invoked when dropping a P, and must run without any write barriers.go:nowritebarrierrec

func nobarrierWakeTime(pp *p) int64 {
	next := int64(atomic.Load64(&pp.timer0When))
	nextAdj := int64(atomic.Load64(&pp.timerModifiedEarliest))
	if next == 0 || (nextAdj != 0 && nextAdj < next) {
		next = nextAdj
	}
	return next
}

runtimer examines the first timer in timers. If it is ready based on now, it runs the timer and removes or updates it. Returns 0 if it ran a timer, -1 if there are no more timers, or the time when the first timer should run. The caller must have locked the timers for pp. If a timer is run, this will temporarily unlock the timers.go:systemstack

func runtimer(pp *p, now int64) int64 {
	for {
		t := pp.timers[0]
		if t.pp.ptr() != pp {
			throw("runtimer: bad p")
		}
		switch s := atomic.Load(&t.status); s {
		case timerWaiting:

Not ready to run.

				return t.when
			}

			if !atomic.Cas(&t.status, s, timerRunning) {
				continue

Note that runOneTimer may temporarily unlock pp.timersLock.

			runOneTimer(pp, t, now)
			return 0

		case timerDeleted:
			if !atomic.Cas(&t.status, s, timerRemoving) {
				continue
			}
			dodeltimer0(pp)
			if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
				badTimer()
			}
			atomic.Xadd(&pp.deletedTimers, -1)
			if len(pp.timers) == 0 {
				return -1
			}

		case timerModifiedEarlier, timerModifiedLater:
			if !atomic.Cas(&t.status, s, timerMoving) {
				continue
			}
			t.when = t.nextwhen
			dodeltimer0(pp)
			doaddtimer(pp, t)
			if s == timerModifiedEarlier {
				atomic.Xadd(&pp.adjustTimers, -1)
			}
			if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
				badTimer()
			}

Wait for modification to complete.

			osyield()

Should not see a new or inactive timer on the heap.

			badTimer()

These should only be set when timers are locked, and we didn't do it.

			badTimer()
		default:
			badTimer()
		}
	}
}

runOneTimer runs a single timer. The caller must have locked the timers for pp. This will temporarily unlock the timers while running the timer function.go:systemstack

func runOneTimer(pp *p, t *timer, now int64) {
	if raceenabled {
		ppcur := getg().m.p.ptr()
		if ppcur.timerRaceCtx == 0 {
			ppcur.timerRaceCtx = racegostart(funcPC(runtimer) + sys.PCQuantum)
		}
		raceacquirectx(ppcur.timerRaceCtx, unsafe.Pointer(t))
	}

	f := t.f
	arg := t.arg
	seq := t.seq

Leave in heap but adjust next time to fire.

		delta := t.when - now
		t.when += t.period * (1 + -delta/t.period)
		if t.when < 0 { // check for overflow.
			t.when = maxWhen
		}
		siftdownTimer(pp.timers, 0)
		if !atomic.Cas(&t.status, timerRunning, timerWaiting) {
			badTimer()
		}
		updateTimer0When(pp)

Remove from heap.

		dodeltimer0(pp)
		if !atomic.Cas(&t.status, timerRunning, timerNoStatus) {
			badTimer()
		}
	}

Temporarily use the current P's racectx for g0.

		gp := getg()
		if gp.racectx != 0 {
			throw("runOneTimer: unexpected racectx")
		}
		gp.racectx = gp.m.p.ptr().timerRaceCtx
	}

	unlock(&pp.timersLock)

	f(arg, seq)

	lock(&pp.timersLock)

	if raceenabled {
		gp := getg()
		gp.racectx = 0
	}
}

clearDeletedTimers removes all deleted timers from the P's timer heap. This is used to avoid clogging up the heap if the program starts a lot of long-running timers and then stops them. For example, this can happen via context.WithTimeout. This is the only function that walks through the entire timer heap, other than moveTimers which only runs when the world is stopped. The caller must have locked the timers for pp.

We are going to clear all timerModifiedEarlier timers. Do this now in case new ones show up while we are looping.

	atomic.Store64(&pp.timerModifiedEarliest, 0)

	cdel := int32(0)
	cearlier := int32(0)
	to := 0
	changedHeap := false
	timers := pp.timers
nextTimer:
	for _, t := range timers {
		for {
			switch s := atomic.Load(&t.status); s {
			case timerWaiting:
				if changedHeap {
					timers[to] = t
					siftupTimer(timers, to)
				}
				to++
				continue nextTimer
			case timerModifiedEarlier, timerModifiedLater:
				if atomic.Cas(&t.status, s, timerMoving) {
					t.when = t.nextwhen
					timers[to] = t
					siftupTimer(timers, to)
					to++
					changedHeap = true
					if !atomic.Cas(&t.status, timerMoving, timerWaiting) {
						badTimer()
					}
					if s == timerModifiedEarlier {
						cearlier++
					}
					continue nextTimer
				}
			case timerDeleted:
				if atomic.Cas(&t.status, s, timerRemoving) {
					t.pp = 0
					cdel++
					if !atomic.Cas(&t.status, timerRemoving, timerRemoved) {
						badTimer()
					}
					changedHeap = true
					continue nextTimer
				}

Loop until modification complete.

				osyield()

We should not see these status values in a timer heap.

				badTimer()

Some other P thinks it owns this timer, which should not happen.

				badTimer()
			default:
				badTimer()
			}
		}
	}

Set remaining slots in timers slice to nil, so that the timer values can be garbage collected.

	for i := to; i < len(timers); i++ {
		timers[i] = nil
	}

	atomic.Xadd(&pp.deletedTimers, -cdel)
	atomic.Xadd(&pp.numTimers, -cdel)
	atomic.Xadd(&pp.adjustTimers, -cearlier)

	timers = timers[:to]
	pp.timers = timers
	updateTimer0When(pp)

	if verifyTimers {
		verifyTimerHeap(pp)
	}
}

verifyTimerHeap verifies that the timer heap is in a valid state. This is only for debugging, and is only called if verifyTimers is true. The caller must have locked the timers.

func verifyTimerHeap(pp *p) {
	for i, t := range pp.timers {

First timer has no parent.

			continue
		}

The heap is 4-ary. See siftupTimer and siftdownTimer.

		p := (i - 1) / 4
		if t.when < pp.timers[p].when {
			print("bad timer heap at ", i, ": ", p, ": ", pp.timers[p].when, ", ", i, ": ", t.when, "\n")
			throw("bad timer heap")
		}
	}
	if numTimers := int(atomic.Load(&pp.numTimers)); len(pp.timers) != numTimers {
		println("timer heap len", len(pp.timers), "!= numTimers", numTimers)
		throw("bad timer heap len")
	}
}

updateTimer0When sets the P's timer0When field. The caller must have locked the timers for pp.

func updateTimer0When(pp *p) {
	if len(pp.timers) == 0 {
		atomic.Store64(&pp.timer0When, 0)
	} else {
		atomic.Store64(&pp.timer0When, uint64(pp.timers[0].when))
	}
}

updateTimerModifiedEarliest updates the recorded nextwhen field of the earlier timerModifiedEarier value. The timers for pp will not be locked.

func updateTimerModifiedEarliest(pp *p, nextwhen int64) {
	for {
		old := atomic.Load64(&pp.timerModifiedEarliest)
		if old != 0 && int64(old) < nextwhen {
			return
		}
		if atomic.Cas64(&pp.timerModifiedEarliest, old, uint64(nextwhen)) {
			return
		}
	}
}

timeSleepUntil returns the time when the next timer should fire, and the P that holds the timer heap that that timer is on. This is only called by sysmon and checkdead.

func timeSleepUntil() (int64, *p) {
	next := int64(maxWhen)
	var pret *p

Prevent allp slice changes. This is like retake.

	lock(&allpLock)
	for _, pp := range allp {

This can happen if procresize has grown allp but not yet created new Ps.

			continue
		}

		w := int64(atomic.Load64(&pp.timer0When))
		if w != 0 && w < next {
			next = w
			pret = pp
		}

		w = int64(atomic.Load64(&pp.timerModifiedEarliest))
		if w != 0 && w < next {
			next = w
			pret = pp
		}
	}
	unlock(&allpLock)

	return next, pret
}

Heap maintenance algorithms. These algorithms check for slice index errors manually. Slice index error can happen if the program is using racy access to timers. We don't want to panic here, because it will cause the program to crash with a mysterious "panic holding locks" message. Instead, we panic while not holding a lock.


func siftupTimer(t []*timer, i int) {
	if i >= len(t) {
		badTimer()
	}
	when := t[i].when
	if when <= 0 {
		badTimer()
	}
	tmp := t[i]
	for i > 0 {
		p := (i - 1) / 4 // parent
		if when >= t[p].when {
			break
		}
		t[i] = t[p]
		i = p
	}
	if tmp != t[i] {
		t[i] = tmp
	}
}

func siftdownTimer(t []*timer, i int) {
	n := len(t)
	if i >= n {
		badTimer()
	}
	when := t[i].when
	if when <= 0 {
		badTimer()
	}
	tmp := t[i]
	for {
		c := i*4 + 1 // left child
		c3 := c + 2  // mid child
		if c >= n {
			break
		}
		w := t[c].when
		if c+1 < n && t[c+1].when < w {
			w = t[c+1].when
			c++
		}
		if c3 < n {
			w3 := t[c3].when
			if c3+1 < n && t[c3+1].when < w3 {
				w3 = t[c3+1].when
				c3++
			}
			if w3 < w {
				w = w3
				c = c3
			}
		}
		if w >= when {
			break
		}
		t[i] = t[c]
		i = c
	}
	if tmp != t[i] {
		t[i] = tmp
	}
}

badTimer is called if the timer data structures have been corrupted, presumably due to racy use by the program. We panic here rather than panicing due to invalid slice access while holding locks. See issue #25686.

func badTimer() {
	throw("timer data corruption")