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