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

View as plain text