libgo/go/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 "unsafe"
  10
  11 // Package time knows the layout of this structure.
  12 // If this struct changes, adjust ../time/sleep.go:/runtimeTimer.
  13 // For GOOS=nacl, package syscall knows the layout of this structure.
  14 // If this struct changes, adjust ../syscall/net_nacl.go:/runtimeTimer.
  15 type timer struct {
  16         i int // heap index
  17
  18         // Timer wakes up at when, and then at when+period, ... (period > 0 only)
  19         // each time calling f(arg, now) in the timer goroutine, so f must be
  20         // a well-behaved function and not block.
  21         when   int64
  22         period int64
  23         f      func(interface{}, uintptr)
  24         arg    interface{}
  25         seq    uintptr
  26 }
  27
  28 var timers struct {
  29         lock         mutex
  30         gp           *g
  31         created      bool
  32         sleeping     bool
  33         rescheduling bool
  34         sleepUntil   int64
  35         waitnote     note
  36         t            []*timer
  37 }
  38
  39 // nacl fake time support - time in nanoseconds since 1970
  40 var faketime int64
  41
  42 // Package time APIs.
  43 // Godoc uses the comments in package time, not these.
  44
  45 // time.now is implemented in assembly.
  46
  47 // timeSleep puts the current goroutine to sleep for at least ns nanoseconds.
  48 //go:linkname timeSleep time.Sleep
  49 func timeSleep(ns int64) {
  50         if ns <= 0 {
  51                 return
  52         }
  53
  54         t := getg().timer
  55         if t == nil {
  56                 t = new(timer)
  57                 getg().timer = t
  58         }
  59         *t = timer{}
  60         t.when = nanotime() + ns
  61         t.f = goroutineReady
  62         t.arg = getg()
  63         lock(&timers.lock)
  64         addtimerLocked(t)
  65         goparkunlock(&timers.lock, "sleep", traceEvGoSleep, 2)
  66 }
  67
  68 // startTimer adds t to the timer heap.
  69 //go:linkname startTimer time.startTimer
  70 func startTimer(t *timer) {
  71         if raceenabled {
  72                 racerelease(unsafe.Pointer(t))
  73         }
  74         addtimer(t)
  75 }
  76
  77 // stopTimer removes t from the timer heap if it is there.
  78 // It returns true if t was removed, false if t wasn't even there.
  79 //go:linkname stopTimer time.stopTimer
  80 func stopTimer(t *timer) bool {
  81         return deltimer(t)
  82 }
  83
  84 // Go runtime.
  85
  86 // Ready the goroutine arg.
  87 func goroutineReady(arg interface{}, seq uintptr) {
  88         goready(arg.(*g), 0)
  89 }
  90
  91 func addtimer(t *timer) {
  92         lock(&timers.lock)
  93         addtimerLocked(t)
  94         unlock(&timers.lock)
  95 }
  96
  97 // Add a timer to the heap and start or kick timerproc if the new timer is
  98 // earlier than any of the others.
  99 // Timers are locked.
 100 func addtimerLocked(t *timer) {
 101         // when must never be negative; otherwise timerproc will overflow
 102         // during its delta calculation and never expire other runtime timers.
 103         if t.when < 0 {
 104                 t.when = 1<<63 - 1
 105         }
 106         t.i = len(timers.t)
 107         timers.t = append(timers.t, t)
 108         siftupTimer(t.i)
 109         if t.i == 0 {
 110                 // siftup moved to top: new earliest deadline.
 111                 if timers.sleeping {
 112                         timers.sleeping = false
 113                         notewakeup(&timers.waitnote)
 114                 }
 115                 if timers.rescheduling {
 116                         timers.rescheduling = false
 117                         goready(timers.gp, 0)
 118                 }
 119         }
 120         if !timers.created {
 121                 timers.created = true
 122                 expectSystemGoroutine()
 123                 go timerproc()
 124         }
 125 }
 126
 127 // Delete timer t from the heap.
 128 // Do not need to update the timerproc: if it wakes up early, no big deal.
 129 func deltimer(t *timer) bool {
 130         // Dereference t so that any panic happens before the lock is held.
 131         // Discard result, because t might be moving in the heap.
 132         _ = t.i
 133
 134         lock(&timers.lock)
 135         // t may not be registered anymore and may have
 136         // a bogus i (typically 0, if generated by Go).
 137         // Verify it before proceeding.
 138         i := t.i
 139         last := len(timers.t) - 1
 140         if i < 0 || i > last || timers.t[i] != t {
 141                 unlock(&timers.lock)
 142                 return false
 143         }
 144         if i != last {
 145                 timers.t[i] = timers.t[last]
 146                 timers.t[i].i = i
 147         }
 148         timers.t[last] = nil
 149         timers.t = timers.t[:last]
 150         if i != last {
 151                 siftupTimer(i)
 152                 siftdownTimer(i)
 153         }
 154         unlock(&timers.lock)
 155         return true
 156 }
 157
 158 // Timerproc runs the time-driven events.
 159 // It sleeps until the next event in the timers heap.
 160 // If addtimer inserts a new earlier event, it wakes timerproc early.
 161 func timerproc() {
 162         setSystemGoroutine()
 163
 164         timers.gp = getg()
 165         for {
 166                 lock(&timers.lock)
 167                 timers.sleeping = false
 168                 now := nanotime()
 169                 delta := int64(-1)
 170                 for {
 171                         if len(timers.t) == 0 {
 172                                 delta = -1
 173                                 break
 174                         }
 175                         t := timers.t[0]
 176                         delta = t.when - now
 177                         if delta > 0 {
 178                                 break
 179                         }
 180                         if t.period > 0 {
 181                                 // leave in heap but adjust next time to fire
 182                                 t.when += t.period * (1 + -delta/t.period)
 183                                 siftdownTimer(0)
 184                         } else {
 185                                 // remove from heap
 186                                 last := len(timers.t) - 1
 187                                 if last > 0 {
 188                                         timers.t[0] = timers.t[last]
 189                                         timers.t[0].i = 0
 190                                 }
 191                                 timers.t[last] = nil
 192                                 timers.t = timers.t[:last]
 193                                 if last > 0 {
 194                                         siftdownTimer(0)
 195                                 }
 196                                 t.i = -1 // mark as removed
 197                         }
 198                         f := t.f
 199                         arg := t.arg
 200                         seq := t.seq
 201                         unlock(&timers.lock)
 202                         if raceenabled {
 203                                 raceacquire(unsafe.Pointer(t))
 204                         }
 205                         f(arg, seq)
 206                         lock(&timers.lock)
 207                 }
 208                 if delta < 0 || faketime > 0 {
 209                         // No timers left - put goroutine to sleep.
 210                         timers.rescheduling = true
 211                         goparkunlock(&timers.lock, "timer goroutine (idle)", traceEvGoBlock, 1)
 212                         continue
 213                 }
 214                 // At least one timer pending. Sleep until then.
 215                 timers.sleeping = true
 216                 timers.sleepUntil = now + delta
 217                 noteclear(&timers.waitnote)
 218                 unlock(&timers.lock)
 219                 notetsleepg(&timers.waitnote, delta)
 220         }
 221 }
 222
 223 func timejump() *g {
 224         if faketime == 0 {
 225                 return nil
 226         }
 227
 228         lock(&timers.lock)
 229         if !timers.created || len(timers.t) == 0 {
 230                 unlock(&timers.lock)
 231                 return nil
 232         }
 233
 234         var gp *g
 235         if faketime < timers.t[0].when {
 236                 faketime = timers.t[0].when
 237                 if timers.rescheduling {
 238                         timers.rescheduling = false
 239                         gp = timers.gp
 240                 }
 241         }
 242         unlock(&timers.lock)
 243         return gp
 244 }
 245
 246 // Heap maintenance algorithms.
 247
 248 func siftupTimer(i int) {
 249         t := timers.t
 250         when := t[i].when
 251         tmp := t[i]
 252         for i > 0 {
 253                 p := (i - 1) / 4 // parent
 254                 if when >= t[p].when {
 255                         break
 256                 }
 257                 t[i] = t[p]
 258                 t[i].i = i
 259                 t[p] = tmp
 260                 t[p].i = p
 261                 i = p
 262         }
 263 }
 264
 265 func siftdownTimer(i int) {
 266         t := timers.t
 267         n := len(t)
 268         when := t[i].when
 269         tmp := t[i]
 270         for {
 271                 c := i*4 + 1 // left child
 272                 c3 := c + 2  // mid child
 273                 if c >= n {
 274                         break
 275                 }
 276                 w := t[c].when
 277                 if c+1 < n && t[c+1].when < w {
 278                         w = t[c+1].when
 279                         c++
 280                 }
 281                 if c3 < n {
 282                         w3 := t[c3].when
 283                         if c3+1 < n && t[c3+1].when < w3 {
 284                                 w3 = t[c3+1].when
 285                                 c3++
 286                         }
 287                         if w3 < w {
 288                                 w = w3
 289                                 c = c3
 290                         }
 291                 }
 292                 if w >= when {
 293                         break
 294                 }
 295                 t[i] = t[c]
 296                 t[i].i = i
 297                 t[c] = tmp
 298                 t[c].i = c
 299                 i = c
 300         }
 301 }
 302
 303 // Entry points for net, time to call nanotime.
 304
 305 //go:linkname poll_runtimeNano internal_poll.runtimeNano
 306 func poll_runtimeNano() int64 {
 307         return nanotime()
 308 }
 309
 310 //go:linkname time_runtimeNano time.runtimeNano
 311 func time_runtimeNano() int64 {
 312         return nanotime()
 313 }
 314
 315 var startNano int64 = nanotime()