]>
Commit | Line | Data |
---|---|---|
e9d8db1c | 1 | /* |
11ac1dff | 2 | * Copyright (C) 2009-2015 Tobias Brunner |
9fe1a1ca | 3 | * Copyright (C) 2005-2007 Martin Willi |
c71d53ba | 4 | * Copyright (C) 2005 Jan Hutter |
19ef2aec TB |
5 | * |
6 | * Copyright (C) secunet Security Networks AG | |
e9d8db1c MW |
7 | * |
8 | * This program is free software; you can redistribute it and/or modify it | |
9 | * under the terms of the GNU General Public License as published by the | |
10 | * Free Software Foundation; either version 2 of the License, or (at your | |
11 | * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>. | |
12 | * | |
13 | * This program is distributed in the hope that it will be useful, but | |
14 | * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
15 | * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
16 | * for more details. | |
552cc11b MW |
17 | */ |
18 | ||
19 | /** | |
20 | * @defgroup scheduler scheduler | |
e18556e9 | 21 | * @{ @ingroup processing |
e9d8db1c MW |
22 | */ |
23 | ||
24 | #ifndef SCHEDULER_H_ | |
25 | #define SCHEDULER_H_ | |
26 | ||
5796aa16 MW |
27 | typedef struct scheduler_t scheduler_t; |
28 | ||
db7ef624 | 29 | #include <library.h> |
9fe1a1ca | 30 | #include <processing/jobs/job.h> |
382b4817 | 31 | |
e9d8db1c | 32 | /** |
28154e35 | 33 | * The scheduler queues timed events which are then passed to the processor. |
382b4817 | 34 | * |
28154e35 TB |
35 | * The scheduler is implemented as a heap. A heap is a special kind of tree- |
36 | * based data structure that satisfies the following property: if B is a child | |
37 | * node of A, then key(A) >= (or <=) key(B). So either the element with the | |
38 | * greatest (max-heap) or the smallest (min-heap) key is the root of the heap. | |
f3bb1bd0 | 39 | * We use a min-heap with the key being the absolute unix time at which an |
28154e35 TB |
40 | * event is scheduled. So the root is always the event that will fire next. |
41 | * | |
42 | * An earlier implementation of the scheduler used a sorted linked list to store | |
43 | * the events. That had the advantage that removing the next event was extremely | |
44 | * fast, also, adding an event scheduled before or after all other events was | |
45 | * equally fast (all in O(1)). The problem was, though, that adding an event | |
46 | * in-between got slower, as the number of events grew larger (O(n)). | |
47 | * For each connection there could be several events: IKE-rekey, NAT-keepalive, | |
48 | * retransmissions, expire (half-open), and others. So a gateway that probably | |
2db6d5b8 | 49 | * has to handle thousands of concurrent connections has to be able to queue a |
28154e35 TB |
50 | * large number of events as fast as possible. Locking makes this even worse, to |
51 | * provide thread-safety, no events can be processed, while an event is queued, | |
52 | * so making the insertion fast is even more important. | |
53 | * | |
54 | * That's the advantage of the heap. Adding an element to the heap can be | |
55 | * achieved in O(log n) - on the other hand, removing the root node also | |
56 | * requires O(log n) operations. Consider 10000 queued events. Inserting a new | |
57 | * event in the list implementation required up to 10000 comparisons. In the | |
58 | * heap implementation, the worst case is about 13.3 comparisons. That's a | |
59 | * drastic improvement. | |
60 | * | |
61 | * The implementation itself uses a binary tree mapped to a one-based array to | |
62 | * store the elements. This reduces storage overhead and simplifies navigation: | |
63 | * the children of the node at position n are at position 2n and 2n+1 (likewise | |
64 | * the parent node of the node at position n is at position [n/2]). Thus, | |
65 | * navigating up and down the tree is reduced to simple index computations. | |
66 | * | |
67 | * Adding an element to the heap works as follows: The heap is always filled | |
68 | * from left to right, until a row is full, then the next row is filled. Mapped | |
69 | * to an array this gets as simple as putting the new element to the first free | |
70 | * position. In a one-based array that position equals the number of elements | |
71 | * currently stored in the heap. Then the heap property has to be restored, i.e. | |
72 | * the new element has to be "bubbled up" the tree until the parent node's key | |
68173e1f | 73 | * is smaller or the element got the new root of the tree. |
28154e35 TB |
74 | * |
75 | * Removing the next event from the heap works similarly. The event itself is | |
76 | * the root node and stored at position 1 of the array. After removing it, the | |
77 | * root has to be replaced and the heap property has to be restored. This is | |
78 | * done by moving the bottom element (last row, rightmost element) to the root | |
79 | * and then "seep it down" by swapping it with child nodes until none of the | |
80 | * children has a smaller key or it is again a leaf node. | |
e9d8db1c | 81 | */ |
6554b5e4 | 82 | struct scheduler_t { |
7daf5226 | 83 | |
6554b5e4 MW |
84 | /** |
85 | * Adds a event to the queue, using a relative time offset in s. | |
86 | * | |
8c387909 TB |
87 | * @param job job to schedule |
88 | * @param time relative time to schedule job, in s | |
6554b5e4 | 89 | */ |
b12c53ce | 90 | void (*schedule_job) (scheduler_t *this, job_t *job, uint32_t s); |
7daf5226 | 91 | |
9fe1a1ca | 92 | /** |
6554b5e4 | 93 | * Adds a event to the queue, using a relative time offset in ms. |
9fe1a1ca | 94 | * |
8c387909 TB |
95 | * @param job job to schedule |
96 | * @param time relative time to schedule job, in ms | |
6554b5e4 | 97 | */ |
b12c53ce | 98 | void (*schedule_job_ms) (scheduler_t *this, job_t *job, uint32_t ms); |
7daf5226 | 99 | |
6554b5e4 | 100 | /** |
2db6d5b8 | 101 | * Adds a event to the queue, using an absolute time. |
9fe1a1ca | 102 | * |
3d5818ec MW |
103 | * The passed timeval should be calculated based on the time_monotonic() |
104 | * function. | |
105 | * | |
8c387909 | 106 | * @param job job to schedule |
2db6d5b8 | 107 | * @param time absolute time to schedule job |
9fe1a1ca | 108 | */ |
6554b5e4 | 109 | void (*schedule_job_tv) (scheduler_t *this, job_t *job, timeval_t tv); |
7daf5226 | 110 | |
9fe1a1ca | 111 | /** |
552cc11b | 112 | * Returns number of jobs scheduled. |
9fe1a1ca | 113 | * |
8c387909 | 114 | * @return number of scheduled jobs |
9fe1a1ca MW |
115 | */ |
116 | u_int (*get_job_load) (scheduler_t *this); | |
7daf5226 | 117 | |
11ac1dff TB |
118 | /** |
119 | * Remove all scheduled jobs. | |
120 | */ | |
121 | void (*flush)(scheduler_t *this); | |
122 | ||
e9d8db1c | 123 | /** |
552cc11b | 124 | * Destroys a scheduler object. |
e9d8db1c | 125 | */ |
9fe1a1ca | 126 | void (*destroy) (scheduler_t *this); |
e9d8db1c MW |
127 | }; |
128 | ||
ca76df97 | 129 | /** |
552cc11b | 130 | * Create a scheduler. |
28154e35 | 131 | * |
8c387909 | 132 | * @return scheduler_t object |
ca76df97 | 133 | */ |
9fe1a1ca | 134 | scheduler_t *scheduler_create(void); |
e9d8db1c | 135 | |
1490ff4d | 136 | #endif /** SCHEDULER_H_ @}*/ |