// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Time-related runtime and pieces of package time.

package runtime

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

// A timer is a potentially repeating trigger for calling t.f(t.arg, t.seq).
// Timers are allocated by client code, often as part of other data structures.
// Each P has a heap of pointers to timers that it manages.
//
// A timer is expected to be used by only one client goroutine at a time,
// but there will be concurrent access by the P managing that timer.
// The fundamental state about the timer is managed in the atomic state field,
// including a lock bit to manage access to the other fields.
// The lock bit supports a manual cas-based spin lock that handles
// contention by yielding the OS thread. The expectation is that critical
// sections are very short and contention on the lock bit is low.
//
// Package time knows the layout of this structure.
// If this struct changes, adjust ../time/sleep.go:/runtimeTimer.
type timer struct {
	// 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.
	// Timers in heaps are ordered by when.
	when   int64
	period int64
	f      func(any, uintptr)
	arg    any
	seq    uintptr

	// nextWhen is the next value for when,
	// set if state&timerNextWhen is true.
	// In that case, the actual update of when = nextWhen
	// must be delayed until the heap can be fixed at the same time.
	nextWhen int64

	// The state field holds state bits, defined below.
	state atomic.Uint32
}

// Timer state field.
// Note that state 0 must be "unlocked, not in heap" and usable,
// at least for time.Timer.Stop. See go.dev/issue/21874.
const (
	// timerLocked is set when the timer is locked,
	// meaning other goroutines cannot read or write mutable fields.
	// Goroutines can still read the state word atomically to see
	// what the state was before it was locked.
	// The lock is implemented as a cas on the state field with osyield on contention;
	// the expectation is very short critical sections with little to no contention.
	timerLocked = 1 << iota

	// timerHeaped is set when the timer is stored in some P's heap.
	timerHeaped

	// timerNextWhen is set when a pending change to the timer's when
	// field has been stored in t.nextwhen. The change to t.when waits
	// until the heap in which the timer appears can also be updated.
	// Only set when timerHeaped is also set.
	timerNextWhen
)

// lock locks the timer, allowing reading or writing any of the timer fields.
// It returns the current m and the status prior to the lock.
// The caller must call unlock with the same m and an updated status.
func (t *timer) lock() (state uint32, mp *m) {
	acquireLockRank(lockRankTimer)
	for {
		state := t.state.Load()
		if state&timerLocked != 0 {
			osyield()
			continue
		}
		// Prevent preemption while the timer is locked.
		// This could lead to a self-deadlock. See #38070.
		mp := acquirem()
		if t.state.CompareAndSwap(state, state|timerLocked) {
			return state, mp
		}
		releasem(mp)
	}
}

// unlock unlocks the timer.
// If mp == nil, the caller is responsible for calling
// releasem(mp) with the mp returned by t.lock.
func (t *timer) unlock(state uint32, mp *m) {
	releaseLockRank(lockRankTimer)
	if t.state.Load()&timerLocked == 0 {
		badTimer()
	}
	if state&timerLocked != 0 {
		badTimer()
	}
	t.state.Store(state)
	if mp != nil {
		releasem(mp)
	}
}

// updateWhen updates t.when as directed by state, returning the new state
// and a bool indicating whether the state (and t.when) changed.
// If pp != nil, then the caller must have locked pp.timers,
// t must be pp.timers[0], and updateWhen takes care of
// moving t within the pp.timers heap when t.when is changed.
func (t *timer) updateWhen(state uint32, pp *p) (newState uint32, updated bool) {
	if state&timerNextWhen == 0 {
		return state, false
	}
	state &^= timerNextWhen
	if t.nextWhen == 0 {
		if pp != nil {
			if t != pp.timers[0] {
				badTimer()
			}
			pp.deletedTimers.Add(-1)
			dodeltimer0(pp)
		}
		state &^= timerHeaped
	} else {
		// Now we can change the when field.
		t.when = t.nextWhen
		// Move t to the right position.
		if pp != nil {
			if t != pp.timers[0] {
				badTimer()
			}
			siftdownTimer(pp.timers, 0)
			updateTimer0When(pp)
		}
	}
	return state, true
}

// 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, traceBlockSleep, 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)
	t.reset(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))
	}
	if t.state.Load() != 0 {
		throw("startTimer called with initialized timer")
	}
	t.reset(t.when)
}

// stopTimer stops a timer.
// It reports whether t was stopped before being run.
//
//go:linkname stopTimer time.stopTimer
func stopTimer(t *timer) bool {
	return t.stop()
}

// resetTimer resets an inactive timer, adding it to the heap.
//
// Reports whether the timer was modified before it was run.
//
//go:linkname resetTimer time.resetTimer
func resetTimer(t *timer, when int64) bool {
	if raceenabled {
		racerelease(unsafe.Pointer(t))
	}
	return t.reset(when)
}

// modTimer modifies an existing timer.
//
//go:linkname modTimer time.modTimer
func modTimer(t *timer, when, period int64) {
	t.modify(when, period, t.f, t.arg, t.seq)
}

// Go runtime.

// Ready the goroutine arg.
func goroutineReady(arg any, seq uintptr) {
	goready(arg.(*g), 0)
}

// doaddtimer adds t to the current P's heap.
// The caller must have set t.pp = pp, unlocked t,
// and then locked the timers for pp.
func doaddtimer(pp *p, t *timer) {
	// Timers rely on the network poller, so make sure the poller
	// has started.
	if netpollInited.Load() == 0 {
		netpollGenericInit()
	}

	if t.pp.ptr() != pp {
		throw("doaddtimer: P not set in timer")
	}
	i := len(pp.timers)
	pp.timers = append(pp.timers, t)
	siftupTimer(pp.timers, i)
	if t == pp.timers[0] {
		pp.timer0When.Store(t.when)
	}
	pp.numTimers.Add(1)
}

// stop 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 stopped.
// It will be removed in due course by the P whose heap it is on.
// Reports whether the timer was stopped before it was run.
func (t *timer) stop() bool {
	state, mp := t.lock()
	if state&timerHeaped != 0 && (state&timerNextWhen == 0 || t.nextWhen != 0) {
		// Timer pending: stop it.
		t.pp.ptr().deletedTimers.Add(1)
		t.nextWhen = 0
		state |= timerNextWhen
		t.unlock(state, mp)
		return true
	}

	// Timer already run or deleted.
	t.unlock(state, mp)
	return false
}

// 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)
	n := pp.numTimers.Add(-1)
	if n == 0 {
		// If there are no timers, then clearly none are modified.
		pp.timerModifiedEarliest.Store(0)
	}
}

// modify 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 (t *timer) modify(when, period int64, f func(any, uintptr), arg any, seq uintptr) bool {
	if when <= 0 {
		throw("timer when must be positive")
	}
	if period < 0 {
		throw("timer period must be non-negative")
	}

	state, mp := t.lock()
	t.period = period
	t.f = f
	t.arg = arg
	t.seq = seq

	if state&timerHeaped == 0 {
		// Set up t for insertion but unlock first,
		// to avoid lock inversion with timers lock.
		// Since t is not in a heap yet, nothing will
		// find and modify it until after the doaddtimer.
		state |= timerHeaped
		t.when = when

		pp := getg().m.p.ptr()
		t.pp.set(pp)
		// pass mp=nil to t.unlock to avoid preemption
		// between t.unlock and lock of timersLock.
		// releasem done manually below
		t.unlock(state, nil)

		lock(&pp.timersLock)
		doaddtimer(pp, t)
		unlock(&pp.timersLock)
		releasem(mp)
		wakeNetPoller(when)
		return false
	}

	pending := state&timerNextWhen == 0 || t.nextWhen != 0 // timerHeaped is set (checked above)
	if !pending {
		t.pp.ptr().deletedTimers.Add(-1)
	}

	// 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
	state |= timerNextWhen
	earlier := when < t.when
	if earlier {
		updateTimerModifiedEarliest(t.pp.ptr(), when)
	}

	t.unlock(state, mp)

	// If the new status is earlier, wake up the poller.
	if earlier {
		wakeNetPoller(when)
	}

	return pending
}

// reset resets the time when a timer should fire.
// If used for an inactive timer, the timer will become active.
// Reports whether the timer was active and was stopped.
func (t *timer) reset(when int64) bool {
	return t.modify(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 heap operations.
// 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")
		}

		if t.state.Load()&timerNextWhen == 0 {
			// Fast path: head of timers does not need adjustment.
			return
		}

		state, mp := t.lock()
		state, updated := t.updateWhen(state, pp)
		t.unlock(state, mp)
		if !updated {
			// Head of timers does not need adjustment.
			t.unlock(state, mp)
			return
		}
	}
}

// adoptTimers adopts any timers from pp into the local P,
// because pp is being destroyed.
func adoptTimers(pp *p) {
	if len(pp.timers) > 0 {
		plocal := getg().m.p.ptr()
		// The world is stopped, but we acquire timersLock to
		// protect against sysmon calling timeSleepUntil.
		// This is the only case where we hold the timersLock of
		// more than one P, so there are no deadlock concerns.
		lock(&plocal.timersLock)
		lock(&pp.timersLock)
		moveTimers(plocal, pp.timers)
		pp.timers = nil
		pp.numTimers.Store(0)
		pp.deletedTimers.Store(0)
		pp.timer0When.Store(0)
		unlock(&pp.timersLock)
		unlock(&plocal.timersLock)
	}
}

// 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 {
		state, mp := t.lock()
		t.pp = 0
		state, _ = t.updateWhen(state, nil)
		// Unlock before add, to avoid append (allocation)
		// while holding lock. This would be correct even if the world wasn't
		// stopped (but it is), and it makes staticlockranking happy.
		if state&timerHeaped != 0 {
				t.pp.set(pp)
		}
		t.unlock(state, mp)
		if state&timerHeaped != 0 {
			doaddtimer(pp, t)
		}
	}
}

// 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, force bool) {
	// If we haven't yet reached the time of the earliest timerModified
	// 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 !force {
		first := pp.timerModifiedEarliest.Load()
		if first == 0 || first > now {
			if verifyTimers {
				verifyTimerHeap(pp)
			}
			return
		}
	}

	// We are going to clear all timerModified timers.
	pp.timerModifiedEarliest.Store(0)

	changed := false
	for i := 0; i < len(pp.timers); i++ {
		t := pp.timers[i]
		if t.pp.ptr() != pp {
			throw("adjusttimers: bad p")
		}

		state, mp := t.lock()
		if state&timerHeaped == 0 {
			badTimer()
		}
		state, updated := t.updateWhen(state, nil)
		if updated {
			changed = true
			if state&timerHeaped == 0 {
				n := len(pp.timers)
				pp.timers[i] = pp.timers[n-1]
				pp.timers[n-1] = nil
				pp.timers = pp.timers[:n-1]
				t.pp = 0
				pp.deletedTimers.Add(-1)
				i--
			}
		}
		t.unlock(state, mp)
	}

	if changed {
		initTimerHeap(pp.timers)
		updateTimer0When(pp)
	}

	if verifyTimers {
		verifyTimerHeap(pp)
	}
}

// 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 := pp.timer0When.Load()
	nextAdj := pp.timerModifiedEarliest.Load()
	if next == 0 || (nextAdj != 0 && nextAdj < next) {
		next = nextAdj
	}
	return next
}

// checkTimers runs any timers for the P that are ready.
// If now is not 0 it is the current time.
// It returns the passed time or the current time if now was passed as 0.
// and the time when the next timer should run or 0 if there is no next timer,
// and reports whether it ran any timers.
// If the time when the next timer should run is not 0,
// it is always larger than the returned time.
// We pass now in and out to avoid extra calls of nanotime.
//
//go:yeswritebarrierrec
func checkTimers(pp *p, now int64) (rnow, pollUntil int64, ran bool) {
	// If it's not yet time for the first timer, or the first adjusted
	// timer, then there is nothing to do.
	next := pp.timer0When.Load()
	nextAdj := pp.timerModifiedEarliest.Load()
	if next == 0 || (nextAdj != 0 && nextAdj < next) {
		next = nextAdj
	}

	if next == 0 {
		// No timers to run or adjust.
		return now, 0, false
	}

	if now == 0 {
		now = nanotime()
	}
	if now < next {
		// Next timer is not ready to run, but keep going
		// if we would clear deleted timers.
		// This corresponds to the condition below where
		// we decide whether to call clearDeletedTimers.
		if pp != getg().m.p.ptr() || int(pp.deletedTimers.Load()) <= int(pp.numTimers.Load()/4) {
			return now, next, false
		}
	}

	lock(&pp.timersLock)

	if len(pp.timers) > 0 {
		// If this is the local P, and there are a lot of deleted timers,
		// clear them out. We only do this for the local P to reduce
		// lock contention on timersLock.
		force := pp == getg().m.p.ptr() && int(pp.deletedTimers.Load()) > len(pp.timers)/4
		adjusttimers(pp, now, force)
		for len(pp.timers) > 0 {
			// Note that runtimer may temporarily unlock
			// pp.timersLock.
			if tw := runtimer(pp, now); tw != 0 {
				if tw > 0 {
					pollUntil = tw
				}
				break
			}
			ran = true
		}
	}

	unlock(&pp.timersLock)

	return now, pollUntil, ran
}

// 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 {
Redo:
	if len(pp.timers) == 0 {
		return -1
	}
	t := pp.timers[0]
	if t.pp.ptr() != pp {
		throw("runtimer: bad p")
	}

	if t.state.Load()&timerNextWhen == 0 && t.when > now {
		// Fast path: not ready to run.
		// The access of t.when is protected by the caller holding
		// pp.timersLock, even though t itself is unlocked.
		return t.when
	}

	state, mp := t.lock()
	state, updated := t.updateWhen(state, pp)
	if updated {
		t.unlock(state, mp)
		goto Redo
	}

	if state&timerHeaped == 0 {
		badTimer()
	}

	if t.when > now {
		// Not ready to run.
		t.unlock(state, mp)
		return t.when
	}

	unlockAndRunTimer(pp, t, now, state, mp)
	return 0
}

// unlockAndRunTimer unlocks and 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 unlockAndRunTimer(pp *p, t *timer, now int64, state uint32, mp *m) {
	if raceenabled {
		ppcur := getg().m.p.ptr()
		if ppcur.timerRaceCtx == 0 {
			ppcur.timerRaceCtx = racegostart(abi.FuncPCABIInternal(runtimer) + sys.PCQuantum)
		}
		raceacquirectx(ppcur.timerRaceCtx, unsafe.Pointer(t))
	}

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

	if t.period > 0 {
		// Leave in heap but adjust next time to fire.
		delta := t.when - now
		t.nextWhen = t.when + t.period*(1+-delta/t.period)
		if t.nextWhen < 0 { // check for overflow.
			t.nextWhen = maxWhen
		}
	} else {
		t.nextWhen = 0
	}
	state, _ = t.updateWhen(state|timerNextWhen, pp)
	t.unlock(state, mp)

	if raceenabled {
		// 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
	}
}

// updateTimerPMask clears pp's timer mask if it has no timers on its heap.
//
// Ideally, the timer mask would be kept immediately consistent on any timer
// operations. Unfortunately, updating a shared global data structure in the
// timer hot path adds too much overhead in applications frequently switching
// between no timers and some timers.
//
// As a compromise, the timer mask is updated only on pidleget / pidleput. A
// running P (returned by pidleget) may add a timer at any time, so its mask
// must be set. An idle P (passed to pidleput) cannot add new timers while
// idle, so if it has no timers at that time, its mask may be cleared.
//
// Thus, we get the following effects on timer-stealing in findrunnable:
//
//   - Idle Ps with no timers when they go idle are never checked in findrunnable
//     (for work- or timer-stealing; this is the ideal case).
//   - Running Ps must always be checked.
//   - Idle Ps whose timers are stolen must continue to be checked until they run
//     again, even after timer expiration.
//
// When the P starts running again, the mask should be set, as a timer may be
// added at any time.
//
// TODO(prattmic): Additional targeted updates may improve the above cases.
// e.g., updating the mask when stealing a timer.
func updateTimerPMask(pp *p) {
	if pp.numTimers.Load() > 0 {
		return
	}

	// Looks like there are no timers, however another P may transiently
	// decrement numTimers when handling a timerModified timer in
	// checkTimers. We must take timersLock to serialize with these changes.
	lock(&pp.timersLock)
	if pp.numTimers.Load() == 0 {
		timerpMask.clear(pp.id)
	}
	unlock(&pp.timersLock)
}

// 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 {
		if i == 0 {
			// 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(pp.numTimers.Load()); 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 {
		pp.timer0When.Store(0)
	} else {
		pp.timer0When.Store(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 := pp.timerModifiedEarliest.Load()
		if old != 0 && old < nextwhen {
			return
		}

		if pp.timerModifiedEarliest.CompareAndSwap(old, nextwhen) {
			return
		}
	}
}

// timeSleepUntil returns the time when the next timer should fire. Returns
// maxWhen if there are no timers.
// This is only called by sysmon and checkdead.
func timeSleepUntil() int64 {
	next := int64(maxWhen)

	// Prevent allp slice changes. This is like retake.
	lock(&allpLock)
	for _, pp := range allp {
		if pp == nil {
			// This can happen if procresize has grown
			// allp but not yet created new Ps.
			continue
		}

		w := pp.timer0When.Load()
		if w != 0 && w < next {
			next = w
		}

		w = pp.timerModifiedEarliest.Load()
		if w != 0 && w < next {
			next = w
		}
	}
	unlock(&allpLock)

	return next
}

// 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.

// siftupTimer puts the timer at position i in the right place
// in the heap by moving it up toward the top of the heap.
// It returns the smallest changed index.
func siftupTimer(t []*timer, i int) 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
	}
	return i
}

// siftdownTimer puts the timer at position i in the right place
// in the heap by moving it down toward the bottom of the heap.
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
	}
}

// initTimerHeap reestablishes the heap order in the slice t.
// It takes O(n) time for n=len(t), not the O(n log n) of n repeated add operations.
func initTimerHeap(t []*timer) {
	// Last possible element that needs sifting down is parent of last element;
	// last element is len(t)-1; parent of last element is (len(t)-1-1)/4.
	if len(t) <= 1 {
		return
	}
	for i := (len(t) - 1 - 1) / 4; i >= 0; i-- {
		siftdownTimer(t, i)
	}
}

// badTimer is called if the timer data structures have been corrupted,
// presumably due to racy use by the program. We panic here rather than
// panicking due to invalid slice access while holding locks.
// See issue #25686.
func badTimer() {
	throw("timer data corruption")
}