13
15
#include <common/config.h>
16
#include <common/eb32tree.h>
14
17
#include <common/memory.h>
15
18
#include <common/mini-clist.h>
16
19
#include <common/standard.h>
17
20
#include <common/time.h>
19
22
#include <proto/proxy.h>
23
#include <proto/session.h>
20
24
#include <proto/task.h>
21
#include <types/task.h>
23
// FIXME: check 8bitops.c for faster FLS
24
#include <import/bitops.h>
25
#include <import/tree.h>
27
static struct ultree *stack[LLONGBITS];
29
struct pool_head *pool2_task, *pool2_tree64;
31
UL2TREE_HEAD(timer_wq);
32
void *eternity_queue = NULL;
33
void *run_queue = NULL;
26
struct pool_head *pool2_task;
28
unsigned int nb_tasks = 0;
29
unsigned int run_queue = 0;
30
unsigned int run_queue_cur = 0; /* copy of the run queue size */
31
unsigned int nb_tasks_cur = 0; /* copy of the tasks count */
32
unsigned int niced_tasks = 0; /* number of niced tasks in the run queue */
33
struct eb32_node *last_timer = NULL; /* optimization: last queued timer */
35
static struct eb_root timers; /* sorted timers tree */
36
static struct eb_root rqueue; /* tree constituting the run queue */
37
static unsigned int rqueue_ticks; /* insertion count */
39
/* Puts the task <t> in run queue at a position depending on t->nice. <t> is
40
* returned. The nice value assigns boosts in 32th of the run queue size. A
41
* nice value of -1024 sets the task to -run_queue*32, while a nice value of
42
* 1024 sets the task to run_queue*32. The state flags are cleared, so the
43
* caller will have to set its flags after this call.
44
* The task must not already be in the run queue. If unsure, use the safer
45
* task_wakeup() function.
47
struct task *__task_wakeup(struct task *t)
50
t->rq.key = ++rqueue_ticks;
52
if (likely(t->nice)) {
56
if (likely(t->nice > 0))
57
offset = (unsigned)((run_queue * (unsigned int)t->nice) / 32U);
59
offset = -(unsigned)((run_queue * (unsigned int)-t->nice) / 32U);
63
/* clear state flags at the same time */
64
t->state &= ~TASK_WOKEN_ANY;
66
eb32_insert(&rqueue, &t->rq);
73
* Inserts a task into the wait queue at the position given by its expiration
74
* date. It does not matter if the task was already in the wait queue or not,
75
* as it will be unlinked. The task must not have an infinite expiration timer.
76
* Last, tasks must not be queued further than the end of the tree, which is
77
* between <now_ms> and <now_ms> + 2^31 ms (now+24days in 32bit).
79
* This function should not be used directly, it is meant to be called by the
80
* inline version of task_queue() which performs a few cheap preliminary tests
81
* before deciding to call __task_queue().
83
void __task_queue(struct task *task)
85
if (likely(task_in_wq(task)))
86
__task_unlink_wq(task);
88
/* the task is not in the queue now */
89
task->wq.key = task->expire;
90
#ifdef DEBUG_CHECK_INVALID_EXPIRATION_DATES
91
if (tick_is_lt(task->wq.key, now_ms))
92
/* we're queuing too far away or in the past (most likely) */
96
if (likely(last_timer &&
97
last_timer->node.bit < 0 &&
98
last_timer->key == task->wq.key &&
99
last_timer->node.node_p)) {
100
/* Most often, last queued timer has the same expiration date, so
101
* if it's not queued at the root, let's queue a dup directly there.
102
* Note that we can only use dups at the dup tree's root (most
105
eb_insert_dup(&last_timer->node, &task->wq.node);
106
if (task->wq.node.bit < last_timer->node.bit)
107
last_timer = &task->wq;
110
eb32_insert(&timers, &task->wq);
111
if (!last_timer || (task->wq.node.bit < last_timer->node.bit))
112
last_timer = &task->wq;
117
* Extract all expired timers from the timer queue, and wakes up all
118
* associated tasks. Returns the date of next event (or eternity) in <next>.
120
void wake_expired_tasks(int *next)
123
struct eb32_node *eb;
125
eb = eb32_lookup_ge(&timers, now_ms - TIMER_LOOK_BACK);
128
/* we might have reached the end of the tree, typically because
129
* <now_ms> is in the first half and we're first scanning the last
130
* half. Let's loop back to the beginning of the tree now.
132
eb = eb32_first(&timers);
137
if (likely(tick_is_lt(now_ms, eb->key))) {
138
/* timer not expired yet, revisit it later */
143
/* timer looks expired, detach it from the queue */
144
task = eb32_entry(eb, struct task, wq);
146
__task_unlink_wq(task);
148
/* It is possible that this task was left at an earlier place in the
149
* tree because a recent call to task_queue() has not moved it. This
150
* happens when the new expiration date is later than the old one.
151
* Since it is very unlikely that we reach a timeout anyway, it's a
152
* lot cheaper to proceed like this because we almost never update
153
* the tree. We may also find disabled expiration dates there. Since
154
* we have detached the task from the tree, we simply call task_queue
155
* to take care of this.
157
if (!tick_is_expired(task->expire, now_ms)) {
161
task_wakeup(task, TASK_WOKEN_TIMER);
164
/* We have found no task to expire in any tree */
165
*next = TICK_ETERNITY;
169
/* The run queue is chronologically sorted in a tree. An insertion counter is
170
* used to assign a position to each task. This counter may be combined with
171
* other variables (eg: nice value) to set the final position in the tree. The
172
* counter may wrap without a problem, of course. We then limit the number of
173
* tasks processed at once to 1/4 of the number of tasks in the queue, and to
174
* 200 max in any case, so that general latency remains low and so that task
175
* positions have a chance to be considered.
177
* The function adjusts <next> if a new event is closer.
179
void process_runnable_tasks(int *next)
182
struct eb32_node *eb;
183
unsigned int max_processed;
186
run_queue_cur = run_queue; /* keep a copy for reporting */
187
nb_tasks_cur = nb_tasks;
188
max_processed = run_queue;
189
if (max_processed > 200)
192
if (likely(niced_tasks))
193
max_processed = (max_processed + 3) / 4;
196
eb = eb32_lookup_ge(&rqueue, rqueue_ticks - TIMER_LOOK_BACK);
197
while (max_processed--) {
198
/* Note: this loop is one of the fastest code path in
199
* the whole program. It should not be re-arranged
200
* without a good reason.
204
/* we might have reached the end of the tree, typically because
205
* <rqueue_ticks> is in the first half and we're first scanning
206
* the last half. Let's loop back to the beginning of the tree now.
208
eb = eb32_first(&rqueue);
213
/* detach the task from the queue */
214
t = eb32_entry(eb, struct task, rq);
218
t->state |= TASK_RUNNING;
219
/* This is an optimisation to help the processor's branch
220
* predictor take this most common call.
223
if (likely(t->process == process_session))
224
t = process_session(t);
228
if (likely(t != NULL)) {
229
t->state &= ~TASK_RUNNING;
232
expire = tick_first_2nz(expire, t->expire);
235
/* if the task has put itself back into the run queue, we want to ensure
236
* it will be served at the proper time, especially if it's reniced.
238
if (unlikely(task_in_rq(t)) && (!eb || tick_is_lt(t->rq.key, eb->key))) {
239
eb = eb32_lookup_ge(&rqueue, rqueue_ticks - TIMER_LOOK_BACK);
35
246
/* perform minimal intializations, report 0 in case of error, 1 if OK. */
249
memset(&timers, 0, sizeof(timers));
250
memset(&rqueue, 0, sizeof(rqueue));
38
251
pool2_task = create_pool("task", sizeof(struct task), MEM_F_SHARED);
39
pool2_tree64 = create_pool("tree64", sizeof(struct tree64), MEM_F_SHARED);
40
return pool2_task && pool2_tree64;
43
struct ultree *ul2tree_insert(struct ultree *root, unsigned long h, unsigned long l)
45
return __ul2tree_insert(root, h, l);
48
void *tree_delete(void *node) {
49
return __tree_delete(node);
52
struct task *_task_wakeup(struct task *t)
54
return __task_wakeup(t);
60
* Inserts a task into the wait queue at the position given by its expiration
64
struct task *task_queue(struct task *task)
66
if (unlikely(task->qlist.p != NULL)) {
67
DLIST_DEL(&task->qlist);
71
if (unlikely(task->wq != NULL)) {
72
tree_delete(task->wq);
76
if (unlikely(tv_iseternity(&task->expire))) {
78
DLIST_ADD(eternity_queue, &task->qlist);
82
task->wq = ul2tree_insert(&timer_wq, task->expire.tv_sec, task->expire.tv_usec);
83
DLIST_ADD(task->wq->data, &task->qlist);
89
* Extract all expired timers from the wait queue, and wakes up all
90
* associated tasks. Returns the date of next event (or eternity).
93
void wake_expired_tasks(struct timeval *next)
99
#ifdef WAKE_HINT_CHECK_FIRST
101
* Hint: tasks are *rarely* expired. So we can try to optimize
102
* by not scanning the tree at all in most cases. However, this
103
* code costs 160 more bytes which do not look much useful because
104
* the performance win is not obvious.
107
if (likely(timer_wq.data != NULL)) {
108
task = LIST_ELEM(timer_wq.data, struct task *, qlist);
109
if (likely(tv_isgt(&task->expire, &now))) {
110
*next = task->expire;
114
/* OK we lose. Let's scan the tree then. */
117
tree64_foreach(&timer_wq, data, stack, slen) {
118
task = LIST_ELEM(data, struct task *, qlist);
120
if (tv_isgt(&task->expire, &now)) {
121
*next = task->expire;
126
* OK, all tasks linked to this node will be unlinked, as well
127
* as the node itself, so we do not need to care about correct
130
foreach_dlist_item(task, data, struct task *, qlist) {
131
DLIST_DEL(&task->qlist);
133
DLIST_ADD(run_queue, &task->qlist);
134
task->state = TASK_RUNNING;
142
* This does 4 things :
143
* - wake up all expired tasks
144
* - call all runnable tasks
145
* - call maintain_proxies() to enable/disable the listeners
146
* - return the date of next event in <next> or eternity.
149
void process_runnable_tasks(struct timeval *next)
155
wake_expired_tasks(next);
156
/* process each task in the run queue now. Each task may be deleted
157
* since we only use the run queue's head. Note that any task can be
158
* woken up by any other task and it will be processed immediately
159
* after as it will be queued on the run queue's head !
163
foreach_dlist_item(t, queue, struct task *, qlist) {
164
DLIST_DEL(&t->qlist);
167
t->state = TASK_IDLE;
168
t->process(t, &temp);
169
tv_bound(next, &temp);
172
/* maintain all proxies in a consistent state. This should quickly
173
* become a task because it becomes expensive when there are huge
174
* numbers of proxies. */
175
maintain_proxies(&temp);
176
tv_bound(next, &temp);
252
return pool2_task != NULL;
added
removed
src/task.c
