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