Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 1 | /* |
| 2 | include/proto/task.h |
| 3 | Functions for task management. |
| 4 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 5 | Copyright (C) 2000-2009 Willy Tarreau - w@1wt.eu |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 6 | |
| 7 | This library is free software; you can redistribute it and/or |
| 8 | modify it under the terms of the GNU Lesser General Public |
| 9 | License as published by the Free Software Foundation, version 2.1 |
| 10 | exclusively. |
| 11 | |
| 12 | This library is distributed in the hope that it will be useful, |
| 13 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 15 | Lesser General Public License for more details. |
| 16 | |
| 17 | You should have received a copy of the GNU Lesser General Public |
| 18 | License along with this library; if not, write to the Free Software |
| 19 | Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
| 20 | */ |
| 21 | |
| 22 | #ifndef _PROTO_TASK_H |
| 23 | #define _PROTO_TASK_H |
| 24 | |
| 25 | |
| 26 | #include <sys/time.h> |
Willy Tarreau | e3ba5f0 | 2006-06-29 18:54:54 +0200 | [diff] [blame] | 27 | |
| 28 | #include <common/config.h> |
Willy Tarreau | 2dd0d47 | 2006-06-29 17:53:05 +0200 | [diff] [blame] | 29 | #include <common/memory.h> |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 30 | #include <common/mini-clist.h> |
| 31 | #include <common/standard.h> |
Willy Tarreau | d0a201b | 2009-03-08 15:53:06 +0100 | [diff] [blame] | 32 | #include <common/ticks.h> |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 33 | |
Willy Tarreau | e3ba5f0 | 2006-06-29 18:54:54 +0200 | [diff] [blame] | 34 | #include <types/task.h> |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 35 | |
Willy Tarreau | d0a201b | 2009-03-08 15:53:06 +0100 | [diff] [blame] | 36 | /* Principle of the wait queue. |
| 37 | * |
| 38 | * We want to be able to tell whether an expiration date is before of after the |
| 39 | * current time <now>. We KNOW that expiration dates are never too far apart, |
| 40 | * because they are measured in ticks (milliseconds). We also know that almost |
| 41 | * all dates will be in the future, and that a very small part of them will be |
| 42 | * in the past, they are the ones which have expired since last time we checked |
| 43 | * them. Using ticks, we know if a date is in the future or in the past, but we |
| 44 | * cannot use that to store sorted information because that reference changes |
| 45 | * all the time. |
| 46 | * |
Willy Tarreau | e35c94a | 2009-03-21 10:01:42 +0100 | [diff] [blame] | 47 | * We'll use the fact that the time wraps to sort timers. Timers above <now> |
| 48 | * are in the future, timers below <now> are in the past. Here, "above" and |
| 49 | * "below" are to be considered modulo 2^31. |
Willy Tarreau | d0a201b | 2009-03-08 15:53:06 +0100 | [diff] [blame] | 50 | * |
Willy Tarreau | e35c94a | 2009-03-21 10:01:42 +0100 | [diff] [blame] | 51 | * Timers are stored sorted in an ebtree. We use the new ability for ebtrees to |
| 52 | * lookup values starting from X to only expire tasks between <now> - 2^31 and |
| 53 | * <now>. If the end of the tree is reached while walking over it, we simply |
| 54 | * loop back to the beginning. That way, we have no problem keeping sorted |
| 55 | * wrapping timers in a tree, between (now - 24 days) and (now + 24 days). The |
| 56 | * keys in the tree always reflect their real position, none can be infinite. |
| 57 | * This reduces the number of checks to be performed. |
Willy Tarreau | d0a201b | 2009-03-08 15:53:06 +0100 | [diff] [blame] | 58 | * |
| 59 | * Another nice optimisation is to allow a timer to stay at an old place in the |
| 60 | * queue as long as it's not further than the real expiration date. That way, |
| 61 | * we use the tree as a place holder for a minorant of the real expiration |
| 62 | * date. Since we have a very low chance of hitting a timeout anyway, we can |
| 63 | * bounce the nodes to their right place when we scan the tree if we encounter |
| 64 | * a misplaced node once in a while. This even allows us not to remove the |
| 65 | * infinite timers from the wait queue. |
| 66 | * |
| 67 | * So, to summarize, we have : |
| 68 | * - node->key always defines current position in the wait queue |
| 69 | * - timer is the real expiration date (possibly infinite) |
Willy Tarreau | e35c94a | 2009-03-21 10:01:42 +0100 | [diff] [blame] | 70 | * - node->key is always before or equal to timer |
Willy Tarreau | d0a201b | 2009-03-08 15:53:06 +0100 | [diff] [blame] | 71 | * |
| 72 | * The run queue works similarly to the wait queue except that the current date |
| 73 | * is replaced by an insertion counter which can also wrap without any problem. |
| 74 | */ |
| 75 | |
Willy Tarreau | e35c94a | 2009-03-21 10:01:42 +0100 | [diff] [blame] | 76 | /* The farthest we can look back in a timer tree */ |
| 77 | #define TIMER_LOOK_BACK (1U << 31) |
Willy Tarreau | d0a201b | 2009-03-08 15:53:06 +0100 | [diff] [blame] | 78 | |
| 79 | /* a few exported variables */ |
Willy Tarreau | 91e9993 | 2008-06-30 07:51:00 +0200 | [diff] [blame] | 80 | extern unsigned int run_queue; /* run queue size */ |
| 81 | extern unsigned int niced_tasks; /* number of niced tasks in the run queue */ |
Willy Tarreau | c6ca1a0 | 2007-05-13 19:43:47 +0200 | [diff] [blame] | 82 | extern struct pool_head *pool2_task; |
Willy Tarreau | ce44f12 | 2008-07-05 18:16:19 +0200 | [diff] [blame] | 83 | extern struct task *last_timer; /* optimization: last queued timer */ |
Willy Tarreau | c6ca1a0 | 2007-05-13 19:43:47 +0200 | [diff] [blame] | 84 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 85 | /* return 0 if task is in run queue, otherwise non-zero */ |
| 86 | static inline int task_in_rq(struct task *t) |
| 87 | { |
| 88 | return t->rq.node.leaf_p != NULL; |
| 89 | } |
| 90 | |
| 91 | /* return 0 if task is in wait queue, otherwise non-zero */ |
| 92 | static inline int task_in_wq(struct task *t) |
| 93 | { |
| 94 | return t->wq.node.leaf_p != NULL; |
| 95 | } |
| 96 | |
Willy Tarreau | fdccded | 2008-08-29 18:19:04 +0200 | [diff] [blame] | 97 | /* puts the task <t> in run queue with reason flags <f>, and returns <t> */ |
Willy Tarreau | 4df8206 | 2008-08-29 15:26:14 +0200 | [diff] [blame] | 98 | struct task *__task_wakeup(struct task *t); |
Willy Tarreau | fdccded | 2008-08-29 18:19:04 +0200 | [diff] [blame] | 99 | static inline struct task *task_wakeup(struct task *t, unsigned int f) |
Willy Tarreau | 4df8206 | 2008-08-29 15:26:14 +0200 | [diff] [blame] | 100 | { |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 101 | if (likely(!task_in_rq(t))) |
Willy Tarreau | fdccded | 2008-08-29 18:19:04 +0200 | [diff] [blame] | 102 | __task_wakeup(t); |
| 103 | t->state |= f; |
| 104 | return t; |
Willy Tarreau | 4df8206 | 2008-08-29 15:26:14 +0200 | [diff] [blame] | 105 | } |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 106 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 107 | /* |
| 108 | * Unlink the task from the wait queue, and possibly update the last_timer |
| 109 | * pointer. A pointer to the task itself is returned. The task *must* already |
| 110 | * be in the wait queue before calling this function. If unsure, use the safer |
| 111 | * task_unlink_wq() function. |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 112 | */ |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 113 | static inline struct task *__task_unlink_wq(struct task *t) |
| 114 | { |
| 115 | eb32_delete(&t->wq); |
| 116 | if (last_timer == t) |
| 117 | last_timer = NULL; |
| 118 | return t; |
| 119 | } |
| 120 | |
| 121 | static inline struct task *task_unlink_wq(struct task *t) |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 122 | { |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 123 | if (likely(task_in_wq(t))) |
| 124 | __task_unlink_wq(t); |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 125 | return t; |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 126 | } |
| 127 | |
| 128 | /* |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 129 | * Unlink the task from the run queue. The run_queue size and number of niced |
| 130 | * tasks are updated too. A pointer to the task itself is returned. The task |
| 131 | * *must* already be in the wait queue before calling this function. If unsure, |
| 132 | * use the safer task_unlink_rq() function. |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 133 | */ |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 134 | static inline struct task *__task_unlink_rq(struct task *t) |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 135 | { |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 136 | eb32_delete(&t->rq); |
| 137 | run_queue--; |
| 138 | if (likely(t->nice)) |
| 139 | niced_tasks--; |
Willy Tarreau | ce44f12 | 2008-07-05 18:16:19 +0200 | [diff] [blame] | 140 | return t; |
| 141 | } |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 142 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 143 | static inline struct task *task_unlink_rq(struct task *t) |
| 144 | { |
| 145 | if (likely(task_in_rq(t))) |
| 146 | __task_unlink_rq(t); |
| 147 | return t; |
| 148 | } |
| 149 | |
Willy Tarreau | ce44f12 | 2008-07-05 18:16:19 +0200 | [diff] [blame] | 150 | /* |
| 151 | * Unlinks the task and adjusts run queue stats. |
| 152 | * A pointer to the task itself is returned. |
| 153 | */ |
| 154 | static inline struct task *task_delete(struct task *t) |
| 155 | { |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 156 | task_unlink_wq(t); |
| 157 | task_unlink_rq(t); |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 158 | return t; |
| 159 | } |
| 160 | |
| 161 | /* |
| 162 | * Initialize a new task. The bare minimum is performed (queue pointers and state). |
| 163 | * The task is returned. |
| 164 | */ |
| 165 | static inline struct task *task_init(struct task *t) |
| 166 | { |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 167 | t->wq.node.leaf_p = NULL; |
| 168 | t->rq.node.leaf_p = NULL; |
Willy Tarreau | fdccded | 2008-08-29 18:19:04 +0200 | [diff] [blame] | 169 | t->state = TASK_SLEEPING; |
Willy Tarreau | 91e9993 | 2008-06-30 07:51:00 +0200 | [diff] [blame] | 170 | t->nice = 0; |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 171 | return t; |
| 172 | } |
| 173 | |
| 174 | /* |
| 175 | * frees a task. Its context must have been freed since it will be lost. |
| 176 | */ |
| 177 | static inline void task_free(struct task *t) |
| 178 | { |
Willy Tarreau | c6ca1a0 | 2007-05-13 19:43:47 +0200 | [diff] [blame] | 179 | pool_free2(pool2_task, t); |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 180 | } |
| 181 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame] | 182 | /* Place <task> into the wait queue, where it may already be. If the expiration |
Willy Tarreau | 531cf0c | 2009-03-08 16:35:27 +0100 | [diff] [blame] | 183 | * timer is infinite, do nothing and rely on wake_expired_task to clean up. |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 184 | */ |
Willy Tarreau | 531cf0c | 2009-03-08 16:35:27 +0100 | [diff] [blame] | 185 | void __task_queue(struct task *task); |
| 186 | static inline void task_queue(struct task *task) |
| 187 | { |
| 188 | /* If we already have a place in the wait queue no later than the |
| 189 | * timeout we're trying to set, we'll stay there, because it is very |
| 190 | * unlikely that we will reach the timeout anyway. If the timeout |
| 191 | * has been disabled, it's useless to leave the queue as well. We'll |
| 192 | * rely on wake_expired_tasks() to catch the node and move it to the |
| 193 | * proper place should it ever happen. Finally we only add the task |
| 194 | * to the queue if it was not there or if it was further than what |
| 195 | * we want. |
| 196 | */ |
| 197 | if (!tick_isset(task->expire)) |
| 198 | return; |
| 199 | |
Willy Tarreau | e35c94a | 2009-03-21 10:01:42 +0100 | [diff] [blame] | 200 | if (!task_in_wq(task) || tick_is_lt(task->expire, task->wq.key)) |
Willy Tarreau | 531cf0c | 2009-03-08 16:35:27 +0100 | [diff] [blame] | 201 | __task_queue(task); |
| 202 | } |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 203 | |
| 204 | /* |
| 205 | * This does 4 things : |
| 206 | * - wake up all expired tasks |
| 207 | * - call all runnable tasks |
| 208 | * - call maintain_proxies() to enable/disable the listeners |
Willy Tarreau | d825eef | 2007-05-12 22:35:00 +0200 | [diff] [blame] | 209 | * - return the date of next event in <next> or eternity. |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 210 | */ |
| 211 | |
Willy Tarreau | 0c303ee | 2008-07-07 00:09:58 +0200 | [diff] [blame] | 212 | void process_runnable_tasks(int *next); |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 213 | |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 214 | /* |
| 215 | * Extract all expired timers from the timer queue, and wakes up all |
| 216 | * associated tasks. Returns the date of next event (or eternity). |
| 217 | */ |
Willy Tarreau | 0c303ee | 2008-07-07 00:09:58 +0200 | [diff] [blame] | 218 | void wake_expired_tasks(int *next); |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 219 | |
Willy Tarreau | d0a201b | 2009-03-08 15:53:06 +0100 | [diff] [blame] | 220 | /* Perform minimal initializations, report 0 in case of error, 1 if OK. */ |
| 221 | int init_task(); |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 222 | |
| 223 | #endif /* _PROTO_TASK_H */ |
| 224 | |
| 225 | /* |
| 226 | * Local variables: |
| 227 | * c-indent-level: 8 |
| 228 | * c-basic-offset: 8 |
| 229 | * End: |
| 230 | */ |