2 * Copyright (C) 2008 Tobias Brunner
3 * Copyright (C) 2005-2006 Martin Willi
4 * Copyright (C) 2005 Jan Hutter
5 * Hochschule fuer Technik Rapperswil
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>.
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
24 #include "scheduler.h"
27 #include <processing/processor.h>
28 #include <processing/jobs/callback_job.h>
29 #include <utils/mutex.h>
31 /* the initial size of the heap */
32 #define HEAP_SIZE_DEFAULT 64
34 typedef struct event_t event_t
;
37 * Event containing a job and a schedule time
41 * Time to fire the event.
46 * Every event has its assigned job.
52 * destroy an event and its job
54 static void event_destroy(event_t
*event
)
56 event
->job
->destroy(event
->job
);
60 typedef struct private_scheduler_t private_scheduler_t
;
63 * Private data of a scheduler_t object.
65 struct private_scheduler_t
{
67 * Public part of a scheduler_t object.
72 * Job which queues scheduled jobs to the processor.
77 * The heap in which the events are stored.
82 * The size of the heap.
87 * The number of scheduled events.
92 * Exclusive access to list
97 * Condvar to wait for next job.
103 * Returns the difference of two timeval structs in milliseconds
105 static long time_difference(timeval_t
*end
, timeval_t
*start
)
110 s
= end
->tv_sec
- start
->tv_sec
;
111 us
= end
->tv_usec
- start
->tv_usec
;
112 return (s
* 1000 + us
/1000);
116 * Returns the top event without removing it. Returns NULL if the heap is empty.
118 static event_t
*peek_event(private_scheduler_t
*this)
120 return this->event_count
> 0 ?
this->heap
[1] : NULL
;
124 * Removes the top event from the heap and returns it. Returns NULL if the heap
127 static event_t
*remove_event(private_scheduler_t
*this)
129 event_t
*event
, *top
;
130 if (!this->event_count
)
135 /* store the value to return */
136 event
= this->heap
[1];
137 /* move the bottom event to the top */
138 top
= this->heap
[1] = this->heap
[this->event_count
];
140 if (--this->event_count
> 1)
142 /* seep down the top event */
144 while ((position
<< 1) <= this->event_count
)
146 u_int child
= position
<< 1;
148 if ((child
+ 1) <= this->event_count
&&
149 time_difference(&this->heap
[child
+ 1]->time
,
150 &this->heap
[child
]->time
) < 0)
152 /* the "right" child is smaller */
156 if (time_difference(&top
->time
, &this->heap
[child
]->time
) <= 0)
158 /* the top event fires before the smaller of the two children, stop */
162 /* exchange with the smaller child */
163 this->heap
[position
] = this->heap
[child
];
166 this->heap
[position
] = top
;
172 * Get events from the queue and pass it to the processor
174 static job_requeue_t
schedule(private_scheduler_t
* this)
182 DBG2(DBG_JOB
, "waiting for next event...");
183 this->mutex
->lock(this->mutex
);
185 gettimeofday(&now
, NULL
);
187 if ((event
= peek_event(this)) != NULL
)
189 difference
= time_difference(&now
, &event
->time
);
193 this->mutex
->unlock(this->mutex
);
194 DBG2(DBG_JOB
, "got event, queuing job for execution");
195 charon
->processor
->queue_job(charon
->processor
, event
->job
);
197 return JOB_REQUEUE_DIRECT
;
201 pthread_cleanup_push((void*)this->mutex
->unlock
, this->mutex
);
202 pthread_setcancelstate(PTHREAD_CANCEL_ENABLE
, &oldstate
);
206 this->condvar
->timed_wait_abs(this->condvar
, this->mutex
, event
->time
);
210 this->condvar
->wait(this->condvar
, this->mutex
);
212 pthread_setcancelstate(oldstate
, NULL
);
213 pthread_cleanup_pop(TRUE
);
214 return JOB_REQUEUE_DIRECT
;
218 * Implements scheduler_t.get_job_load
220 static u_int
get_job_load(private_scheduler_t
*this)
223 this->mutex
->lock(this->mutex
);
224 count
= this->event_count
;
225 this->mutex
->unlock(this->mutex
);
230 * Implements scheduler_t.schedule_job.
232 static void schedule_job(private_scheduler_t
*this, job_t
*job
, u_int32_t time
)
240 event
= malloc_thing(event_t
);
243 /* calculate absolute time */
245 us
= (time
- s
* 1000) * 1000;
246 gettimeofday(&now
, NULL
);
247 event
->time
.tv_usec
= (now
.tv_usec
+ us
) % 1000000;
248 event
->time
.tv_sec
= now
.tv_sec
+ (now
.tv_usec
+ us
)/1000000 + s
;
250 this->mutex
->lock(this->mutex
);
253 if (this->event_count
> this->heap_size
)
255 /* double the size of the heap */
256 this->heap_size
<<= 1;
257 this->heap
= (event_t
**)realloc(this->heap
, (this->heap_size
+ 1) * sizeof(event_t
*));
259 /* "put" the event to the bottom */
260 position
= this->event_count
;
262 /* then bubble it up */
263 while (position
> 1 && time_difference(&this->heap
[position
>> 1]->time
,
266 /* parent has to be fired after the new event, move up */
267 this->heap
[position
] = this->heap
[position
>> 1];
270 this->heap
[position
] = event
;
272 this->condvar
->signal(this->condvar
);
273 this->mutex
->unlock(this->mutex
);
277 * Implementation of scheduler_t.destroy.
279 static void destroy(private_scheduler_t
*this)
282 this->job
->cancel(this->job
);
283 this->condvar
->destroy(this->condvar
);
284 this->mutex
->destroy(this->mutex
);
285 while ((event
= remove_event(this)) != NULL
)
287 event_destroy(event
);
294 * Described in header.
296 scheduler_t
* scheduler_create()
298 private_scheduler_t
*this = malloc_thing(private_scheduler_t
);
300 this->public.get_job_load
= (u_int (*) (scheduler_t
*this)) get_job_load
;
301 this->public.schedule_job
= (void (*) (scheduler_t
*this, job_t
*job
, u_int32_t ms
)) schedule_job
;
302 this->public.destroy
= (void(*)(scheduler_t
*)) destroy
;
304 /* Note: the root of the heap is at index 1 */
305 this->event_count
= 0;
306 this->heap_size
= HEAP_SIZE_DEFAULT
;
307 this->heap
= (event_t
**)calloc(this->heap_size
+ 1, sizeof(event_t
*));
309 this->mutex
= mutex_create(MUTEX_DEFAULT
);
310 this->condvar
= condvar_create(CONDVAR_DEFAULT
);
312 this->job
= callback_job_create((callback_job_cb_t
)schedule
, this, NULL
, NULL
);
313 charon
->processor
->queue_job(charon
->processor
, (job_t
*)this->job
);
315 return &this->public;