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