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