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