paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Quagga Work Queue Support. |
| 3 | * |
| 4 | * Copyright (C) 2005 Sun Microsystems, Inc. |
| 5 | * |
| 6 | * This file is part of GNU Zebra. |
| 7 | * |
| 8 | * Quagga is free software; you can redistribute it and/or modify it |
| 9 | * under the terms of the GNU General Public License as published by the |
| 10 | * Free Software Foundation; either version 2, or (at your option) any |
| 11 | * later version. |
| 12 | * |
| 13 | * Quagga is distributed in the hope that it will be useful, but |
| 14 | * WITHOUT ANY WARRANTY; without even the implied warranty of |
| 15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 16 | * General Public License for more details. |
| 17 | * |
| 18 | * You should have received a copy of the GNU General Public License |
| 19 | * along with Quagga; see the file COPYING. If not, write to the Free |
| 20 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA |
| 21 | * 02111-1307, USA. |
| 22 | */ |
| 23 | |
| 24 | #include <lib/zebra.h> |
| 25 | #include "thread.h" |
| 26 | #include "memory.h" |
| 27 | #include "workqueue.h" |
| 28 | #include "linklist.h" |
| 29 | #include "command.h" |
| 30 | #include "log.h" |
| 31 | |
| 32 | /* master list of work_queues */ |
| 33 | static struct list work_queues; |
| 34 | |
| 35 | #define WORK_QUEUE_MIN_GRANULARITY 1 |
| 36 | |
| 37 | static struct work_queue_item * |
| 38 | work_queue_item_new (struct work_queue *wq) |
| 39 | { |
| 40 | struct work_queue_item *item; |
| 41 | assert (wq); |
| 42 | |
| 43 | item = XCALLOC (MTYPE_WORK_QUEUE_ITEM, |
| 44 | sizeof (struct work_queue_item)); |
| 45 | |
| 46 | return item; |
| 47 | } |
| 48 | |
| 49 | static void |
| 50 | work_queue_item_free (struct work_queue_item *item) |
| 51 | { |
| 52 | XFREE (MTYPE_WORK_QUEUE_ITEM, item); |
| 53 | return; |
| 54 | } |
| 55 | |
| 56 | /* create new work queue */ |
| 57 | struct work_queue * |
| 58 | work_queue_new (struct thread_master *m, const char *queue_name) |
| 59 | { |
| 60 | struct work_queue *new; |
| 61 | |
| 62 | new = XCALLOC (MTYPE_WORK_QUEUE, sizeof (struct work_queue)); |
| 63 | |
| 64 | if (new == NULL) |
| 65 | return new; |
| 66 | |
| 67 | new->name = XSTRDUP (MTYPE_WORK_QUEUE_NAME, queue_name); |
| 68 | new->master = m; |
Denis Ovsienko | 6ce80bd | 2007-11-12 14:55:01 +0000 | [diff] [blame] | 69 | SET_FLAG (new->flags, WQ_UNPLUGGED); |
| 70 | UNSET_FLAG (new->flags, WQ_AIM_HEAD); |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 71 | |
| 72 | if ( (new->items = list_new ()) == NULL) |
| 73 | { |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 74 | XFREE (MTYPE_WORK_QUEUE_NAME, new->name); |
| 75 | XFREE (MTYPE_WORK_QUEUE, new); |
| 76 | |
| 77 | return NULL; |
| 78 | } |
| 79 | |
| 80 | new->items->del = (void (*)(void *)) work_queue_item_free; |
| 81 | |
| 82 | listnode_add (&work_queues, new); |
| 83 | |
| 84 | new->cycles.granularity = WORK_QUEUE_MIN_GRANULARITY; |
paul | 190880d | 2005-11-14 12:07:47 +0000 | [diff] [blame] | 85 | |
| 86 | /* Default values, can be overriden by caller */ |
paul | 190880d | 2005-11-14 12:07:47 +0000 | [diff] [blame] | 87 | new->spec.hold = WORK_QUEUE_DEFAULT_HOLD; |
paul | 190880d | 2005-11-14 12:07:47 +0000 | [diff] [blame] | 88 | |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 89 | return new; |
| 90 | } |
| 91 | |
| 92 | void |
| 93 | work_queue_free (struct work_queue *wq) |
| 94 | { |
| 95 | /* list_delete frees items via callback */ |
| 96 | list_delete (wq->items); |
| 97 | listnode_delete (&work_queues, wq); |
| 98 | |
| 99 | XFREE (MTYPE_WORK_QUEUE_NAME, wq->name); |
| 100 | XFREE (MTYPE_WORK_QUEUE, wq); |
| 101 | return; |
| 102 | } |
| 103 | |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 104 | static inline int |
| 105 | work_queue_schedule (struct work_queue *wq, unsigned int delay) |
| 106 | { |
| 107 | /* if appropriate, schedule work queue thread */ |
Denis Ovsienko | 6ce80bd | 2007-11-12 14:55:01 +0000 | [diff] [blame] | 108 | if ( CHECK_FLAG (wq->flags, WQ_UNPLUGGED) |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 109 | && (wq->thread == NULL) |
| 110 | && (listcount (wq->items) > 0) ) |
| 111 | { |
| 112 | wq->thread = thread_add_background (wq->master, work_queue_run, |
| 113 | wq, delay); |
| 114 | return 1; |
| 115 | } |
| 116 | else |
| 117 | return 0; |
| 118 | } |
| 119 | |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 120 | void |
| 121 | work_queue_add (struct work_queue *wq, void *data) |
| 122 | { |
| 123 | struct work_queue_item *item; |
| 124 | |
| 125 | assert (wq); |
| 126 | |
| 127 | if (!(item = work_queue_item_new (wq))) |
| 128 | { |
| 129 | zlog_err ("%s: unable to get new queue item", __func__); |
| 130 | return; |
| 131 | } |
| 132 | |
| 133 | item->data = data; |
Denis Ovsienko | 6ce80bd | 2007-11-12 14:55:01 +0000 | [diff] [blame] | 134 | if (CHECK_FLAG (wq->flags, WQ_AIM_HEAD)) |
| 135 | listnode_add_after (wq->items, NULL, item); |
| 136 | else |
| 137 | listnode_add (wq->items, item); |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 138 | |
paul | 306d889 | 2006-02-02 17:50:19 +0000 | [diff] [blame] | 139 | work_queue_schedule (wq, wq->spec.hold); |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 140 | |
| 141 | return; |
| 142 | } |
| 143 | |
| 144 | static void |
| 145 | work_queue_item_remove (struct work_queue *wq, struct listnode *ln) |
| 146 | { |
| 147 | struct work_queue_item *item = listgetdata (ln); |
| 148 | |
| 149 | assert (item && item->data); |
| 150 | |
| 151 | /* call private data deletion callback if needed */ |
| 152 | if (wq->spec.del_item_data) |
paul | 889e931 | 2005-11-14 14:46:35 +0000 | [diff] [blame] | 153 | wq->spec.del_item_data (wq, item->data); |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 154 | |
| 155 | list_delete_node (wq->items, ln); |
| 156 | work_queue_item_free (item); |
| 157 | |
| 158 | return; |
| 159 | } |
| 160 | |
| 161 | static void |
| 162 | work_queue_item_requeue (struct work_queue *wq, struct listnode *ln) |
| 163 | { |
| 164 | LISTNODE_DETACH (wq->items, ln); |
| 165 | LISTNODE_ATTACH (wq->items, ln); /* attach to end of list */ |
| 166 | } |
| 167 | |
| 168 | DEFUN(show_work_queues, |
| 169 | show_work_queues_cmd, |
| 170 | "show work-queues", |
| 171 | SHOW_STR |
| 172 | "Work Queue information\n") |
| 173 | { |
| 174 | struct listnode *node; |
| 175 | struct work_queue *wq; |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 176 | |
| 177 | vty_out (vty, |
paul | 306d889 | 2006-02-02 17:50:19 +0000 | [diff] [blame] | 178 | "%c %8s %5s %8s %21s%s", |
| 179 | ' ', "List","(ms) ","Q. Runs","Cycle Counts ", |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 180 | VTY_NEWLINE); |
| 181 | vty_out (vty, |
paul | 306d889 | 2006-02-02 17:50:19 +0000 | [diff] [blame] | 182 | "%c %8s %5s %8s %7s %6s %6s %s%s", |
| 183 | 'P', |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 184 | "Items", |
paul | 306d889 | 2006-02-02 17:50:19 +0000 | [diff] [blame] | 185 | "Hold", |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 186 | "Total", |
| 187 | "Best","Gran.","Avg.", |
| 188 | "Name", |
| 189 | VTY_NEWLINE); |
| 190 | |
| 191 | for (ALL_LIST_ELEMENTS_RO ((&work_queues), node, wq)) |
| 192 | { |
paul | 306d889 | 2006-02-02 17:50:19 +0000 | [diff] [blame] | 193 | vty_out (vty,"%c %8d %5d %8ld %7d %6d %6u %s%s", |
Denis Ovsienko | 6ce80bd | 2007-11-12 14:55:01 +0000 | [diff] [blame] | 194 | (CHECK_FLAG (wq->flags, WQ_UNPLUGGED) ? ' ' : 'P'), |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 195 | listcount (wq->items), |
paul | 306d889 | 2006-02-02 17:50:19 +0000 | [diff] [blame] | 196 | wq->spec.hold, |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 197 | wq->runs, |
paul | 8436968 | 2005-04-27 12:39:27 +0000 | [diff] [blame] | 198 | wq->cycles.best, wq->cycles.granularity, |
| 199 | (wq->runs) ? |
| 200 | (unsigned int) (wq->cycles.total / wq->runs) : 0, |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 201 | wq->name, |
| 202 | VTY_NEWLINE); |
| 203 | } |
| 204 | |
| 205 | return CMD_SUCCESS; |
| 206 | } |
| 207 | |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 208 | /* 'plug' a queue: Stop it from being scheduled, |
| 209 | * ie: prevent the queue from draining. |
| 210 | */ |
| 211 | void |
| 212 | work_queue_plug (struct work_queue *wq) |
| 213 | { |
| 214 | if (wq->thread) |
| 215 | thread_cancel (wq->thread); |
| 216 | |
| 217 | wq->thread = NULL; |
| 218 | |
Denis Ovsienko | 6ce80bd | 2007-11-12 14:55:01 +0000 | [diff] [blame] | 219 | UNSET_FLAG (wq->flags, WQ_UNPLUGGED); |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 220 | } |
| 221 | |
| 222 | /* unplug queue, schedule it again, if appropriate |
| 223 | * Ie: Allow the queue to be drained again |
| 224 | */ |
| 225 | void |
| 226 | work_queue_unplug (struct work_queue *wq) |
| 227 | { |
Denis Ovsienko | 6ce80bd | 2007-11-12 14:55:01 +0000 | [diff] [blame] | 228 | SET_FLAG (wq->flags, WQ_UNPLUGGED); |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 229 | |
| 230 | /* if thread isnt already waiting, add one */ |
paul | 306d889 | 2006-02-02 17:50:19 +0000 | [diff] [blame] | 231 | work_queue_schedule (wq, wq->spec.hold); |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 232 | } |
| 233 | |
Denis Ovsienko | 6ce80bd | 2007-11-12 14:55:01 +0000 | [diff] [blame] | 234 | void |
| 235 | work_queue_aim_head (struct work_queue *wq, const unsigned aim_head) |
| 236 | { |
| 237 | if (aim_head) |
| 238 | SET_FLAG (wq->flags, WQ_AIM_HEAD); |
| 239 | else |
| 240 | UNSET_FLAG (wq->flags, WQ_AIM_HEAD); |
| 241 | } |
| 242 | |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 243 | /* timer thread to process a work queue |
| 244 | * will reschedule itself if required, |
| 245 | * otherwise work_queue_item_add |
| 246 | */ |
| 247 | int |
| 248 | work_queue_run (struct thread *thread) |
| 249 | { |
| 250 | struct work_queue *wq; |
| 251 | struct work_queue_item *item; |
| 252 | wq_item_status ret; |
| 253 | unsigned int cycles = 0; |
| 254 | struct listnode *node, *nnode; |
| 255 | char yielded = 0; |
| 256 | |
| 257 | wq = THREAD_ARG (thread); |
| 258 | wq->thread = NULL; |
| 259 | |
| 260 | assert (wq && wq->items); |
| 261 | |
| 262 | /* calculate cycle granularity: |
| 263 | * list iteration == 1 cycle |
| 264 | * granularity == # cycles between checks whether we should yield. |
| 265 | * |
| 266 | * granularity should be > 0, and can increase slowly after each run to |
| 267 | * provide some hysteris, but not past cycles.best or 2*cycles. |
| 268 | * |
| 269 | * Best: starts low, can only increase |
| 270 | * |
Paul Jakma | 213d8da | 2006-03-30 14:45:47 +0000 | [diff] [blame] | 271 | * Granularity: starts at WORK_QUEUE_MIN_GRANULARITY, can be decreased |
| 272 | * if we run to end of time slot, can increase otherwise |
| 273 | * by a small factor. |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 274 | * |
| 275 | * We could use just the average and save some work, however we want to be |
| 276 | * able to adjust quickly to CPU pressure. Average wont shift much if |
| 277 | * daemon has been running a long time. |
| 278 | */ |
| 279 | if (wq->cycles.granularity == 0) |
| 280 | wq->cycles.granularity = WORK_QUEUE_MIN_GRANULARITY; |
| 281 | |
| 282 | for (ALL_LIST_ELEMENTS (wq->items, node, nnode, item)) |
| 283 | { |
| 284 | assert (item && item->data); |
| 285 | |
| 286 | /* dont run items which are past their allowed retries */ |
paul | 8436968 | 2005-04-27 12:39:27 +0000 | [diff] [blame] | 287 | if (item->ran > wq->spec.max_retries) |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 288 | { |
| 289 | /* run error handler, if any */ |
| 290 | if (wq->spec.errorfunc) |
| 291 | wq->spec.errorfunc (wq, item->data); |
| 292 | work_queue_item_remove (wq, node); |
| 293 | continue; |
| 294 | } |
| 295 | |
| 296 | /* run and take care of items that want to be retried immediately */ |
| 297 | do |
| 298 | { |
paul | 889e931 | 2005-11-14 14:46:35 +0000 | [diff] [blame] | 299 | ret = wq->spec.workfunc (wq, item->data); |
paul | 8436968 | 2005-04-27 12:39:27 +0000 | [diff] [blame] | 300 | item->ran++; |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 301 | } |
| 302 | while ((ret == WQ_RETRY_NOW) |
paul | 8436968 | 2005-04-27 12:39:27 +0000 | [diff] [blame] | 303 | && (item->ran < wq->spec.max_retries)); |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 304 | |
| 305 | switch (ret) |
| 306 | { |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 307 | case WQ_QUEUE_BLOCKED: |
| 308 | { |
| 309 | /* decrement item->ran again, cause this isn't an item |
| 310 | * specific error, and fall through to WQ_RETRY_LATER |
| 311 | */ |
| 312 | item->ran--; |
| 313 | } |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 314 | case WQ_RETRY_LATER: |
| 315 | { |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 316 | goto stats; |
| 317 | } |
| 318 | case WQ_REQUEUE: |
| 319 | { |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 320 | work_queue_item_requeue (wq, node); |
| 321 | break; |
| 322 | } |
| 323 | case WQ_RETRY_NOW: |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 324 | /* a RETRY_NOW that gets here has exceeded max_tries, same as ERROR */ |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 325 | case WQ_ERROR: |
| 326 | { |
| 327 | if (wq->spec.errorfunc) |
| 328 | wq->spec.errorfunc (wq, item); |
| 329 | } |
| 330 | /* fall through here is deliberate */ |
| 331 | case WQ_SUCCESS: |
| 332 | default: |
| 333 | { |
| 334 | work_queue_item_remove (wq, node); |
| 335 | break; |
| 336 | } |
| 337 | } |
| 338 | |
| 339 | /* completed cycle */ |
| 340 | cycles++; |
| 341 | |
| 342 | /* test if we should yield */ |
| 343 | if ( !(cycles % wq->cycles.granularity) |
| 344 | && thread_should_yield (thread)) |
| 345 | { |
| 346 | yielded = 1; |
| 347 | goto stats; |
| 348 | } |
| 349 | } |
| 350 | |
| 351 | stats: |
| 352 | |
| 353 | #define WQ_HYSTERIS_FACTOR 2 |
| 354 | |
| 355 | /* we yielded, check whether granularity should be reduced */ |
| 356 | if (yielded && (cycles < wq->cycles.granularity)) |
| 357 | { |
| 358 | wq->cycles.granularity = ((cycles > 0) ? cycles |
| 359 | : WORK_QUEUE_MIN_GRANULARITY); |
| 360 | } |
| 361 | |
paul | 8436968 | 2005-04-27 12:39:27 +0000 | [diff] [blame] | 362 | if (cycles >= (wq->cycles.granularity)) |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 363 | { |
| 364 | if (cycles > wq->cycles.best) |
| 365 | wq->cycles.best = cycles; |
| 366 | |
| 367 | /* along with yielded check, provides hysteris for granularity */ |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 368 | if (cycles > (wq->cycles.granularity * WQ_HYSTERIS_FACTOR * 2)) |
| 369 | wq->cycles.granularity *= WQ_HYSTERIS_FACTOR; /* quick ramp-up */ |
| 370 | else if (cycles > (wq->cycles.granularity * WQ_HYSTERIS_FACTOR)) |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 371 | wq->cycles.granularity += WQ_HYSTERIS_FACTOR; |
| 372 | } |
| 373 | #undef WQ_HYSTERIS_FACTOR |
| 374 | |
| 375 | wq->runs++; |
| 376 | wq->cycles.total += cycles; |
| 377 | |
| 378 | #if 0 |
| 379 | printf ("%s: cycles %d, new: best %d, worst %d\n", |
| 380 | __func__, cycles, wq->cycles.best, wq->cycles.granularity); |
| 381 | #endif |
| 382 | |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 383 | /* Is the queue done yet? If it is, call the completion callback. */ |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 384 | if (listcount (wq->items) > 0) |
paul | 306d889 | 2006-02-02 17:50:19 +0000 | [diff] [blame] | 385 | work_queue_schedule (wq, 0); |
| 386 | else if (wq->spec.completion_func) |
| 387 | wq->spec.completion_func (wq); |
paul | 269d74f | 2005-05-23 13:42:46 +0000 | [diff] [blame] | 388 | |
paul | 354d119 | 2005-04-25 16:26:42 +0000 | [diff] [blame] | 389 | return 0; |
| 390 | } |