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