1 /*

2 * Copyright (C) 2009-2015 Tobias Brunner

3 * Copyright (C) 2005-2007 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 */

18 /**

19 * @defgroup scheduler scheduler

20 * @{ @ingroup processing

21 */

23 #ifndef SCHEDULER_H_

24 #define SCHEDULER_H_

28 #include <library.h>

29 #include <processing/jobs/job.h>

31 /**

32 * The scheduler queues timed events which are then passed to the processor.

33 *

34 * The scheduler is implemented as a heap. A heap is a special kind of tree-

35 * based data structure that satisfies the following property: if B is a child

36 * node of A, then key(A) >= (or <=) key(B). So either the element with the

37 * greatest (max-heap) or the smallest (min-heap) key is the root of the heap.

38 * We use a min-heap with the key being the absolute unix time at which an

39 * event is scheduled. So the root is always the event that will fire next.

40 *

41 * An earlier implementation of the scheduler used a sorted linked list to store

42 * the events. That had the advantage that removing the next event was extremely

43 * fast, also, adding an event scheduled before or after all other events was

44 * equally fast (all in O(1)). The problem was, though, that adding an event

45 * in-between got slower, as the number of events grew larger (O(n)).

46 * For each connection there could be several events: IKE-rekey, NAT-keepalive,

47 * retransmissions, expire (half-open), and others. So a gateway that probably

48 * has to handle thousands of concurrent connnections has to be able to queue a

49 * large number of events as fast as possible. Locking makes this even worse, to

50 * provide thread-safety, no events can be processed, while an event is queued,

51 * so making the insertion fast is even more important.

52 *

53 * That's the advantage of the heap. Adding an element to the heap can be

54 * achieved in O(log n) - on the other hand, removing the root node also

55 * requires O(log n) operations. Consider 10000 queued events. Inserting a new

56 * event in the list implementation required up to 10000 comparisons. In the

57 * heap implementation, the worst case is about 13.3 comparisons. That's a

58 * drastic improvement.

59 *

60 * The implementation itself uses a binary tree mapped to a one-based array to

61 * store the elements. This reduces storage overhead and simplifies navigation:

62 * the children of the node at position n are at position 2n and 2n+1 (likewise

63 * the parent node of the node at position n is at position [n/2]). Thus,

64 * navigating up and down the tree is reduced to simple index computations.

65 *

66 * Adding an element to the heap works as follows: The heap is always filled

67 * from left to right, until a row is full, then the next row is filled. Mapped

68 * to an array this gets as simple as putting the new element to the first free

69 * position. In a one-based array that position equals the number of elements

70 * currently stored in the heap. Then the heap property has to be restored, i.e.

71 * the new element has to be "bubbled up" the tree until the parent node's key

72 * is smaller or the element got the new root of the tree.

73 *

74 * Removing the next event from the heap works similarly. The event itself is

75 * the root node and stored at position 1 of the array. After removing it, the

76 * root has to be replaced and the heap property has to be restored. This is

77 * done by moving the bottom element (last row, rightmost element) to the root

78 * and then "seep it down" by swapping it with child nodes until none of the

79 * children has a smaller key or it is again a leaf node.

80 */

83 /**

84 * Adds a event to the queue, using a relative time offset in s.

85 *

86 * @param job job to schedule

87 * @param time relative time to schedule job, in s

88 */

91 /**

92 * Adds a event to the queue, using a relative time offset in ms.

93 *

94 * @param job job to schedule

95 * @param time relative time to schedule job, in ms

96 */

99 /**

100 * Adds a event to the queue, using an absolut time.

101 *

102 * The passed timeval should be calculated based on the time_monotonic()

103 * function.

104 *

105 * @param job job to schedule

106 * @param time absolut time to schedule job

107 */

110 /**

111 * Returns number of jobs scheduled.

112 *

113 * @return number of scheduled jobs

114 */

117 /**

118 * Remove all scheduled jobs.

119 */

122 /**

123 * Destroys a scheduler object.

124 */

126 };

128 /**

129 * Create a scheduler.

130 *

131 * @return scheduler_t object

132 */