Source file src/runtime/time.go

Documentation: runtime

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

View as plain text