Source file src/runtime/time.go

     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