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

View as plain text