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

View as plain text