Removed strayed code fragment
[strongswan.git] / src / charon / processing / scheduler.c
1 /*
2 * Copyright (C) 2008 Tobias Brunner
3 * Copyright (C) 2005-2006 Martin Willi
4 * Copyright (C) 2005 Jan Hutter
5 * Hochschule fuer Technik Rapperswil
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2 of the License, or (at your
10 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * for more details.
16 */
17
18 #include <stdlib.h>
19
20 #include "scheduler.h"
21
22 #include <daemon.h>
23 #include <processing/processor.h>
24 #include <processing/jobs/callback_job.h>
25 #include <threading/thread.h>
26 #include <threading/condvar.h>
27 #include <threading/mutex.h>
28
29 /* the initial size of the heap */
30 #define HEAP_SIZE_DEFAULT 64
31
32 typedef struct event_t event_t;
33
34 /**
35 * Event containing a job and a schedule time
36 */
37 struct event_t {
38 /**
39 * Time to fire the event.
40 */
41 timeval_t time;
42
43 /**
44 * Every event has its assigned job.
45 */
46 job_t *job;
47 };
48
49 /**
50 * destroy an event and its job
51 */
52 static void event_destroy(event_t *event)
53 {
54 event->job->destroy(event->job);
55 free(event);
56 }
57
58 typedef struct private_scheduler_t private_scheduler_t;
59
60 /**
61 * Private data of a scheduler_t object.
62 */
63 struct private_scheduler_t {
64
65 /**
66 * Public part of a scheduler_t object.
67 */
68 scheduler_t public;
69
70 /**
71 * Job which queues scheduled jobs to the processor.
72 */
73 callback_job_t *job;
74
75 /**
76 * The heap in which the events are stored.
77 */
78 event_t **heap;
79
80 /**
81 * The size of the heap.
82 */
83 u_int heap_size;
84
85 /**
86 * The number of scheduled events.
87 */
88 u_int event_count;
89
90 /**
91 * Exclusive access to list
92 */
93 mutex_t *mutex;
94
95 /**
96 * Condvar to wait for next job.
97 */
98 condvar_t *condvar;
99 };
100
101 /**
102 * Comparse two timevals, return >0 if a > b, <0 if a < b and =0 if equal
103 */
104 static int timeval_cmp(timeval_t *a, timeval_t *b)
105 {
106 if (a->tv_sec > b->tv_sec)
107 {
108 return 1;
109 }
110 if (a->tv_sec < b->tv_sec)
111 {
112 return -1;
113 }
114 if (a->tv_usec > b->tv_usec)
115 {
116 return 1;
117 }
118 if (a->tv_usec < b->tv_usec)
119 {
120 return -1;
121 }
122 return 0;
123 }
124
125 /**
126 * Returns the top event without removing it. Returns NULL if the heap is empty.
127 */
128 static event_t *peek_event(private_scheduler_t *this)
129 {
130 return this->event_count > 0 ? this->heap[1] : NULL;
131 }
132
133 /**
134 * Removes the top event from the heap and returns it. Returns NULL if the heap
135 * is empty.
136 */
137 static event_t *remove_event(private_scheduler_t *this)
138 {
139 event_t *event, *top;
140 if (!this->event_count)
141 {
142 return NULL;
143 }
144
145 /* store the value to return */
146 event = this->heap[1];
147 /* move the bottom event to the top */
148 top = this->heap[1] = this->heap[this->event_count];
149
150 if (--this->event_count > 1)
151 {
152 /* seep down the top event */
153 u_int position = 1;
154 while ((position << 1) <= this->event_count)
155 {
156 u_int child = position << 1;
157
158 if ((child + 1) <= this->event_count &&
159 timeval_cmp(&this->heap[child + 1]->time,
160 &this->heap[child]->time) < 0)
161 {
162 /* the "right" child is smaller */
163 child++;
164 }
165
166 if (timeval_cmp(&top->time, &this->heap[child]->time) <= 0)
167 {
168 /* the top event fires before the smaller of the two children,
169 * stop */
170 break;
171 }
172
173 /* swap with the smaller child */
174 this->heap[position] = this->heap[child];
175 position = child;
176 }
177 this->heap[position] = top;
178 }
179 return event;
180 }
181
182 /**
183 * Get events from the queue and pass it to the processor
184 */
185 static job_requeue_t schedule(private_scheduler_t * this)
186 {
187 timeval_t now;
188 event_t *event;
189 bool timed = FALSE, oldstate;
190
191 this->mutex->lock(this->mutex);
192
193 time_monotonic(&now);
194
195 if ((event = peek_event(this)) != NULL)
196 {
197 if (timeval_cmp(&now, &event->time) >= 0)
198 {
199 remove_event(this);
200 this->mutex->unlock(this->mutex);
201 DBG2(DBG_JOB, "got event, queuing job for execution");
202 charon->processor->queue_job(charon->processor, event->job);
203 free(event);
204 return JOB_REQUEUE_DIRECT;
205 }
206 timersub(&event->time, &now, &now);
207 if (now.tv_sec)
208 {
209 DBG2(DBG_JOB, "next event in %ds %dms, waiting",
210 now.tv_sec, now.tv_usec/1000);
211 }
212 else
213 {
214 DBG2(DBG_JOB, "next event in %dms, waiting", now.tv_usec/1000);
215 }
216 timed = TRUE;
217 }
218 thread_cleanup_push((thread_cleanup_t)this->mutex->unlock, this->mutex);
219 oldstate = thread_cancelability(TRUE);
220
221 if (timed)
222 {
223 this->condvar->timed_wait_abs(this->condvar, this->mutex, event->time);
224 }
225 else
226 {
227 DBG2(DBG_JOB, "no events, waiting");
228 this->condvar->wait(this->condvar, this->mutex);
229 }
230 thread_cancelability(oldstate);
231 thread_cleanup_pop(TRUE);
232 return JOB_REQUEUE_DIRECT;
233 }
234
235 /**
236 * Implements scheduler_t.get_job_load
237 */
238 static u_int get_job_load(private_scheduler_t *this)
239 {
240 int count;
241 this->mutex->lock(this->mutex);
242 count = this->event_count;
243 this->mutex->unlock(this->mutex);
244 return count;
245 }
246
247 /**
248 * Implements scheduler_t.schedule_job_tv.
249 */
250 static void schedule_job_tv(private_scheduler_t *this, job_t *job, timeval_t tv)
251 {
252 event_t *event;
253 u_int position;
254
255 event = malloc_thing(event_t);
256 event->job = job;
257 event->time = tv;
258
259 this->mutex->lock(this->mutex);
260
261 this->event_count++;
262 if (this->event_count > this->heap_size)
263 {
264 /* double the size of the heap */
265 this->heap_size <<= 1;
266 this->heap = (event_t**)realloc(this->heap,
267 (this->heap_size + 1) * sizeof(event_t*));
268 }
269 /* "put" the event to the bottom */
270 position = this->event_count;
271
272 /* then bubble it up */
273 while (position > 1 && timeval_cmp(&this->heap[position >> 1]->time,
274 &event->time) > 0)
275 {
276 /* parent has to be fired after the new event, move up */
277 this->heap[position] = this->heap[position >> 1];
278 position >>= 1;
279 }
280 this->heap[position] = event;
281
282 this->condvar->signal(this->condvar);
283 this->mutex->unlock(this->mutex);
284 }
285
286 /**
287 * Implements scheduler_t.schedule_job.
288 */
289 static void schedule_job(private_scheduler_t *this, job_t *job, u_int32_t s)
290 {
291 timeval_t tv;
292
293 time_monotonic(&tv);
294 tv.tv_sec += s;
295
296 schedule_job_tv(this, job, tv);
297 }
298
299 /**
300 * Implements scheduler_t.schedule_job_ms.
301 */
302 static void schedule_job_ms(private_scheduler_t *this, job_t *job, u_int32_t ms)
303 {
304 timeval_t tv, add;
305
306 time_monotonic(&tv);
307 add.tv_sec = ms / 1000;
308 add.tv_usec = (ms % 1000) * 1000;
309
310 timeradd(&tv, &add, &tv);
311
312 schedule_job_tv(this, job, tv);
313 }
314
315 /**
316 * Implementation of scheduler_t.destroy.
317 */
318 static void destroy(private_scheduler_t *this)
319 {
320 event_t *event;
321 this->job->cancel(this->job);
322 this->condvar->destroy(this->condvar);
323 this->mutex->destroy(this->mutex);
324 while ((event = remove_event(this)) != NULL)
325 {
326 event_destroy(event);
327 }
328 free(this->heap);
329 free(this);
330 }
331
332 /*
333 * Described in header.
334 */
335 scheduler_t * scheduler_create()
336 {
337 private_scheduler_t *this = malloc_thing(private_scheduler_t);
338
339 this->public.get_job_load = (u_int (*) (scheduler_t *this)) get_job_load;
340 this->public.schedule_job = (void (*) (scheduler_t *this, job_t *job, u_int32_t s)) schedule_job;
341 this->public.schedule_job_ms = (void (*) (scheduler_t *this, job_t *job, u_int32_t ms)) schedule_job_ms;
342 this->public.schedule_job_tv = (void (*) (scheduler_t *this, job_t *job, timeval_t tv)) schedule_job_tv;
343 this->public.destroy = (void(*)(scheduler_t*)) destroy;
344
345 /* Note: the root of the heap is at index 1 */
346 this->event_count = 0;
347 this->heap_size = HEAP_SIZE_DEFAULT;
348 this->heap = (event_t**)calloc(this->heap_size + 1, sizeof(event_t*));
349
350 this->mutex = mutex_create(MUTEX_TYPE_DEFAULT);
351 this->condvar = condvar_create(CONDVAR_TYPE_DEFAULT);
352
353 this->job = callback_job_create((callback_job_cb_t)schedule, this, NULL, NULL);
354 charon->processor->queue_job(charon->processor, (job_t*)this->job);
355
356 return &this->public;
357 }
358