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  	"internal/cpu"
    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 [cpu.CacheLinePadSize - unsafe.Sizeof(timersBucket{})%cpu.CacheLinePadSize]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 && tb.sleepUntil > t.when {
   160  			tb.sleeping = false
   161  			notewakeup(&tb.waitnote)
   162  		}
   163  		if tb.rescheduling {
   164  			tb.rescheduling = false
   165  			goready(tb.gp, 0)
   166  		}
   167  		if !tb.created {
   168  			tb.created = true
   169  			go timerproc(tb)
   170  		}
   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  	removed, ok := tb.deltimerLocked(t)
   191  	unlock(&tb.lock)
   192  	if !ok {
   193  		badTimer()
   194  	}
   195  	return removed
   196  }
   197  
   198  func (tb *timersBucket) deltimerLocked(t *timer) (removed, ok bool) {
   199  	// t may not be registered anymore and may have
   200  	// a bogus i (typically 0, if generated by Go).
   201  	// Verify it before proceeding.
   202  	i := t.i
   203  	last := len(tb.t) - 1
   204  	if i < 0 || i > last || tb.t[i] != t {
   205  		return false, true
   206  	}
   207  	if i != last {
   208  		tb.t[i] = tb.t[last]
   209  		tb.t[i].i = i
   210  	}
   211  	tb.t[last] = nil
   212  	tb.t = tb.t[:last]
   213  	ok = true
   214  	if i != last {
   215  		if !siftupTimer(tb.t, i) {
   216  			ok = false
   217  		}
   218  		if !siftdownTimer(tb.t, i) {
   219  			ok = false
   220  		}
   221  	}
   222  	return true, ok
   223  }
   224  
   225  func modtimer(t *timer, when, period int64, f func(interface{}, uintptr), arg interface{}, seq uintptr) {
   226  	tb := t.tb
   227  
   228  	lock(&tb.lock)
   229  	_, ok := tb.deltimerLocked(t)
   230  	if ok {
   231  		t.when = when
   232  		t.period = period
   233  		t.f = f
   234  		t.arg = arg
   235  		t.seq = seq
   236  		ok = tb.addtimerLocked(t)
   237  	}
   238  	unlock(&tb.lock)
   239  	if !ok {
   240  		badTimer()
   241  	}
   242  }
   243  
   244  // Timerproc runs the time-driven events.
   245  // It sleeps until the next event in the tb heap.
   246  // If addtimer inserts a new earlier event, it wakes timerproc early.
   247  func timerproc(tb *timersBucket) {
   248  	tb.gp = getg()
   249  	for {
   250  		lock(&tb.lock)
   251  		tb.sleeping = false
   252  		now := nanotime()
   253  		delta := int64(-1)
   254  		for {
   255  			if len(tb.t) == 0 {
   256  				delta = -1
   257  				break
   258  			}
   259  			t := tb.t[0]
   260  			delta = t.when - now
   261  			if delta > 0 {
   262  				break
   263  			}
   264  			ok := true
   265  			if t.period > 0 {
   266  				// leave in heap but adjust next time to fire
   267  				t.when += t.period * (1 + -delta/t.period)
   268  				if !siftdownTimer(tb.t, 0) {
   269  					ok = false
   270  				}
   271  			} else {
   272  				// remove from heap
   273  				last := len(tb.t) - 1
   274  				if last > 0 {
   275  					tb.t[0] = tb.t[last]
   276  					tb.t[0].i = 0
   277  				}
   278  				tb.t[last] = nil
   279  				tb.t = tb.t[:last]
   280  				if last > 0 {
   281  					if !siftdownTimer(tb.t, 0) {
   282  						ok = false
   283  					}
   284  				}
   285  				t.i = -1 // mark as removed
   286  			}
   287  			f := t.f
   288  			arg := t.arg
   289  			seq := t.seq
   290  			unlock(&tb.lock)
   291  			if !ok {
   292  				badTimer()
   293  			}
   294  			if raceenabled {
   295  				raceacquire(unsafe.Pointer(t))
   296  			}
   297  			f(arg, seq)
   298  			lock(&tb.lock)
   299  		}
   300  		if delta < 0 || faketime > 0 {
   301  			// No timers left - put goroutine to sleep.
   302  			tb.rescheduling = true
   303  			goparkunlock(&tb.lock, waitReasonTimerGoroutineIdle, traceEvGoBlock, 1)
   304  			continue
   305  		}
   306  		// At least one timer pending. Sleep until then.
   307  		tb.sleeping = true
   308  		tb.sleepUntil = now + delta
   309  		noteclear(&tb.waitnote)
   310  		unlock(&tb.lock)
   311  		notetsleepg(&tb.waitnote, delta)
   312  	}
   313  }
   314  
   315  func timejump() *g {
   316  	if faketime == 0 {
   317  		return nil
   318  	}
   319  
   320  	for i := range timers {
   321  		lock(&timers[i].lock)
   322  	}
   323  	gp := timejumpLocked()
   324  	for i := range timers {
   325  		unlock(&timers[i].lock)
   326  	}
   327  
   328  	return gp
   329  }
   330  
   331  func timejumpLocked() *g {
   332  	// Determine a timer bucket with minimum when.
   333  	var minT *timer
   334  	for i := range timers {
   335  		tb := &timers[i]
   336  		if !tb.created || len(tb.t) == 0 {
   337  			continue
   338  		}
   339  		t := tb.t[0]
   340  		if minT == nil || t.when < minT.when {
   341  			minT = t
   342  		}
   343  	}
   344  	if minT == nil || minT.when <= faketime {
   345  		return nil
   346  	}
   347  
   348  	faketime = minT.when
   349  	tb := minT.tb
   350  	if !tb.rescheduling {
   351  		return nil
   352  	}
   353  	tb.rescheduling = false
   354  	return tb.gp
   355  }
   356  
   357  func timeSleepUntil() int64 {
   358  	next := int64(1<<63 - 1)
   359  
   360  	// Determine minimum sleepUntil across all the timer buckets.
   361  	//
   362  	// The function can not return a precise answer,
   363  	// as another timer may pop in as soon as timers have been unlocked.
   364  	// So lock the timers one by one instead of all at once.
   365  	for i := range timers {
   366  		tb := &timers[i]
   367  
   368  		lock(&tb.lock)
   369  		if tb.sleeping && tb.sleepUntil < next {
   370  			next = tb.sleepUntil
   371  		}
   372  		unlock(&tb.lock)
   373  	}
   374  
   375  	return next
   376  }
   377  
   378  // Heap maintenance algorithms.
   379  // These algorithms check for slice index errors manually.
   380  // Slice index error can happen if the program is using racy
   381  // access to timers. We don't want to panic here, because
   382  // it will cause the program to crash with a mysterious
   383  // "panic holding locks" message. Instead, we panic while not
   384  // holding a lock.
   385  // The races can occur despite the bucket locks because assignBucket
   386  // itself is called without locks, so racy calls can cause a timer to
   387  // change buckets while executing these functions.
   388  
   389  func siftupTimer(t []*timer, i int) bool {
   390  	if i >= len(t) {
   391  		return false
   392  	}
   393  	when := t[i].when
   394  	tmp := t[i]
   395  	for i > 0 {
   396  		p := (i - 1) / 4 // parent
   397  		if when >= t[p].when {
   398  			break
   399  		}
   400  		t[i] = t[p]
   401  		t[i].i = i
   402  		i = p
   403  	}
   404  	if tmp != t[i] {
   405  		t[i] = tmp
   406  		t[i].i = i
   407  	}
   408  	return true
   409  }
   410  
   411  func siftdownTimer(t []*timer, i int) bool {
   412  	n := len(t)
   413  	if i >= n {
   414  		return false
   415  	}
   416  	when := t[i].when
   417  	tmp := t[i]
   418  	for {
   419  		c := i*4 + 1 // left child
   420  		c3 := c + 2  // mid child
   421  		if c >= n {
   422  			break
   423  		}
   424  		w := t[c].when
   425  		if c+1 < n && t[c+1].when < w {
   426  			w = t[c+1].when
   427  			c++
   428  		}
   429  		if c3 < n {
   430  			w3 := t[c3].when
   431  			if c3+1 < n && t[c3+1].when < w3 {
   432  				w3 = t[c3+1].when
   433  				c3++
   434  			}
   435  			if w3 < w {
   436  				w = w3
   437  				c = c3
   438  			}
   439  		}
   440  		if w >= when {
   441  			break
   442  		}
   443  		t[i] = t[c]
   444  		t[i].i = i
   445  		i = c
   446  	}
   447  	if tmp != t[i] {
   448  		t[i] = tmp
   449  		t[i].i = i
   450  	}
   451  	return true
   452  }
   453  
   454  // badTimer is called if the timer data structures have been corrupted,
   455  // presumably due to racy use by the program. We panic here rather than
   456  // panicing due to invalid slice access while holding locks.
   457  // See issue #25686.
   458  func badTimer() {
   459  	panic(errorString("racy use of timers"))
   460  }
   461
View as plain text