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/sys"
    11  	"unsafe"
    12  )
    13  
    14  // Package time knows the layout of this structure.
    15  // If this struct changes, adjust ../time/sleep.go:/runtimeTimer.
    16  // For GOOS=nacl, package syscall knows the layout of this structure.
    17  // If this struct changes, adjust ../syscall/net_nacl.go:/runtimeTimer.
    18  type timer struct {
    19  	tb *timersBucket // the bucket the timer lives in
    20  	i  int           // heap index
    21  
    22  	// Timer wakes up at when, and then at when+period, ... (period > 0 only)
    23  	// each time calling f(arg, now) in the timer goroutine, so f must be
    24  	// a well-behaved function and not block.
    25  	when   int64
    26  	period int64
    27  	f      func(interface{}, uintptr)
    28  	arg    interface{}
    29  	seq    uintptr
    30  }
    31  
    32  // timersLen is the length of timers array.
    33  //
    34  // Ideally, this would be set to GOMAXPROCS, but that would require
    35  // dynamic reallocation
    36  //
    37  // The current value is a compromise between memory usage and performance
    38  // that should cover the majority of GOMAXPROCS values used in the wild.
    39  const timersLen = 64
    40  
    41  // timers contains "per-P" timer heaps.
    42  //
    43  // Timers are queued into timersBucket associated with the current P,
    44  // so each P may work with its own timers independently of other P instances.
    45  //
    46  // Each timersBucket may be associated with multiple P
    47  // if GOMAXPROCS > timersLen.
    48  var timers [timersLen]struct {
    49  	timersBucket
    50  
    51  	// The padding should eliminate false sharing
    52  	// between timersBucket values.
    53  	pad [sys.CacheLineSize - unsafe.Sizeof(timersBucket{})%sys.CacheLineSize]byte
    54  }
    55  
    56  func (t *timer) assignBucket() *timersBucket {
    57  	id := uint8(getg().m.p.ptr().id) % timersLen
    58  	t.tb = &timers[id].timersBucket
    59  	return t.tb
    60  }
    61  
    62  //go:notinheap
    63  type timersBucket struct {
    64  	lock         mutex
    65  	gp           *g
    66  	created      bool
    67  	sleeping     bool
    68  	rescheduling bool
    69  	sleepUntil   int64
    70  	waitnote     note
    71  	t            []*timer
    72  }
    73  
    74  // nacl fake time support - time in nanoseconds since 1970
    75  var faketime int64
    76  
    77  // Package time APIs.
    78  // Godoc uses the comments in package time, not these.
    79  
    80  // time.now is implemented in assembly.
    81  
    82  // timeSleep puts the current goroutine to sleep for at least ns nanoseconds.
    83  //go:linkname timeSleep time.Sleep
    84  func timeSleep(ns int64) {
    85  	if ns <= 0 {
    86  		return
    87  	}
    88  
    89  	gp := getg()
    90  	t := gp.timer
    91  	if t == nil {
    92  		t = new(timer)
    93  		gp.timer = t
    94  	}
    95  	*t = timer{}
    96  	t.when = nanotime() + ns
    97  	t.f = goroutineReady
    98  	t.arg = gp
    99  	tb := t.assignBucket()
   100  	lock(&tb.lock)
   101  	if !tb.addtimerLocked(t) {
   102  		unlock(&tb.lock)
   103  		badTimer()
   104  	}
   105  	goparkunlock(&tb.lock, waitReasonSleep, traceEvGoSleep, 2)
   106  }
   107  
   108  // startTimer adds t to the timer heap.
   109  //go:linkname startTimer time.startTimer
   110  func startTimer(t *timer) {
   111  	if raceenabled {
   112  		racerelease(unsafe.Pointer(t))
   113  	}
   114  	addtimer(t)
   115  }
   116  
   117  // stopTimer removes t from the timer heap if it is there.
   118  // It returns true if t was removed, false if t wasn't even there.
   119  //go:linkname stopTimer time.stopTimer
   120  func stopTimer(t *timer) bool {
   121  	return deltimer(t)
   122  }
   123  
   124  // Go runtime.
   125  
   126  // Ready the goroutine arg.
   127  func goroutineReady(arg interface{}, seq uintptr) {
   128  	goready(arg.(*g), 0)
   129  }
   130  
   131  func addtimer(t *timer) {
   132  	tb := t.assignBucket()
   133  	lock(&tb.lock)
   134  	ok := tb.addtimerLocked(t)
   135  	unlock(&tb.lock)
   136  	if !ok {
   137  		badTimer()
   138  	}
   139  }
   140  
   141  // Add a timer to the heap and start or kick timerproc if the new timer is
   142  // earlier than any of the others.
   143  // Timers are locked.
   144  // Returns whether all is well: false if the data structure is corrupt
   145  // due to user-level races.
   146  func (tb *timersBucket) addtimerLocked(t *timer) bool {
   147  	// when must never be negative; otherwise timerproc will overflow
   148  	// during its delta calculation and never expire other runtime timers.
   149  	if t.when < 0 {
   150  		t.when = 1<<63 - 1
   151  	}
   152  	t.i = len(tb.t)
   153  	tb.t = append(tb.t, t)
   154  	if !siftupTimer(tb.t, t.i) {
   155  		return false
   156  	}
   157  	if t.i == 0 {
   158  		// siftup moved to top: new earliest deadline.
   159  		if tb.sleeping {
   160  			tb.sleeping = false
   161  			notewakeup(&tb.waitnote)
   162  		}
   163  		if tb.rescheduling {
   164  			tb.rescheduling = false
   165  			goready(tb.gp, 0)
   166  		}
   167  	}
   168  	if !tb.created {
   169  		tb.created = true
   170  		go timerproc(tb)
   171  	}
   172  	return true
   173  }
   174  
   175  // Delete timer t from the heap.
   176  // Do not need to update the timerproc: if it wakes up early, no big deal.
   177  func deltimer(t *timer) bool {
   178  	if t.tb == nil {
   179  		// t.tb can be nil if the user created a timer
   180  		// directly, without invoking startTimer e.g
   181  		//    time.Ticker{C: c}
   182  		// In this case, return early without any deletion.
   183  		// See Issue 21874.
   184  		return false
   185  	}
   186  
   187  	tb := t.tb
   188  
   189  	lock(&tb.lock)
   190  	// t may not be registered anymore and may have
   191  	// a bogus i (typically 0, if generated by Go).
   192  	// Verify it before proceeding.
   193  	i := t.i
   194  	last := len(tb.t) - 1
   195  	if i < 0 || i > last || tb.t[i] != t {
   196  		unlock(&tb.lock)
   197  		return false
   198  	}
   199  	if i != last {
   200  		tb.t[i] = tb.t[last]
   201  		tb.t[i].i = i
   202  	}
   203  	tb.t[last] = nil
   204  	tb.t = tb.t[:last]
   205  	ok := true
   206  	if i != last {
   207  		if !siftupTimer(tb.t, i) {
   208  			ok = false
   209  		}
   210  		if !siftdownTimer(tb.t, i) {
   211  			ok = false
   212  		}
   213  	}
   214  	unlock(&tb.lock)
   215  	if !ok {
   216  		badTimer()
   217  	}
   218  	return true
   219  }
   220  
   221  // Timerproc runs the time-driven events.
   222  // It sleeps until the next event in the tb heap.
   223  // If addtimer inserts a new earlier event, it wakes timerproc early.
   224  func timerproc(tb *timersBucket) {
   225  	tb.gp = getg()
   226  	for {
   227  		lock(&tb.lock)
   228  		tb.sleeping = false
   229  		now := nanotime()
   230  		delta := int64(-1)
   231  		for {
   232  			if len(tb.t) == 0 {
   233  				delta = -1
   234  				break
   235  			}
   236  			t := tb.t[0]
   237  			delta = t.when - now
   238  			if delta > 0 {
   239  				break
   240  			}
   241  			ok := true
   242  			if t.period > 0 {
   243  				// leave in heap but adjust next time to fire
   244  				t.when += t.period * (1 + -delta/t.period)
   245  				if !siftdownTimer(tb.t, 0) {
   246  					ok = false
   247  				}
   248  			} else {
   249  				// remove from heap
   250  				last := len(tb.t) - 1
   251  				if last > 0 {
   252  					tb.t[0] = tb.t[last]
   253  					tb.t[0].i = 0
   254  				}
   255  				tb.t[last] = nil
   256  				tb.t = tb.t[:last]
   257  				if last > 0 {
   258  					if !siftdownTimer(tb.t, 0) {
   259  						ok = false
   260  					}
   261  				}
   262  				t.i = -1 // mark as removed
   263  			}
   264  			f := t.f
   265  			arg := t.arg
   266  			seq := t.seq
   267  			unlock(&tb.lock)
   268  			if !ok {
   269  				badTimer()
   270  			}
   271  			if raceenabled {
   272  				raceacquire(unsafe.Pointer(t))
   273  			}
   274  			f(arg, seq)
   275  			lock(&tb.lock)
   276  		}
   277  		if delta < 0 || faketime > 0 {
   278  			// No timers left - put goroutine to sleep.
   279  			tb.rescheduling = true
   280  			goparkunlock(&tb.lock, waitReasonTimerGoroutineIdle, traceEvGoBlock, 1)
   281  			continue
   282  		}
   283  		// At least one timer pending. Sleep until then.
   284  		tb.sleeping = true
   285  		tb.sleepUntil = now + delta
   286  		noteclear(&tb.waitnote)
   287  		unlock(&tb.lock)
   288  		notetsleepg(&tb.waitnote, delta)
   289  	}
   290  }
   291  
   292  func timejump() *g {
   293  	if faketime == 0 {
   294  		return nil
   295  	}
   296  
   297  	for i := range timers {
   298  		lock(&timers[i].lock)
   299  	}
   300  	gp := timejumpLocked()
   301  	for i := range timers {
   302  		unlock(&timers[i].lock)
   303  	}
   304  
   305  	return gp
   306  }
   307  
   308  func timejumpLocked() *g {
   309  	// Determine a timer bucket with minimum when.
   310  	var minT *timer
   311  	for i := range timers {
   312  		tb := &timers[i]
   313  		if !tb.created || len(tb.t) == 0 {
   314  			continue
   315  		}
   316  		t := tb.t[0]
   317  		if minT == nil || t.when < minT.when {
   318  			minT = t
   319  		}
   320  	}
   321  	if minT == nil || minT.when <= faketime {
   322  		return nil
   323  	}
   324  
   325  	faketime = minT.when
   326  	tb := minT.tb
   327  	if !tb.rescheduling {
   328  		return nil
   329  	}
   330  	tb.rescheduling = false
   331  	return tb.gp
   332  }
   333  
   334  func timeSleepUntil() int64 {
   335  	next := int64(1<<63 - 1)
   336  
   337  	// Determine minimum sleepUntil across all the timer buckets.
   338  	//
   339  	// The function can not return a precise answer,
   340  	// as another timer may pop in as soon as timers have been unlocked.
   341  	// So lock the timers one by one instead of all at once.
   342  	for i := range timers {
   343  		tb := &timers[i]
   344  
   345  		lock(&tb.lock)
   346  		if tb.sleeping && tb.sleepUntil < next {
   347  			next = tb.sleepUntil
   348  		}
   349  		unlock(&tb.lock)
   350  	}
   351  
   352  	return next
   353  }
   354  
   355  // Heap maintenance algorithms.
   356  // These algorithms check for slice index errors manually.
   357  // Slice index error can happen if the program is using racy
   358  // access to timers. We don't want to panic here, because
   359  // it will cause the program to crash with a mysterious
   360  // "panic holding locks" message. Instead, we panic while not
   361  // holding a lock.
   362  // The races can occur despite the bucket locks because assignBucket
   363  // itself is called without locks, so racy calls can cause a timer to
   364  // change buckets while executing these functions.
   365  
   366  func siftupTimer(t []*timer, i int) bool {
   367  	if i >= len(t) {
   368  		return false
   369  	}
   370  	when := t[i].when
   371  	tmp := t[i]
   372  	for i > 0 {
   373  		p := (i - 1) / 4 // parent
   374  		if when >= t[p].when {
   375  			break
   376  		}
   377  		t[i] = t[p]
   378  		t[i].i = i
   379  		i = p
   380  	}
   381  	if tmp != t[i] {
   382  		t[i] = tmp
   383  		t[i].i = i
   384  	}
   385  	return true
   386  }
   387  
   388  func siftdownTimer(t []*timer, i int) bool {
   389  	n := len(t)
   390  	if i >= n {
   391  		return false
   392  	}
   393  	when := t[i].when
   394  	tmp := t[i]
   395  	for {
   396  		c := i*4 + 1 // left child
   397  		c3 := c + 2  // mid child
   398  		if c >= n {
   399  			break
   400  		}
   401  		w := t[c].when
   402  		if c+1 < n && t[c+1].when < w {
   403  			w = t[c+1].when
   404  			c++
   405  		}
   406  		if c3 < n {
   407  			w3 := t[c3].when
   408  			if c3+1 < n && t[c3+1].when < w3 {
   409  				w3 = t[c3+1].when
   410  				c3++
   411  			}
   412  			if w3 < w {
   413  				w = w3
   414  				c = c3
   415  			}
   416  		}
   417  		if w >= when {
   418  			break
   419  		}
   420  		t[i] = t[c]
   421  		t[i].i = i
   422  		i = c
   423  	}
   424  	if tmp != t[i] {
   425  		t[i] = tmp
   426  		t[i].i = i
   427  	}
   428  	return true
   429  }
   430  
   431  // badTimer is called if the timer data structures have been corrupted,
   432  // presumably due to racy use by the program. We panic here rather than
   433  // panicing due to invalid slice access while holding locks.
   434  // See issue #25686.
   435  func badTimer() {
   436  	panic(errorString("racy use of timers"))
   437  }
   438  
   439  // Entry points for net, time to call nanotime.
   440  
   441  //go:linkname poll_runtimeNano internal/poll.runtimeNano
   442  func poll_runtimeNano() int64 {
   443  	return nanotime()
   444  }
   445  
   446  //go:linkname time_runtimeNano time.runtimeNano
   447  func time_runtimeNano() int64 {
   448  	return nanotime()
   449  }
   450  
   451  // Monotonic times are reported as offsets from startNano.
   452  // We initialize startNano to nanotime() - 1 so that on systems where
   453  // monotonic time resolution is fairly low (e.g. Windows 2008
   454  // which appears to have a default resolution of 15ms),
   455  // we avoid ever reporting a nanotime of 0.
   456  // (Callers may want to use 0 as "time not set".)
   457  var startNano int64 = nanotime() - 1
   458
View as plain text