Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 1 | /* |
| 2 | * Task management functions. |
| 3 | * |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 4 | * Copyright 2000-2009 Willy Tarreau <w@1wt.eu> |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 5 | * |
| 6 | * This program is free software; you can redistribute it and/or |
| 7 | * modify it under the terms of the GNU General Public License |
| 8 | * as published by the Free Software Foundation; either version |
| 9 | * 2 of the License, or (at your option) any later version. |
| 10 | * |
| 11 | */ |
| 12 | |
Willy Tarreau | 2dd0d47 | 2006-06-29 17:53:05 +0200 | [diff] [blame] | 13 | #include <common/config.h> |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 14 | #include <common/eb32tree.h> |
Willy Tarreau | c6ca1a0 | 2007-05-13 19:43:47 +0200 | [diff] [blame] | 15 | #include <common/memory.h> |
Willy Tarreau | 2dd0d47 | 2006-06-29 17:53:05 +0200 | [diff] [blame] | 16 | #include <common/mini-clist.h> |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 17 | #include <common/standard.h> |
Willy Tarreau | a6a6a93 | 2007-04-28 22:40:08 +0200 | [diff] [blame] | 18 | #include <common/time.h> |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 19 | |
Willy Tarreau | d825eef | 2007-05-12 22:35:00 +0200 | [diff] [blame] | 20 | #include <proto/proxy.h> |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 21 | #include <proto/task.h> |
| 22 | |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 23 | struct pool_head *pool2_task; |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 24 | |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 25 | unsigned int run_queue = 0; |
Willy Tarreau | 91e9993 | 2008-06-30 07:51:00 +0200 | [diff] [blame] | 26 | unsigned int niced_tasks = 0; /* number of niced tasks in the run queue */ |
Willy Tarreau | ce44f12 | 2008-07-05 18:16:19 +0200 | [diff] [blame] | 27 | struct task *last_timer = NULL; /* optimization: last queued timer */ |
Willy Tarreau | 964c936 | 2007-01-07 00:38:00 +0100 | [diff] [blame] | 28 | |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 29 | /* Principle of the wait queue. |
| 30 | * |
| 31 | * We want to be able to tell whether an expiration date is before of after the |
| 32 | * current time <now>. We KNOW that expiration dates are never too far apart, |
| 33 | * because they are already computed by adding integer numbers of milliseconds |
| 34 | * to the current date. |
| 35 | * We also know that almost all dates will be in the future, and that a very |
| 36 | * small part of them will be in the past, they are the ones which have expired |
| 37 | * since last time we checked them. |
| 38 | * |
| 39 | * The current implementation uses a wrapping time cut into 3 ranges : |
| 40 | * - previous : those ones are expired by definition |
| 41 | * - current : some are expired, some are not |
| 42 | * - next : none are expired |
| 43 | * |
| 44 | * We use the higher two bits of the timers expressed in ticks (milliseconds) |
| 45 | * to determine which range a timer is in, compared to <now> : |
| 46 | * |
| 47 | * now previous current next0 next1 |
| 48 | * [31:30] [31:30] [31:30] [31:30] [31:30] |
| 49 | * 00 11 00 01 10 |
| 50 | * 01 00 01 10 11 |
| 51 | * 10 01 10 11 00 |
| 52 | * 11 10 11 00 01 |
| 53 | * |
| 54 | * By definition, <current> is the range containing <now> as well as all timers |
| 55 | * which have the same 2 high bits as <now>, <previous> is the range just |
| 56 | * before, which contains all timers whose high bits equal those of <now> minus |
| 57 | * 1. Last, <next> is composed of the two remaining ranges. |
| 58 | * |
| 59 | * For ease of implementation, the timers will then be stored into 4 queues 0-3 |
| 60 | * determined by the 2 higher bits of the timer. The expiration algorithm is |
| 61 | * very simple : |
| 62 | * - expire everything in <previous>=queue[((now>>30)-1)&3] |
| 63 | * - expire from <current>=queue[(now>>30)&3] everything where timer >= now |
| 64 | * |
| 65 | * With this algorithm, it's possible to queue tasks meant to expire 24.8 days |
| 66 | * in the future, and still be able to detect events remaining unprocessed for |
| 67 | * the last 12.4 days! Note that the principle might be extended to any number |
| 68 | * of higher bits as long as there is only one range for expired tasks. For |
| 69 | * instance, using the 8 higher bits to index the range, we would have one past |
| 70 | * range of 4.6 hours (24 bits in ms), and 254 ranges in the future totalizing |
| 71 | * 49.3 days. This would eat more memory for a very little added benefit. |
| 72 | * |
| 73 | * Also, in order to maintain the ability to perform time comparisons, it is |
| 74 | * recommended to avoid using the <next1> range above, as values in this range |
| 75 | * may not easily be compared to <now> outside of these functions as it is the |
| 76 | * opposite of the <current> range, and <timer>-<now> may randomly be positive |
| 77 | * or negative. That means we're left with +/- 12 days timers. |
| 78 | * |
| 79 | * To keep timers ordered, we use 4 ebtrees [0..3]. To keep computation low, we |
| 80 | * may use (seconds*1024)+milliseconds, which preserves ordering eventhough we |
| 81 | * can't do real computations on it. Future evolutions could make use of 1024th |
| 82 | * of seconds instead of milliseconds, with the special value 0 avoided (and |
| 83 | * replaced with 1), so that zero indicates the timer is not set. |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 84 | */ |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 85 | |
| 86 | #define TIMER_TICK_BITS 32 |
| 87 | #define TIMER_TREE_BITS 2 |
| 88 | #define TIMER_TREES (1 << TIMER_TREE_BITS) |
| 89 | #define TIMER_TREE_SHIFT (TIMER_TICK_BITS - TIMER_TREE_BITS) |
| 90 | #define TIMER_TREE_MASK (TIMER_TREES - 1) |
| 91 | #define TIMER_TICK_MASK ((1U << (TIMER_TICK_BITS-1)) * 2 - 1) |
| 92 | #define TIMER_SIGN_BIT (1 << (TIMER_TICK_BITS - 1)) |
Willy Tarreau | c6ca1a0 | 2007-05-13 19:43:47 +0200 | [diff] [blame] | 93 | |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 94 | static struct eb_root timers[TIMER_TREES]; /* trees with MSB 00, 01, 10 and 11 */ |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 95 | static struct eb_root rqueue[TIMER_TREES]; /* trees constituting the run queue */ |
| 96 | static unsigned int rqueue_ticks; /* insertion count */ |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 97 | |
| 98 | /* returns an ordered key based on an expiration date. */ |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 99 | static inline unsigned int timeval_to_ticks(const struct timeval *t) |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 100 | { |
| 101 | unsigned int key; |
| 102 | |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 103 | key = ((unsigned int)t->tv_sec * 1000) + ((unsigned int)t->tv_usec / 1000); |
| 104 | key &= TIMER_TICK_MASK; |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 105 | return key; |
| 106 | } |
| 107 | |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 108 | /* returns a tree number based on a ticks value */ |
| 109 | static inline unsigned int ticks_to_tree(unsigned int ticks) |
| 110 | { |
| 111 | return (ticks >> TIMER_TREE_SHIFT) & TIMER_TREE_MASK; |
| 112 | } |
| 113 | |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 114 | /* returns a tree number based on an expiration date. */ |
| 115 | static inline unsigned int timeval_to_tree(const struct timeval *t) |
| 116 | { |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 117 | return ticks_to_tree(timeval_to_ticks(t)); |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 118 | } |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 119 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 120 | /* Puts the task <t> in run queue at a position depending on t->nice. <t> is |
| 121 | * returned. The nice value assigns boosts in 32th of the run queue size. A |
| 122 | * nice value of -1024 sets the task to -run_queue*32, while a nice value of |
| 123 | * 1024 sets the task to run_queue*32. The state flags are cleared, so the |
| 124 | * caller will have to set its flags after this call. |
| 125 | * The task must not already be in the run queue. If unsure, use the safer |
| 126 | * task_wakeup() function. |
Willy Tarreau | 91e9993 | 2008-06-30 07:51:00 +0200 | [diff] [blame] | 127 | */ |
Willy Tarreau | 4df8206 | 2008-08-29 15:26:14 +0200 | [diff] [blame] | 128 | struct task *__task_wakeup(struct task *t) |
Willy Tarreau | e33aece | 2007-04-30 13:15:14 +0200 | [diff] [blame] | 129 | { |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 130 | run_queue++; |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 131 | t->rq.key = ++rqueue_ticks; |
Willy Tarreau | 91e9993 | 2008-06-30 07:51:00 +0200 | [diff] [blame] | 132 | |
| 133 | if (likely(t->nice)) { |
| 134 | int offset; |
| 135 | |
| 136 | niced_tasks++; |
| 137 | if (likely(t->nice > 0)) |
| 138 | offset = (unsigned)((run_queue * (unsigned int)t->nice) / 32U); |
| 139 | else |
| 140 | offset = -(unsigned)((run_queue * (unsigned int)-t->nice) / 32U); |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 141 | t->rq.key += offset; |
Willy Tarreau | 91e9993 | 2008-06-30 07:51:00 +0200 | [diff] [blame] | 142 | } |
| 143 | |
Willy Tarreau | fdccded | 2008-08-29 18:19:04 +0200 | [diff] [blame] | 144 | /* clear state flags at the same time */ |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 145 | t->state &= ~TASK_WOKEN_ANY; |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 146 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 147 | eb32_insert(&rqueue[ticks_to_tree(t->rq.key)], &t->rq); |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 148 | return t; |
Willy Tarreau | e33aece | 2007-04-30 13:15:14 +0200 | [diff] [blame] | 149 | } |
Willy Tarreau | d825eef | 2007-05-12 22:35:00 +0200 | [diff] [blame] | 150 | |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 151 | /* |
| 152 | * task_queue() |
| 153 | * |
| 154 | * Inserts a task into the wait queue at the position given by its expiration |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 155 | * date. It does not matter if the task was already in the wait queue or not, |
| 156 | * and it may even help if its position has not changed because we'll be able |
| 157 | * to return without doing anything. Tasks queued with an eternity expiration |
| 158 | * are just unlinked from the WQ. Last, tasks must not be queued further than |
| 159 | * the end of the next tree, which is between <now_ms> and <now_ms> + |
| 160 | * TIMER_SIGN_BIT ms (now+12days..24days in 32bit). |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 161 | */ |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 162 | void task_queue(struct task *task) |
Willy Tarreau | 964c936 | 2007-01-07 00:38:00 +0100 | [diff] [blame] | 163 | { |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 164 | /* if the task is already in the wait queue, we may reuse its position |
| 165 | * or we will at least have to unlink it first. |
| 166 | */ |
| 167 | if (task_in_wq(task)) { |
| 168 | if (task->wq.key == task->expire) |
| 169 | return; |
| 170 | __task_unlink_wq(task); |
| 171 | } |
| 172 | |
| 173 | /* the task is not in the queue now */ |
Willy Tarreau | 0c303ee | 2008-07-07 00:09:58 +0200 | [diff] [blame] | 174 | if (unlikely(!task->expire)) |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 175 | return; |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 176 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 177 | task->wq.key = task->expire; |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 178 | #ifdef DEBUG_CHECK_INVALID_EXPIRATION_DATES |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 179 | if ((task->wq.key - now_ms) & TIMER_SIGN_BIT) |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 180 | /* we're queuing too far away or in the past (most likely) */ |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 181 | return; |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 182 | #endif |
Willy Tarreau | ce44f12 | 2008-07-05 18:16:19 +0200 | [diff] [blame] | 183 | |
| 184 | if (likely(last_timer && |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 185 | last_timer->wq.key == task->wq.key && |
| 186 | last_timer->wq.node.node_p && |
| 187 | last_timer->wq.node.bit == -1)) { |
Willy Tarreau | ce44f12 | 2008-07-05 18:16:19 +0200 | [diff] [blame] | 188 | /* Most often, last queued timer has the same expiration date, so |
| 189 | * if it's not queued at the root, let's queue a dup directly there. |
Willy Tarreau | 1b8ca66 | 2009-03-08 00:26:28 +0100 | [diff] [blame] | 190 | * Note that we can only use dups at the dup tree's root (bit==-1). |
Willy Tarreau | ce44f12 | 2008-07-05 18:16:19 +0200 | [diff] [blame] | 191 | */ |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 192 | eb_insert_dup(&last_timer->wq.node, &task->wq.node); |
| 193 | return; |
Willy Tarreau | ce44f12 | 2008-07-05 18:16:19 +0200 | [diff] [blame] | 194 | } |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 195 | eb32_insert(&timers[ticks_to_tree(task->wq.key)], &task->wq); |
| 196 | if (task->wq.node.bit == -1) |
Willy Tarreau | 1b8ca66 | 2009-03-08 00:26:28 +0100 | [diff] [blame] | 197 | last_timer = task; /* we only want dup a tree's root */ |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 198 | return; |
Willy Tarreau | 964c936 | 2007-01-07 00:38:00 +0100 | [diff] [blame] | 199 | } |
| 200 | |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 201 | /* |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 202 | * Extract all expired timers from the timer queue, and wakes up all |
Willy Tarreau | d825eef | 2007-05-12 22:35:00 +0200 | [diff] [blame] | 203 | * associated tasks. Returns the date of next event (or eternity). |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 204 | */ |
Willy Tarreau | 0c303ee | 2008-07-07 00:09:58 +0200 | [diff] [blame] | 205 | void wake_expired_tasks(int *next) |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 206 | { |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 207 | struct task *task; |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 208 | struct eb32_node *eb; |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 209 | unsigned int now_tree; |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 210 | unsigned int tree; |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 211 | |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 212 | /* In theory, we should : |
| 213 | * - wake all tasks from the <previous> tree |
| 214 | * - wake all expired tasks from the <current> tree |
| 215 | * - scan <next> trees for next expiration date if not found earlier. |
| 216 | * But we can do all this more easily : we scan all 3 trees before we |
| 217 | * wrap, and wake everything expired from there, then stop on the first |
| 218 | * non-expired entry. |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 219 | */ |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 220 | |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 221 | now_tree = ticks_to_tree(now_ms); |
| 222 | tree = (now_tree - 1) & TIMER_TREE_MASK; |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 223 | do { |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 224 | eb = eb32_first(&timers[tree]); |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 225 | while (eb) { |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 226 | task = eb32_entry(eb, struct task, wq); |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 227 | if ((now_ms - eb->key) & TIMER_SIGN_BIT) { |
| 228 | /* note that we don't need this check for the <previous> |
| 229 | * tree, but it's cheaper than duplicating the code. |
| 230 | */ |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 231 | *next = task->expire; |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 232 | return; |
| 233 | } |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 234 | |
Willy Tarreau | af754fc | 2008-06-29 19:25:52 +0200 | [diff] [blame] | 235 | /* detach the task from the queue and add the task to the run queue */ |
| 236 | eb = eb32_next(eb); |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 237 | __task_unlink_wq(task); |
| 238 | task_wakeup(task, TASK_WOKEN_TIMER); |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 239 | } |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 240 | tree = (tree + 1) & TIMER_TREE_MASK; |
| 241 | } while (((tree - now_tree) & TIMER_TREE_MASK) < TIMER_TREES/2); |
Willy Tarreau | 9789f7b | 2008-06-24 08:17:16 +0200 | [diff] [blame] | 242 | |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 243 | /* We have found no task to expire in any tree */ |
Willy Tarreau | 0c303ee | 2008-07-07 00:09:58 +0200 | [diff] [blame] | 244 | *next = TICK_ETERNITY; |
Willy Tarreau | 28c41a4 | 2008-06-29 17:00:59 +0200 | [diff] [blame] | 245 | return; |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 246 | } |
| 247 | |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 248 | /* The run queue is chronologically sorted in a tree. An insertion counter is |
| 249 | * used to assign a position to each task. This counter may be combined with |
| 250 | * other variables (eg: nice value) to set the final position in the tree. The |
| 251 | * counter may wrap without a problem, of course. We then limit the number of |
Willy Tarreau | 91e9993 | 2008-06-30 07:51:00 +0200 | [diff] [blame] | 252 | * tasks processed at once to 1/4 of the number of tasks in the queue, and to |
| 253 | * 200 max in any case, so that general latency remains low and so that task |
| 254 | * positions have a chance to be considered. It also reduces the number of |
| 255 | * trees to be evaluated when no task remains. |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 256 | * |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 257 | * Just like with timers, we start with tree[(current - 1)], which holds past |
| 258 | * values, and stop when we reach the middle of the list. In practise, we visit |
| 259 | * 3 out of 4 trees. |
| 260 | * |
| 261 | * The function adjusts <next> if a new event is closer. |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 262 | */ |
Willy Tarreau | 0c303ee | 2008-07-07 00:09:58 +0200 | [diff] [blame] | 263 | void process_runnable_tasks(int *next) |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 264 | { |
Willy Tarreau | 0c303ee | 2008-07-07 00:09:58 +0200 | [diff] [blame] | 265 | int temp; |
Willy Tarreau | 964c936 | 2007-01-07 00:38:00 +0100 | [diff] [blame] | 266 | struct task *t; |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 267 | struct eb32_node *eb; |
| 268 | unsigned int tree, stop; |
| 269 | unsigned int max_processed; |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 270 | |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 271 | if (!run_queue) |
| 272 | return; |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 273 | |
Willy Tarreau | 91e9993 | 2008-06-30 07:51:00 +0200 | [diff] [blame] | 274 | max_processed = run_queue; |
| 275 | if (max_processed > 200) |
| 276 | max_processed = 200; |
| 277 | |
| 278 | if (likely(niced_tasks)) |
| 279 | max_processed /= 4; |
Willy Tarreau | 96bcfd7 | 2007-04-29 10:41:56 +0200 | [diff] [blame] | 280 | |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 281 | tree = ticks_to_tree(rqueue_ticks); |
| 282 | stop = (tree + TIMER_TREES / 2) & TIMER_TREE_MASK; |
| 283 | tree = (tree - 1) & TIMER_TREE_MASK; |
Willy Tarreau | 964c936 | 2007-01-07 00:38:00 +0100 | [diff] [blame] | 284 | |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 285 | do { |
| 286 | eb = eb32_first(&rqueue[tree]); |
| 287 | while (eb) { |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 288 | t = eb32_entry(eb, struct task, rq); |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 289 | |
| 290 | /* detach the task from the queue and add the task to the run queue */ |
| 291 | eb = eb32_next(eb); |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 292 | __task_unlink_rq(t); |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 293 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 294 | t->state |= TASK_RUNNING; |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 295 | t->process(t, &temp); |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 296 | t->state &= ~TASK_RUNNING; |
Willy Tarreau | 0c303ee | 2008-07-07 00:09:58 +0200 | [diff] [blame] | 297 | *next = tick_first(*next, temp); |
Willy Tarreau | 58b458d | 2008-06-29 22:40:23 +0200 | [diff] [blame] | 298 | |
| 299 | if (!--max_processed) |
| 300 | return; |
| 301 | } |
| 302 | tree = (tree + 1) & TIMER_TREE_MASK; |
| 303 | } while (tree != stop); |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 304 | } |
| 305 | |
Willy Tarreau | 4726f53 | 2009-03-07 17:25:21 +0100 | [diff] [blame^] | 306 | /* perform minimal intializations, report 0 in case of error, 1 if OK. */ |
| 307 | int init_task() |
| 308 | { |
| 309 | memset(&timers, 0, sizeof(timers)); |
| 310 | memset(&rqueue, 0, sizeof(rqueue)); |
| 311 | pool2_task = create_pool("task", sizeof(struct task), MEM_F_SHARED); |
| 312 | return pool2_task != NULL; |
| 313 | } |
| 314 | |
Willy Tarreau | baaee00 | 2006-06-26 02:48:02 +0200 | [diff] [blame] | 315 | /* |
| 316 | * Local variables: |
| 317 | * c-indent-level: 8 |
| 318 | * c-basic-offset: 8 |
| 319 | * End: |
| 320 | */ |