Source file src/runtime/time.go

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

View as plain text