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