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