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 7package time 8 9#include "runtime.h" 10#include "defs.h" 11#include "arch.h" 12#include "malloc.h" 13#include "race.h" 14 15enum { 16 debug = 0, 17}; 18 19static Timers timers; 20static void addtimer(Timer*); 21static 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. 29func Sleep(ns int64) { 30 runtime_tsleep(ns, "sleep"); 31} 32 33// startTimer adds t to the timer heap. 34func 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. 42func stopTimer(t *Timer) (stopped bool) { 43 stopped = runtime_deltimer(t); 44} 45 46// C runtime. 47 48static void timerproc(void*); 49static void siftup(int32); 50static void siftdown(int32); 51 52// Ready the goroutine e.data. 53static void 54ready(int64 now, Eface e) 55{ 56 USED(now); 57 58 runtime_ready(e.__object); 59} 60 61static FuncVal readyv = {(void(*)(void))ready}; 62 63// Put the current goroutine to sleep for ns nanoseconds. 64void 65runtime_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 84void 85runtime_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. 94static void 95addtimer(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. 139static 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. 144bool 145runtime_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. 185static void 186timerproc(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 242static void 243siftup(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 264static void 265siftdown(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 307static void 308dumptimers(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 322void 323runtime_time_scan(void (*addroot)(Obj)) 324{ 325 addroot((Obj){(byte*)&timers, sizeof timers, 0}); 326} 327