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