blob: 8880b9e22ed01ae31ed1c9290940ecd94cb233a2 [file] [log] [blame]
paul354d1192005-04-25 16:26:42 +00001/*
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 */
33static struct list work_queues;
34
35#define WORK_QUEUE_MIN_GRANULARITY 1
36
37static struct work_queue_item *
38work_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
49static void
50work_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 */
57struct work_queue *
58work_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 Ovsienko6ce80bd2007-11-12 14:55:01 +000069 SET_FLAG (new->flags, WQ_UNPLUGGED);
70 UNSET_FLAG (new->flags, WQ_AIM_HEAD);
paul354d1192005-04-25 16:26:42 +000071
72 if ( (new->items = list_new ()) == NULL)
73 {
paul354d1192005-04-25 16:26:42 +000074 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;
paul190880d2005-11-14 12:07:47 +000085
86 /* Default values, can be overriden by caller */
paul190880d2005-11-14 12:07:47 +000087 new->spec.hold = WORK_QUEUE_DEFAULT_HOLD;
paul190880d2005-11-14 12:07:47 +000088
paul354d1192005-04-25 16:26:42 +000089 return new;
90}
91
92void
93work_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
paul269d74f2005-05-23 13:42:46 +0000104static inline int
105work_queue_schedule (struct work_queue *wq, unsigned int delay)
106{
107 /* if appropriate, schedule work queue thread */
Denis Ovsienko6ce80bd2007-11-12 14:55:01 +0000108 if ( CHECK_FLAG (wq->flags, WQ_UNPLUGGED)
paul269d74f2005-05-23 13:42:46 +0000109 && (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
paul354d1192005-04-25 16:26:42 +0000120void
121work_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 Ovsienko6ce80bd2007-11-12 14:55:01 +0000134 if (CHECK_FLAG (wq->flags, WQ_AIM_HEAD))
135 listnode_add_after (wq->items, NULL, item);
136 else
137 listnode_add (wq->items, item);
paul354d1192005-04-25 16:26:42 +0000138
paul306d8892006-02-02 17:50:19 +0000139 work_queue_schedule (wq, wq->spec.hold);
paul354d1192005-04-25 16:26:42 +0000140
141 return;
142}
143
144static void
145work_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)
paul889e9312005-11-14 14:46:35 +0000153 wq->spec.del_item_data (wq, item->data);
paul354d1192005-04-25 16:26:42 +0000154
155 list_delete_node (wq->items, ln);
156 work_queue_item_free (item);
157
158 return;
159}
160
161static void
162work_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
168DEFUN(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;
paul354d1192005-04-25 16:26:42 +0000176
177 vty_out (vty,
paul306d8892006-02-02 17:50:19 +0000178 "%c %8s %5s %8s %21s%s",
179 ' ', "List","(ms) ","Q. Runs","Cycle Counts ",
paul354d1192005-04-25 16:26:42 +0000180 VTY_NEWLINE);
181 vty_out (vty,
paul306d8892006-02-02 17:50:19 +0000182 "%c %8s %5s %8s %7s %6s %6s %s%s",
183 'P',
paul354d1192005-04-25 16:26:42 +0000184 "Items",
paul306d8892006-02-02 17:50:19 +0000185 "Hold",
paul354d1192005-04-25 16:26:42 +0000186 "Total",
187 "Best","Gran.","Avg.",
188 "Name",
189 VTY_NEWLINE);
190
191 for (ALL_LIST_ELEMENTS_RO ((&work_queues), node, wq))
192 {
paul306d8892006-02-02 17:50:19 +0000193 vty_out (vty,"%c %8d %5d %8ld %7d %6d %6u %s%s",
Denis Ovsienko6ce80bd2007-11-12 14:55:01 +0000194 (CHECK_FLAG (wq->flags, WQ_UNPLUGGED) ? ' ' : 'P'),
paul354d1192005-04-25 16:26:42 +0000195 listcount (wq->items),
paul306d8892006-02-02 17:50:19 +0000196 wq->spec.hold,
paul354d1192005-04-25 16:26:42 +0000197 wq->runs,
paul84369682005-04-27 12:39:27 +0000198 wq->cycles.best, wq->cycles.granularity,
199 (wq->runs) ?
200 (unsigned int) (wq->cycles.total / wq->runs) : 0,
paul354d1192005-04-25 16:26:42 +0000201 wq->name,
202 VTY_NEWLINE);
203 }
204
205 return CMD_SUCCESS;
206}
207
paul269d74f2005-05-23 13:42:46 +0000208/* 'plug' a queue: Stop it from being scheduled,
209 * ie: prevent the queue from draining.
210 */
211void
212work_queue_plug (struct work_queue *wq)
213{
214 if (wq->thread)
215 thread_cancel (wq->thread);
216
217 wq->thread = NULL;
218
Denis Ovsienko6ce80bd2007-11-12 14:55:01 +0000219 UNSET_FLAG (wq->flags, WQ_UNPLUGGED);
paul269d74f2005-05-23 13:42:46 +0000220}
221
222/* unplug queue, schedule it again, if appropriate
223 * Ie: Allow the queue to be drained again
224 */
225void
226work_queue_unplug (struct work_queue *wq)
227{
Denis Ovsienko6ce80bd2007-11-12 14:55:01 +0000228 SET_FLAG (wq->flags, WQ_UNPLUGGED);
paul269d74f2005-05-23 13:42:46 +0000229
230 /* if thread isnt already waiting, add one */
paul306d8892006-02-02 17:50:19 +0000231 work_queue_schedule (wq, wq->spec.hold);
paul269d74f2005-05-23 13:42:46 +0000232}
233
Denis Ovsienko6ce80bd2007-11-12 14:55:01 +0000234void
235work_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
paul354d1192005-04-25 16:26:42 +0000243/* timer thread to process a work queue
244 * will reschedule itself if required,
245 * otherwise work_queue_item_add
246 */
247int
248work_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 Jakma213d8da2006-03-30 14:45:47 +0000271 * 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.
paul354d1192005-04-25 16:26:42 +0000274 *
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 */
paul84369682005-04-27 12:39:27 +0000287 if (item->ran > wq->spec.max_retries)
paul354d1192005-04-25 16:26:42 +0000288 {
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 {
paul889e9312005-11-14 14:46:35 +0000299 ret = wq->spec.workfunc (wq, item->data);
paul84369682005-04-27 12:39:27 +0000300 item->ran++;
paul354d1192005-04-25 16:26:42 +0000301 }
302 while ((ret == WQ_RETRY_NOW)
paul84369682005-04-27 12:39:27 +0000303 && (item->ran < wq->spec.max_retries));
paul354d1192005-04-25 16:26:42 +0000304
305 switch (ret)
306 {
paul269d74f2005-05-23 13:42:46 +0000307 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 }
paul354d1192005-04-25 16:26:42 +0000314 case WQ_RETRY_LATER:
315 {
paul354d1192005-04-25 16:26:42 +0000316 goto stats;
317 }
318 case WQ_REQUEUE:
319 {
paul354d1192005-04-25 16:26:42 +0000320 work_queue_item_requeue (wq, node);
321 break;
322 }
323 case WQ_RETRY_NOW:
paul269d74f2005-05-23 13:42:46 +0000324 /* a RETRY_NOW that gets here has exceeded max_tries, same as ERROR */
paul354d1192005-04-25 16:26:42 +0000325 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
351stats:
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
paul84369682005-04-27 12:39:27 +0000362 if (cycles >= (wq->cycles.granularity))
paul354d1192005-04-25 16:26:42 +0000363 {
364 if (cycles > wq->cycles.best)
365 wq->cycles.best = cycles;
366
367 /* along with yielded check, provides hysteris for granularity */
paul269d74f2005-05-23 13:42:46 +0000368 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))
paul354d1192005-04-25 16:26:42 +0000371 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
paul269d74f2005-05-23 13:42:46 +0000383 /* Is the queue done yet? If it is, call the completion callback. */
paul354d1192005-04-25 16:26:42 +0000384 if (listcount (wq->items) > 0)
paul306d8892006-02-02 17:50:19 +0000385 work_queue_schedule (wq, 0);
386 else if (wq->spec.completion_func)
387 wq->spec.completion_func (wq);
paul269d74f2005-05-23 13:42:46 +0000388
paul354d1192005-04-25 16:26:42 +0000389 return 0;
390}