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

View as plain text