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

View as plain text