blob: 82e6f5322bcafa2fd8588f7abc0ab0d532a7a2c9 [file] [log] [blame]
Willy Tarreaubaaee002006-06-26 02:48:02 +02001/*
Willy Tarreau24f4efa2010-08-27 17:56:48 +02002 * include/proto/task.h
3 * Functions for task management.
4 *
5 * Copyright (C) 2000-2010 Willy Tarreau - w@1wt.eu
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 */
Willy Tarreaubaaee002006-06-26 02:48:02 +020021
22#ifndef _PROTO_TASK_H
23#define _PROTO_TASK_H
24
25
26#include <sys/time.h>
Willy Tarreaue3ba5f02006-06-29 18:54:54 +020027
28#include <common/config.h>
Willy Tarreau2dd0d472006-06-29 17:53:05 +020029#include <common/memory.h>
Willy Tarreau96bcfd72007-04-29 10:41:56 +020030#include <common/mini-clist.h>
31#include <common/standard.h>
Willy Tarreaud0a201b2009-03-08 15:53:06 +010032#include <common/ticks.h>
Willy Tarreau45cb4fb2009-10-26 21:10:04 +010033#include <eb32tree.h>
Willy Tarreau96bcfd72007-04-29 10:41:56 +020034
Willy Tarreaueb118892014-11-13 16:57:19 +010035#include <types/global.h>
Willy Tarreaue3ba5f02006-06-29 18:54:54 +020036#include <types/task.h>
Willy Tarreaubaaee002006-06-26 02:48:02 +020037
Willy Tarreaud0a201b2009-03-08 15:53:06 +010038/* Principle of the wait queue.
39 *
40 * We want to be able to tell whether an expiration date is before of after the
41 * current time <now>. We KNOW that expiration dates are never too far apart,
42 * because they are measured in ticks (milliseconds). We also know that almost
43 * all dates will be in the future, and that a very small part of them will be
44 * in the past, they are the ones which have expired since last time we checked
45 * them. Using ticks, we know if a date is in the future or in the past, but we
46 * cannot use that to store sorted information because that reference changes
47 * all the time.
48 *
Willy Tarreaue35c94a2009-03-21 10:01:42 +010049 * We'll use the fact that the time wraps to sort timers. Timers above <now>
50 * are in the future, timers below <now> are in the past. Here, "above" and
51 * "below" are to be considered modulo 2^31.
Willy Tarreaud0a201b2009-03-08 15:53:06 +010052 *
Willy Tarreaue35c94a2009-03-21 10:01:42 +010053 * Timers are stored sorted in an ebtree. We use the new ability for ebtrees to
54 * lookup values starting from X to only expire tasks between <now> - 2^31 and
55 * <now>. If the end of the tree is reached while walking over it, we simply
56 * loop back to the beginning. That way, we have no problem keeping sorted
57 * wrapping timers in a tree, between (now - 24 days) and (now + 24 days). The
58 * keys in the tree always reflect their real position, none can be infinite.
59 * This reduces the number of checks to be performed.
Willy Tarreaud0a201b2009-03-08 15:53:06 +010060 *
61 * Another nice optimisation is to allow a timer to stay at an old place in the
62 * queue as long as it's not further than the real expiration date. That way,
63 * we use the tree as a place holder for a minorant of the real expiration
64 * date. Since we have a very low chance of hitting a timeout anyway, we can
65 * bounce the nodes to their right place when we scan the tree if we encounter
66 * a misplaced node once in a while. This even allows us not to remove the
67 * infinite timers from the wait queue.
68 *
69 * So, to summarize, we have :
70 * - node->key always defines current position in the wait queue
71 * - timer is the real expiration date (possibly infinite)
Willy Tarreaue35c94a2009-03-21 10:01:42 +010072 * - node->key is always before or equal to timer
Willy Tarreaud0a201b2009-03-08 15:53:06 +010073 *
74 * The run queue works similarly to the wait queue except that the current date
75 * is replaced by an insertion counter which can also wrap without any problem.
76 */
77
Willy Tarreaue35c94a2009-03-21 10:01:42 +010078/* The farthest we can look back in a timer tree */
79#define TIMER_LOOK_BACK (1U << 31)
Willy Tarreaud0a201b2009-03-08 15:53:06 +010080
81/* a few exported variables */
Willy Tarreaua4613182009-03-21 18:13:21 +010082extern unsigned int nb_tasks; /* total number of tasks */
Christopher Faulet34c5cc92016-12-06 09:15:30 +010083extern unsigned int tasks_run_queue; /* run queue size */
84extern unsigned int tasks_run_queue_cur;
Willy Tarreauc7bdf092009-03-21 18:33:52 +010085extern unsigned int nb_tasks_cur;
Willy Tarreau91e99932008-06-30 07:51:00 +020086extern unsigned int niced_tasks; /* number of niced tasks in the run queue */
Willy Tarreauc6ca1a02007-05-13 19:43:47 +020087extern struct pool_head *pool2_task;
88
Willy Tarreau4726f532009-03-07 17:25:21 +010089/* return 0 if task is in run queue, otherwise non-zero */
90static inline int task_in_rq(struct task *t)
91{
92 return t->rq.node.leaf_p != NULL;
93}
94
95/* return 0 if task is in wait queue, otherwise non-zero */
96static inline int task_in_wq(struct task *t)
97{
98 return t->wq.node.leaf_p != NULL;
99}
100
Willy Tarreaufdccded2008-08-29 18:19:04 +0200101/* puts the task <t> in run queue with reason flags <f>, and returns <t> */
Willy Tarreau4df82062008-08-29 15:26:14 +0200102struct task *__task_wakeup(struct task *t);
Willy Tarreaufdccded2008-08-29 18:19:04 +0200103static inline struct task *task_wakeup(struct task *t, unsigned int f)
Willy Tarreau4df82062008-08-29 15:26:14 +0200104{
Emeric Brun01948972017-03-30 15:37:25 +0200105 /* If task is running, we postpone the call
106 * and backup the state.
107 */
108 if (unlikely(t->state & TASK_RUNNING)) {
109 t->pending_state |= f;
110 return t;
111 }
Willy Tarreau4726f532009-03-07 17:25:21 +0100112 if (likely(!task_in_rq(t)))
Willy Tarreaufdccded2008-08-29 18:19:04 +0200113 __task_wakeup(t);
114 t->state |= f;
115 return t;
Willy Tarreau4df82062008-08-29 15:26:14 +0200116}
Willy Tarreaubaaee002006-06-26 02:48:02 +0200117
Willy Tarreau4726f532009-03-07 17:25:21 +0100118/*
119 * Unlink the task from the wait queue, and possibly update the last_timer
120 * pointer. A pointer to the task itself is returned. The task *must* already
121 * be in the wait queue before calling this function. If unsure, use the safer
122 * task_unlink_wq() function.
Willy Tarreaubaaee002006-06-26 02:48:02 +0200123 */
Willy Tarreau4726f532009-03-07 17:25:21 +0100124static inline struct task *__task_unlink_wq(struct task *t)
125{
126 eb32_delete(&t->wq);
Willy Tarreau4726f532009-03-07 17:25:21 +0100127 return t;
128}
129
130static inline struct task *task_unlink_wq(struct task *t)
Willy Tarreaubaaee002006-06-26 02:48:02 +0200131{
Willy Tarreau4726f532009-03-07 17:25:21 +0100132 if (likely(task_in_wq(t)))
133 __task_unlink_wq(t);
Willy Tarreau96bcfd72007-04-29 10:41:56 +0200134 return t;
Willy Tarreaubaaee002006-06-26 02:48:02 +0200135}
136
137/*
Christopher Faulet34c5cc92016-12-06 09:15:30 +0100138 * Unlink the task from the run queue. The tasks_run_queue size and number of
139 * niced tasks are updated too. A pointer to the task itself is returned. The
140 * task *must* already be in the run queue before calling this function. If
141 * unsure, use the safer task_unlink_rq() function. Note that the pointer to the
142 * next run queue entry is neither checked nor updated.
Willy Tarreaubaaee002006-06-26 02:48:02 +0200143 */
Willy Tarreau4726f532009-03-07 17:25:21 +0100144static inline struct task *__task_unlink_rq(struct task *t)
Willy Tarreaubaaee002006-06-26 02:48:02 +0200145{
Willy Tarreau4726f532009-03-07 17:25:21 +0100146 eb32_delete(&t->rq);
Christopher Faulet34c5cc92016-12-06 09:15:30 +0100147 tasks_run_queue--;
Willy Tarreau4726f532009-03-07 17:25:21 +0100148 if (likely(t->nice))
149 niced_tasks--;
Willy Tarreauce44f122008-07-05 18:16:19 +0200150 return t;
151}
Willy Tarreau9789f7b2008-06-24 08:17:16 +0200152
Willy Tarreau501260b2015-02-23 16:07:01 +0100153/* This function unlinks task <t> from the run queue if it is in it. It also
154 * takes care of updating the next run queue task if it was this task.
155 */
Willy Tarreau4726f532009-03-07 17:25:21 +0100156static inline struct task *task_unlink_rq(struct task *t)
157{
Willy Tarreau501260b2015-02-23 16:07:01 +0100158 if (likely(task_in_rq(t))) {
Willy Tarreau4726f532009-03-07 17:25:21 +0100159 __task_unlink_rq(t);
Willy Tarreau501260b2015-02-23 16:07:01 +0100160 }
Willy Tarreau4726f532009-03-07 17:25:21 +0100161 return t;
162}
163
Willy Tarreauce44f122008-07-05 18:16:19 +0200164/*
165 * Unlinks the task and adjusts run queue stats.
166 * A pointer to the task itself is returned.
167 */
168static inline struct task *task_delete(struct task *t)
169{
Willy Tarreau4726f532009-03-07 17:25:21 +0100170 task_unlink_wq(t);
171 task_unlink_rq(t);
Willy Tarreau9789f7b2008-06-24 08:17:16 +0200172 return t;
173}
174
175/*
Willy Tarreaua4613182009-03-21 18:13:21 +0100176 * Initialize a new task. The bare minimum is performed (queue pointers and
177 * state). The task is returned. This function should not be used outside of
178 * task_new().
Willy Tarreau9789f7b2008-06-24 08:17:16 +0200179 */
180static inline struct task *task_init(struct task *t)
181{
Willy Tarreau4726f532009-03-07 17:25:21 +0100182 t->wq.node.leaf_p = NULL;
183 t->rq.node.leaf_p = NULL;
Emeric Brun01948972017-03-30 15:37:25 +0200184 t->pending_state = t->state = TASK_SLEEPING;
Willy Tarreau91e99932008-06-30 07:51:00 +0200185 t->nice = 0;
Willy Tarreau3884cba2009-03-28 17:54:35 +0100186 t->calls = 0;
Willy Tarreauf4219992017-07-24 17:52:58 +0200187 t->expire = TICK_ETERNITY;
Willy Tarreaubaaee002006-06-26 02:48:02 +0200188 return t;
189}
190
191/*
Willy Tarreaua4613182009-03-21 18:13:21 +0100192 * Allocate and initialise a new task. The new task is returned, or NULL in
193 * case of lack of memory. The task count is incremented. Tasks should only
194 * be allocated this way, and must be freed using task_free().
195 */
196static inline struct task *task_new(void)
197{
198 struct task *t = pool_alloc2(pool2_task);
199 if (t) {
200 nb_tasks++;
201 task_init(t);
202 }
203 return t;
204}
205
206/*
207 * Free a task. Its context must have been freed since it will be lost.
208 * The task count is decremented.
Willy Tarreaubaaee002006-06-26 02:48:02 +0200209 */
210static inline void task_free(struct task *t)
211{
Willy Tarreauc6ca1a02007-05-13 19:43:47 +0200212 pool_free2(pool2_task, t);
Willy Tarreaueb118892014-11-13 16:57:19 +0100213 if (unlikely(stopping))
214 pool_flush2(pool2_task);
Willy Tarreaua4613182009-03-21 18:13:21 +0100215 nb_tasks--;
Willy Tarreaubaaee002006-06-26 02:48:02 +0200216}
217
Willy Tarreau4726f532009-03-07 17:25:21 +0100218/* Place <task> into the wait queue, where it may already be. If the expiration
Willy Tarreau531cf0c2009-03-08 16:35:27 +0100219 * timer is infinite, do nothing and rely on wake_expired_task to clean up.
Willy Tarreaubaaee002006-06-26 02:48:02 +0200220 */
Willy Tarreau531cf0c2009-03-08 16:35:27 +0100221void __task_queue(struct task *task);
222static inline void task_queue(struct task *task)
223{
224 /* If we already have a place in the wait queue no later than the
225 * timeout we're trying to set, we'll stay there, because it is very
226 * unlikely that we will reach the timeout anyway. If the timeout
227 * has been disabled, it's useless to leave the queue as well. We'll
228 * rely on wake_expired_tasks() to catch the node and move it to the
229 * proper place should it ever happen. Finally we only add the task
230 * to the queue if it was not there or if it was further than what
231 * we want.
232 */
233 if (!tick_isset(task->expire))
234 return;
235
Willy Tarreaue35c94a2009-03-21 10:01:42 +0100236 if (!task_in_wq(task) || tick_is_lt(task->expire, task->wq.key))
Willy Tarreau531cf0c2009-03-08 16:35:27 +0100237 __task_queue(task);
238}
Willy Tarreaubaaee002006-06-26 02:48:02 +0200239
Willy Tarreau26e48812011-07-25 14:30:42 +0200240/* Ensure <task> will be woken up at most at <when>. If the task is already in
241 * the run queue (but not running), nothing is done. It may be used that way
242 * with a delay : task_schedule(task, tick_add(now_ms, delay));
243 */
244static inline void task_schedule(struct task *task, int when)
245{
246 if (task_in_rq(task))
247 return;
248
249 if (task_in_wq(task))
250 when = tick_first(when, task->expire);
251
252 task->expire = when;
253 if (!task_in_wq(task) || tick_is_lt(task->expire, task->wq.key))
254 __task_queue(task);
255}
256
Willy Tarreaubaaee002006-06-26 02:48:02 +0200257/*
Willy Tarreau918ff602011-07-25 16:33:49 +0200258 * This does 3 things :
Willy Tarreaubaaee002006-06-26 02:48:02 +0200259 * - wake up all expired tasks
260 * - call all runnable tasks
Willy Tarreaud825eef2007-05-12 22:35:00 +0200261 * - return the date of next event in <next> or eternity.
Willy Tarreaubaaee002006-06-26 02:48:02 +0200262 */
263
Thierry FOURNIER9cf7c4b2014-12-15 13:26:01 +0100264void process_runnable_tasks();
Willy Tarreaubaaee002006-06-26 02:48:02 +0200265
Willy Tarreau58b458d2008-06-29 22:40:23 +0200266/*
267 * Extract all expired timers from the timer queue, and wakes up all
268 * associated tasks. Returns the date of next event (or eternity).
269 */
Thierry FOURNIER9cf7c4b2014-12-15 13:26:01 +0100270int wake_expired_tasks();
Willy Tarreau58b458d2008-06-29 22:40:23 +0200271
Willy Tarreaud0a201b2009-03-08 15:53:06 +0100272/* Perform minimal initializations, report 0 in case of error, 1 if OK. */
273int init_task();
Willy Tarreaubaaee002006-06-26 02:48:02 +0200274
275#endif /* _PROTO_TASK_H */
276
277/*
278 * Local variables:
279 * c-indent-level: 8
280 * c-basic-offset: 8
281 * End:
282 */