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 <sys/time.h>
  10
  11 #include "runtime.h"
  12 #include "defs.h"
  13 #include "arch.h"
  14 #include "malloc.h"
  15
  16 enum {
  17         debug = 0,
  18 };
  19
  20 static Timers timers;
  21 static void addtimer(Timer*);
  22 static void dumptimers(const char*);
  23
  24 // nacl fake time support.
  25 int64 runtime_timens;
  26
  27 // Package time APIs.
  28 // Godoc uses the comments in package time, not these.
  29
  30 // time.now is implemented in assembly.
  31
  32 // runtimeNano returns the current value of the runtime clock in nanoseconds.
  33 func runtimeNano() (ns int64) {
  34         ns = runtime_nanotime();
  35 }
  36
  37 // Sleep puts the current goroutine to sleep for at least ns nanoseconds.
  38 func Sleep(ns int64) {
  39         runtime_tsleep(ns, "sleep");
  40 }
  41
  42 // startTimer adds t to the timer heap.
  43 func startTimer(t *Timer) {
  44         runtime_addtimer(t);
  45 }
  46
  47 // stopTimer removes t from the timer heap if it is there.
  48 // It returns true if t was removed, false if t wasn't even there.
  49 func stopTimer(t *Timer) (stopped bool) {
  50         stopped = runtime_deltimer(t);
  51 }
  52
  53 // C runtime.
  54
  55 int64 runtime_unixnanotime(void)
  56 {
  57         struct time_now_ret r;
  58
  59         r = now();
  60         return r.sec*1000000000 + r.nsec;
  61 }
  62
  63 static void timerproc(void*);
  64 static void siftup(int32);
  65 static void siftdown(int32);
  66
  67 // Ready the goroutine e.data.
  68 static void
  69 ready(int64 now, Eface e)
  70 {
  71         USED(now);
  72
  73         runtime_ready(e.__object);
  74 }
  75
  76 static FuncVal readyv = {(void(*)(void))ready};
  77
  78 // Put the current goroutine to sleep for ns nanoseconds.
  79 void
  80 runtime_tsleep(int64 ns, const char *reason)
  81 {
  82         G* g;
  83         Timer t;
  84
  85         g = runtime_g();
  86
  87         if(ns <= 0)
  88                 return;
  89
  90         t.when = runtime_nanotime() + ns;
  91         t.period = 0;
  92         t.fv = &readyv;
  93         t.arg.__object = g;
  94         runtime_lock(&timers);
  95         addtimer(&t);
  96         runtime_parkunlock(&timers, reason);
  97 }
  98
  99 void
 100 runtime_addtimer(Timer *t)
 101 {
 102         runtime_lock(&timers);
 103         addtimer(t);
 104         runtime_unlock(&timers);
 105 }
 106
 107 // Add a timer to the heap and start or kick the timer proc
 108 // if the new timer is earlier than any of the others.
 109 static void
 110 addtimer(Timer *t)
 111 {
 112         int32 n;
 113         Timer **nt;
 114
 115         // when must never be negative; otherwise timerproc will overflow
 116         // during its delta calculation and never expire other timers.
 117         if(t->when < 0)
 118                 t->when = (int64)((1ULL<<63)-1);
 119
 120         if(timers.len >= timers.cap) {
 121                 // Grow slice.
 122                 n = 16;
 123                 if(n <= timers.cap)
 124                         n = timers.cap*3 / 2;
 125                 nt = runtime_malloc(n*sizeof nt[0]);
 126                 runtime_memmove(nt, timers.t, timers.len*sizeof nt[0]);
 127                 runtime_free(timers.t);
 128                 timers.t = nt;
 129                 timers.cap = n;
 130         }
 131         t->i = timers.len++;
 132         timers.t[t->i] = t;
 133         siftup(t->i);
 134         if(t->i == 0) {
 135                 // siftup moved to top: new earliest deadline.
 136                 if(timers.sleeping) {
 137                         timers.sleeping = false;
 138                         runtime_notewakeup(&timers.waitnote);
 139                 }
 140                 if(timers.rescheduling) {
 141                         timers.rescheduling = false;
 142                         runtime_ready(timers.timerproc);
 143                 }
 144         }
 145         if(timers.timerproc == nil) {
 146                 timers.timerproc = __go_go(timerproc, nil);
 147                 timers.timerproc->issystem = true;
 148         }
 149         if(debug)
 150                 dumptimers("addtimer");
 151 }
 152
 153 // Used to force a dereference before the lock is acquired.
 154 static int32 gi;
 155
 156 // Delete timer t from the heap.
 157 // Do not need to update the timerproc:
 158 // if it wakes up early, no big deal.
 159 bool
 160 runtime_deltimer(Timer *t)
 161 {
 162         int32 i;
 163
 164         // Dereference t so that any panic happens before the lock is held.
 165         // Discard result, because t might be moving in the heap.
 166         i = t->i;
 167         gi = i;
 168
 169         runtime_lock(&timers);
 170
 171         // t may not be registered anymore and may have
 172         // a bogus i (typically 0, if generated by Go).
 173         // Verify it before proceeding.
 174         i = t->i;
 175         if(i < 0 || i >= timers.len || timers.t[i] != t) {
 176                 runtime_unlock(&timers);
 177                 return false;
 178         }
 179
 180         timers.len--;
 181         if(i == timers.len) {
 182                 timers.t[i] = nil;
 183         } else {
 184                 timers.t[i] = timers.t[timers.len];
 185                 timers.t[timers.len] = nil;
 186                 timers.t[i]->i = i;
 187                 siftup(i);
 188                 siftdown(i);
 189         }
 190         if(debug)
 191                 dumptimers("deltimer");
 192         runtime_unlock(&timers);
 193         return true;
 194 }
 195
 196 // Timerproc runs the time-driven events.
 197 // It sleeps until the next event in the timers heap.
 198 // If addtimer inserts a new earlier event, addtimer
 199 // wakes timerproc early.
 200 static void
 201 timerproc(void* dummy __attribute__ ((unused)))
 202 {
 203         int64 delta, now;
 204         Timer *t;
 205         FuncVal *fv;
 206         void (*f)(int64, Eface);
 207         Eface arg;
 208
 209         for(;;) {
 210                 runtime_lock(&timers);
 211                 timers.sleeping = false;
 212                 now = runtime_nanotime();
 213                 for(;;) {
 214                         if(timers.len == 0) {
 215                                 delta = -1;
 216                                 break;
 217                         }
 218                         t = timers.t[0];
 219                         delta = t->when - now;
 220                         if(delta > 0)
 221                                 break;
 222                         if(t->period > 0) {
 223                                 // leave in heap but adjust next time to fire
 224                                 t->when += t->period * (1 + -delta/t->period);
 225                                 siftdown(0);
 226                         } else {
 227                                 // remove from heap
 228                                 timers.t[0] = timers.t[--timers.len];
 229                                 timers.t[0]->i = 0;
 230                                 siftdown(0);
 231                                 t->i = -1;  // mark as removed
 232                         }
 233                         fv = t->fv;
 234                         f = (void*)t->fv->fn;
 235                         arg = t->arg;
 236                         runtime_unlock(&timers);
 237                         __go_set_closure(fv);
 238                         f(now, arg);
 239
 240                         // clear f and arg to avoid leak while sleeping for next timer
 241                         f = nil;
 242                         USED(f);
 243                         arg.__type_descriptor = nil;
 244                         arg.__object = nil;
 245                         USED(&arg);
 246
 247                         runtime_lock(&timers);
 248                 }
 249                 if(delta < 0) {
 250                         // No timers left - put goroutine to sleep.
 251                         timers.rescheduling = true;
 252                         runtime_g()->isbackground = true;
 253                         runtime_parkunlock(&timers, "timer goroutine (idle)");
 254                         runtime_g()->isbackground = false;
 255                         continue;
 256                 }
 257                 // At least one timer pending.  Sleep until then.
 258                 timers.sleeping = true;
 259                 runtime_noteclear(&timers.waitnote);
 260                 runtime_unlock(&timers);
 261                 runtime_notetsleepg(&timers.waitnote, delta);
 262         }
 263 }
 264
 265 // heap maintenance algorithms.
 266
 267 static void
 268 siftup(int32 i)
 269 {
 270         int32 p;
 271         int64 when;
 272         Timer **t, *tmp;
 273
 274         t = timers.t;
 275         when = t[i]->when;
 276         tmp = t[i];
 277         while(i > 0) {
 278                 p = (i-1)/4;  // parent
 279                 if(when >= t[p]->when)
 280                         break;
 281                 t[i] = t[p];
 282                 t[i]->i = i;
 283                 t[p] = tmp;
 284                 tmp->i = p;
 285                 i = p;
 286         }
 287 }
 288
 289 static void
 290 siftdown(int32 i)
 291 {
 292         int32 c, c3, len;
 293         int64 when, w, w3;
 294         Timer **t, *tmp;
 295
 296         t = timers.t;
 297         len = timers.len;
 298         when = t[i]->when;
 299         tmp = t[i];
 300         for(;;) {
 301                 c = i*4 + 1;  // left child
 302                 c3 = c + 2;  // mid child
 303                 if(c >= len) {
 304                         break;
 305                 }
 306                 w = t[c]->when;
 307                 if(c+1 < len && t[c+1]->when < w) {
 308                         w = t[c+1]->when;
 309                         c++;
 310                 }
 311                 if(c3 < len) {
 312                         w3 = t[c3]->when;
 313                         if(c3+1 < len && t[c3+1]->when < w3) {
 314                                 w3 = t[c3+1]->when;
 315                                 c3++;
 316                         }
 317                         if(w3 < w) {
 318                                 w = w3;
 319                                 c = c3;
 320                         }
 321                 }
 322                 if(w >= when)
 323                         break;
 324                 t[i] = t[c];
 325                 t[i]->i = i;
 326                 t[c] = tmp;
 327                 tmp->i = c;
 328                 i = c;
 329         }
 330 }
 331
 332 static void
 333 dumptimers(const char *msg)
 334 {
 335         Timer *t;
 336         int32 i;
 337
 338         runtime_printf("timers: %s\n", msg);
 339         for(i = 0; i < timers.len; i++) {
 340                 t = timers.t[i];
 341                 runtime_printf("\t%d\t%p:\ti %d when %D period %D fn %p\n",
 342                                 i, t, t->i, t->when, t->period, t->fv->fn);
 343         }
 344         runtime_printf("\n");
 345 }
 346
 347 void
 348 runtime_time_scan(struct Workbuf** wbufp, void (*enqueue1)(struct Workbuf**, Obj))
 349 {
 350         enqueue1(wbufp, (Obj){(byte*)&timers, sizeof timers, 0});
 351 }