libgo/runtime/time.goc

   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 time
   8
   9 #include "runtime.h"
  10 #include "defs.h"
  11 #include "arch.h"
  12 #include "malloc.h"
  13
  14 static Timers timers;
  15 static void addtimer(Timer*);
  16 static bool deltimer(Timer*);
  17
  18 // Package time APIs.
  19 // Godoc uses the comments in package time, not these.
  20
  21 // time.now is implemented in assembly.
  22
  23 // Sleep puts the current goroutine to sleep for at least ns nanoseconds.
  24 func Sleep(ns int64) {
  25         G *g;
  26
  27         g = runtime_g();
  28         g->status = Gwaiting;
  29         g->waitreason = "sleep";
  30         runtime_tsleep(ns);
  31 }
  32
  33 // startTimer adds t to the timer heap.
  34 func startTimer(t *Timer) {
  35         addtimer(t);
  36 }
  37
  38 // stopTimer removes t from the timer heap if it is there.
  39 // It returns true if t was removed, false if t wasn't even there.
  40 func stopTimer(t *Timer) (stopped bool) {
  41         stopped = deltimer(t);
  42 }
  43
  44 // C runtime.
  45
  46 static void timerproc(void*);
  47 static void siftup(int32);
  48 static void siftdown(int32);
  49
  50 // Ready the goroutine e.data.
  51 static void
  52 ready(int64 now, Eface e)
  53 {
  54         USED(now);
  55
  56         runtime_ready(e.__object);
  57 }
  58
  59 // Put the current goroutine to sleep for ns nanoseconds.
  60 // The caller must have set g->status and g->waitreason.
  61 void
  62 runtime_tsleep(int64 ns)
  63 {
  64         G* g;
  65         Timer t;
  66
  67         g = runtime_g();
  68
  69         if(ns <= 0) {
  70                 g->status = Grunning;
  71                 g->waitreason = nil;
  72                 return;
  73         }
  74
  75         t.when = runtime_nanotime() + ns;
  76         t.period = 0;
  77         t.f = ready;
  78         t.arg.__object = g;
  79         addtimer(&t);
  80         runtime_gosched();
  81 }
  82
  83 // Add a timer to the heap and start or kick the timer proc
  84 // if the new timer is earlier than any of the others.
  85 static void
  86 addtimer(Timer *t)
  87 {
  88         int32 n;
  89         Timer **nt;
  90
  91         runtime_lock(&timers);
  92         if(timers.len >= timers.cap) {
  93                 // Grow slice.
  94                 n = 16;
  95                 if(n <= timers.cap)
  96                         n = timers.cap*3 / 2;
  97                 nt = runtime_malloc(n*sizeof nt[0]);
  98                 runtime_memmove(nt, timers.t, timers.len*sizeof nt[0]);
  99                 runtime_free(timers.t);
 100                 timers.t = nt;
 101                 timers.cap = n;
 102         }
 103         t->i = timers.len++;
 104         timers.t[t->i] = t;
 105         siftup(t->i);
 106         if(t->i == 0) {
 107                 // siftup moved to top: new earliest deadline.
 108                 if(timers.sleeping) {
 109                         timers.sleeping = false;
 110                         runtime_notewakeup(&timers.waitnote);
 111                 }
 112                 if(timers.rescheduling) {
 113                         timers.rescheduling = false;
 114                         runtime_ready(timers.timerproc);
 115                 }
 116         }
 117         if(timers.timerproc == nil)
 118                 timers.timerproc = __go_go(timerproc, nil);
 119         runtime_unlock(&timers);
 120 }
 121
 122 // Delete timer t from the heap.
 123 // Do not need to update the timerproc:
 124 // if it wakes up early, no big deal.
 125 static bool
 126 deltimer(Timer *t)
 127 {
 128         int32 i;
 129
 130         runtime_lock(&timers);
 131
 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         if(i < 0 || i >= timers.len || timers.t[i] != t) {
 137                 runtime_unlock(&timers);
 138                 return false;
 139         }
 140
 141         timers.len--;
 142         if(i == timers.len) {
 143                 timers.t[i] = nil;
 144         } else {
 145                 timers.t[i] = timers.t[timers.len];
 146                 timers.t[timers.len] = nil;
 147                 timers.t[i]->i = i;
 148                 siftup(i);
 149                 siftdown(i);
 150         }
 151         runtime_unlock(&timers);
 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, addtimer
 158 // wakes timerproc early.
 159 static void
 160 timerproc(void* dummy __attribute__ ((unused)))
 161 {
 162         G *g;
 163         int64 delta, now;
 164         Timer *t;
 165         void (*f)(int64, Eface);
 166         Eface arg;
 167
 168         g = runtime_g();
 169         for(;;) {
 170                 runtime_lock(&timers);
 171                 now = runtime_nanotime();
 172                 for(;;) {
 173                         if(timers.len == 0) {
 174                                 delta = -1;
 175                                 break;
 176                         }
 177                         t = timers.t[0];
 178                         delta = t->when - now;
 179                         if(delta > 0)
 180                                 break;
 181                         if(t->period > 0) {
 182                                 // leave in heap but adjust next time to fire
 183                                 t->when += t->period * (1 + -delta/t->period);
 184                                 siftdown(0);
 185                         } else {
 186                                 // remove from heap
 187                                 timers.t[0] = timers.t[--timers.len];
 188                                 timers.t[0]->i = 0;
 189                                 siftdown(0);
 190                                 t->i = -1;  // mark as removed
 191                         }
 192                         f = t->f;
 193                         arg = t->arg;
 194                         runtime_unlock(&timers);
 195                         f(now, arg);
 196                         runtime_lock(&timers);
 197                 }
 198                 if(delta < 0) {
 199                         // No timers left - put goroutine to sleep.
 200                         timers.rescheduling = true;
 201                         g->status = Gwaiting;
 202                         g->waitreason = "timer goroutine (idle)";
 203                         runtime_unlock(&timers);
 204                         runtime_gosched();
 205                         continue;
 206                 }
 207                 // At least one timer pending.  Sleep until then.
 208                 timers.sleeping = true;
 209                 runtime_noteclear(&timers.waitnote);
 210                 runtime_unlock(&timers);
 211                 runtime_entersyscall();
 212                 runtime_notetsleep(&timers.waitnote, delta);
 213                 runtime_exitsyscall();
 214         }
 215 }
 216
 217 // heap maintenance algorithms.
 218
 219 static void
 220 siftup(int32 i)
 221 {
 222         int32 p;
 223         Timer **t, *tmp;
 224
 225         t = timers.t;
 226         while(i > 0) {
 227                 p = (i-1)/2;  // parent
 228                 if(t[i]->when >= t[p]->when)
 229                         break;
 230                 tmp = t[i];
 231                 t[i] = t[p];
 232                 t[p] = tmp;
 233                 t[i]->i = i;
 234                 t[p]->i = p;
 235                 i = p;
 236         }
 237 }
 238
 239 static void
 240 siftdown(int32 i)
 241 {
 242         int32 c, len;
 243         Timer **t, *tmp;
 244
 245         t = timers.t;
 246         len = timers.len;
 247         for(;;) {
 248                 c = i*2 + 1;  // left child
 249                 if(c >= len) {
 250                         break;
 251                 }
 252                 if(c+1 < len && t[c+1]->when < t[c]->when)
 253                         c++;
 254                 if(t[c]->when >= t[i]->when)
 255                         break;
 256                 tmp = t[i];
 257                 t[i] = t[c];
 258                 t[c] = tmp;
 259                 t[i]->i = i;
 260                 t[c]->i = c;
 261                 i = c;
 262         }
 263 }
 264
 265 void
 266 runtime_time_scan(void (*scan)(byte*, int64))
 267 {
 268         scan((byte*)&timers, sizeof timers);
 269 }