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