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 (
  10         "runtime/internal/sys"
  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 [sys.CacheLineSize - unsafe.Sizeof(timersBucket{})%sys.CacheLineSize]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 type timersBucket struct {
  63         lock         mutex
  64         gp           *g
  65         created      bool
  66         sleeping     bool
  67         rescheduling bool
  68         sleepUntil   int64
  69         waitnote     note
  70         t            []*timer
  71 }
  72
  73 // nacl fake time support - time in nanoseconds since 1970
  74 var faketime int64
  75
  76 // Package time APIs.
  77 // Godoc uses the comments in package time, not these.
  78
  79 // time.now is implemented in assembly.
  80
  81 // timeSleep puts the current goroutine to sleep for at least ns nanoseconds.
  82 //go:linkname timeSleep time.Sleep
  83 func timeSleep(ns int64) {
  84         if ns <= 0 {
  85                 return
  86         }
  87
  88         gp := getg()
  89         t := gp.timer
  90         if t == nil {
  91                 t = new(timer)
  92                 gp.timer = t
  93         }
  94         *t = timer{}
  95         t.when = nanotime() + ns
  96         t.f = goroutineReady
  97         t.arg = gp
  98         tb := t.assignBucket()
  99         lock(&tb.lock)
 100         tb.addtimerLocked(t)
 101         goparkunlock(&tb.lock, "sleep", traceEvGoSleep, 2)
 102 }
 103
 104 // startTimer adds t to the timer heap.
 105 //go:linkname startTimer time.startTimer
 106 func startTimer(t *timer) {
 107         if raceenabled {
 108                 racerelease(unsafe.Pointer(t))
 109         }
 110         addtimer(t)
 111 }
 112
 113 // stopTimer removes t from the timer heap if it is there.
 114 // It returns true if t was removed, false if t wasn't even there.
 115 //go:linkname stopTimer time.stopTimer
 116 func stopTimer(t *timer) bool {
 117         return deltimer(t)
 118 }
 119
 120 // Go runtime.
 121
 122 // Ready the goroutine arg.
 123 func goroutineReady(arg interface{}, seq uintptr) {
 124         goready(arg.(*g), 0)
 125 }
 126
 127 func addtimer(t *timer) {
 128         tb := t.assignBucket()
 129         lock(&tb.lock)
 130         tb.addtimerLocked(t)
 131         unlock(&tb.lock)
 132 }
 133
 134 // Add a timer to the heap and start or kick timerproc if the new timer is
 135 // earlier than any of the others.
 136 // Timers are locked.
 137 func (tb *timersBucket) addtimerLocked(t *timer) {
 138         // when must never be negative; otherwise timerproc will overflow
 139         // during its delta calculation and never expire other runtime timers.
 140         if t.when < 0 {
 141                 t.when = 1<<63 - 1
 142         }
 143         t.i = len(tb.t)
 144         tb.t = append(tb.t, t)
 145         siftupTimer(tb.t, t.i)
 146         if t.i == 0 {
 147                 // siftup moved to top: new earliest deadline.
 148                 if tb.sleeping {
 149                         tb.sleeping = false
 150                         notewakeup(&tb.waitnote)
 151                 }
 152                 if tb.rescheduling {
 153                         tb.rescheduling = false
 154                         goready(tb.gp, 0)
 155                 }
 156         }
 157         if !tb.created {
 158                 tb.created = true
 159                 expectSystemGoroutine()
 160                 go timerproc(tb)
 161         }
 162 }
 163
 164 // Delete timer t from the heap.
 165 // Do not need to update the timerproc: if it wakes up early, no big deal.
 166 func deltimer(t *timer) bool {
 167         if t.tb == nil {
 168                 // t.tb can be nil if the user created a timer
 169                 // directly, without invoking startTimer e.g
 170                 //    time.Ticker{C: c}
 171                 // In this case, return early without any deletion.
 172                 // See Issue 21874.
 173                 return false
 174         }
 175
 176         tb := t.tb
 177
 178         lock(&tb.lock)
 179         // t may not be registered anymore and may have
 180         // a bogus i (typically 0, if generated by Go).
 181         // Verify it before proceeding.
 182         i := t.i
 183         last := len(tb.t) - 1
 184         if i < 0 || i > last || tb.t[i] != t {
 185                 unlock(&tb.lock)
 186                 return false
 187         }
 188         if i != last {
 189                 tb.t[i] = tb.t[last]
 190                 tb.t[i].i = i
 191         }
 192         tb.t[last] = nil
 193         tb.t = tb.t[:last]
 194         if i != last {
 195                 siftupTimer(tb.t, i)
 196                 siftdownTimer(tb.t, i)
 197         }
 198         unlock(&tb.lock)
 199         return true
 200 }
 201
 202 // Timerproc runs the time-driven events.
 203 // It sleeps until the next event in the tb heap.
 204 // If addtimer inserts a new earlier event, it wakes timerproc early.
 205 func timerproc(tb *timersBucket) {
 206         setSystemGoroutine()
 207
 208         tb.gp = getg()
 209         for {
 210                 lock(&tb.lock)
 211                 tb.sleeping = false
 212                 now := nanotime()
 213                 delta := int64(-1)
 214                 for {
 215                         if len(tb.t) == 0 {
 216                                 delta = -1
 217                                 break
 218                         }
 219                         t := tb.t[0]
 220                         delta = t.when - now
 221                         if delta > 0 {
 222                                 break
 223                         }
 224                         if t.period > 0 {
 225                                 // leave in heap but adjust next time to fire
 226                                 t.when += t.period * (1 + -delta/t.period)
 227                                 siftdownTimer(tb.t, 0)
 228                         } else {
 229                                 // remove from heap
 230                                 last := len(tb.t) - 1
 231                                 if last > 0 {
 232                                         tb.t[0] = tb.t[last]
 233                                         tb.t[0].i = 0
 234                                 }
 235                                 tb.t[last] = nil
 236                                 tb.t = tb.t[:last]
 237                                 if last > 0 {
 238                                         siftdownTimer(tb.t, 0)
 239                                 }
 240                                 t.i = -1 // mark as removed
 241                         }
 242                         f := t.f
 243                         arg := t.arg
 244                         seq := t.seq
 245                         unlock(&tb.lock)
 246                         if raceenabled {
 247                                 raceacquire(unsafe.Pointer(t))
 248                         }
 249                         f(arg, seq)
 250                         lock(&tb.lock)
 251                 }
 252                 if delta < 0 || faketime > 0 {
 253                         // No timers left - put goroutine to sleep.
 254                         tb.rescheduling = true
 255                         goparkunlock(&tb.lock, "timer goroutine (idle)", traceEvGoBlock, 1)
 256                         continue
 257                 }
 258                 // At least one timer pending. Sleep until then.
 259                 tb.sleeping = true
 260                 tb.sleepUntil = now + delta
 261                 noteclear(&tb.waitnote)
 262                 unlock(&tb.lock)
 263                 notetsleepg(&tb.waitnote, delta)
 264         }
 265 }
 266
 267 func timejump() *g {
 268         if faketime == 0 {
 269                 return nil
 270         }
 271
 272         for i := range timers {
 273                 lock(&timers[i].lock)
 274         }
 275         gp := timejumpLocked()
 276         for i := range timers {
 277                 unlock(&timers[i].lock)
 278         }
 279
 280         return gp
 281 }
 282
 283 func timejumpLocked() *g {
 284         // Determine a timer bucket with minimum when.
 285         var minT *timer
 286         for i := range timers {
 287                 tb := &timers[i]
 288                 if !tb.created || len(tb.t) == 0 {
 289                         continue
 290                 }
 291                 t := tb.t[0]
 292                 if minT == nil || t.when < minT.when {
 293                         minT = t
 294                 }
 295         }
 296         if minT == nil || minT.when <= faketime {
 297                 return nil
 298         }
 299
 300         faketime = minT.when
 301         tb := minT.tb
 302         if !tb.rescheduling {
 303                 return nil
 304         }
 305         tb.rescheduling = false
 306         return tb.gp
 307 }
 308
 309 func timeSleepUntil() int64 {
 310         next := int64(1<<63 - 1)
 311
 312         // Determine minimum sleepUntil across all the timer buckets.
 313         //
 314         // The function can not return a precise answer,
 315         // as another timer may pop in as soon as timers have been unlocked.
 316         // So lock the timers one by one instead of all at once.
 317         for i := range timers {
 318                 tb := &timers[i]
 319
 320                 lock(&tb.lock)
 321                 if tb.sleeping && tb.sleepUntil < next {
 322                         next = tb.sleepUntil
 323                 }
 324                 unlock(&tb.lock)
 325         }
 326
 327         return next
 328 }
 329
 330 // Heap maintenance algorithms.
 331
 332 func siftupTimer(t []*timer, i int) {
 333         when := t[i].when
 334         tmp := t[i]
 335         for i > 0 {
 336                 p := (i - 1) / 4 // parent
 337                 if when >= t[p].when {
 338                         break
 339                 }
 340                 t[i] = t[p]
 341                 t[i].i = i
 342                 i = p
 343         }
 344         if tmp != t[i] {
 345                 t[i] = tmp
 346                 t[i].i = i
 347         }
 348 }
 349
 350 func siftdownTimer(t []*timer, i int) {
 351         n := len(t)
 352         when := t[i].when
 353         tmp := t[i]
 354         for {
 355                 c := i*4 + 1 // left child
 356                 c3 := c + 2  // mid child
 357                 if c >= n {
 358                         break
 359                 }
 360                 w := t[c].when
 361                 if c+1 < n && t[c+1].when < w {
 362                         w = t[c+1].when
 363                         c++
 364                 }
 365                 if c3 < n {
 366                         w3 := t[c3].when
 367                         if c3+1 < n && t[c3+1].when < w3 {
 368                                 w3 = t[c3+1].when
 369                                 c3++
 370                         }
 371                         if w3 < w {
 372                                 w = w3
 373                                 c = c3
 374                         }
 375                 }
 376                 if w >= when {
 377                         break
 378                 }
 379                 t[i] = t[c]
 380                 t[i].i = i
 381                 i = c
 382         }
 383         if tmp != t[i] {
 384                 t[i] = tmp
 385                 t[i].i = i
 386         }
 387 }
 388
 389 // Entry points for net, time to call nanotime.
 390
 391 //go:linkname poll_runtimeNano internal_poll.runtimeNano
 392 func poll_runtimeNano() int64 {
 393         return nanotime()
 394 }
 395
 396 //go:linkname time_runtimeNano time.runtimeNano
 397 func time_runtimeNano() int64 {
 398         return nanotime()
 399 }
 400
 401 // Monotonic times are reported as offsets from startNano.
 402 // We initialize startNano to nanotime() - 1 so that on systems where
 403 // monotonic time resolution is fairly low (e.g. Windows 2008
 404 // which appears to have a default resolution of 15ms),
 405 // we avoid ever reporting a nanotime of 0.
 406 // (Callers may want to use 0 as "time not set".)
 407 var startNano int64 = nanotime() - 1