?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
No empty .Rs/.Re
[netbsd-mini2440.git] / sys / altq / altq_jobs.c
blobd51430a4096acf6e1eb7729801b5b693a53d87e9
1 /* $NetBSD: altq_jobs.c,v 1.4 2006/11/16 01:32:37 christos Exp $ */
2 /* $KAME: altq_jobs.c,v 1.11 2005/04/13 03:44:25 suz Exp $ */
3 /*
4 * Copyright (c) 2001, the Rector and Board of Visitors of the
5 * University of Virginia.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms,
9 * with or without modification, are permitted provided
10 * that the following conditions are met:
11 *
12 * Redistributions of source code must retain the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer.
15 *
16 * Redistributions in binary form must reproduce the above
17 * copyright notice, this list of conditions and the following
18 * disclaimer in the documentation and/or other materials provided
19 * with the distribution.
20 *
21 * Neither the name of the University of Virginia nor the names
22 * of its contributors may be used to endorse or promote products
23 * derived from this software without specific prior written
24 * permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
27 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
28 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
29 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
30 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
31 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
32 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
33 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
34 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
35 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
37 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
38 * THE POSSIBILITY OF SUCH DAMAGE.
39 */
40 /*
41 * JoBS - altq prototype implementation
42 *
43 * Author: Nicolas Christin <nicolas@cs.virginia.edu>
44 *
45 * JoBS algorithms originally devised and proposed by
46 * Nicolas Christin and Jorg Liebeherr.
47 * Grateful acknowledgments to Tarek Abdelzaher for his help and
48 * comments, and to Kenjiro Cho for some helpful advice.
49 * Contributed by the Multimedia Networks Group at the University
50 * of Virginia.
51 *
52 * Papers and additional info can be found at
53 * http://qosbox.cs.virginia.edu
54 *
55 */
56
57 /*
58 * JoBS queue
59 */
60
61 #include <sys/cdefs.h>
62 __KERNEL_RCSID(0, "$NetBSD: altq_jobs.c,v 1.4 2006/11/16 01:32:37 christos Exp $");
63
64 #ifdef _KERNEL_OPT
65 #include "opt_altq.h"
66 #include "opt_inet.h"
67 #endif
68
69 #ifdef ALTQ_JOBS /* jobs is enabled by ALTQ_JOBS option in opt_altq.h */
70
71 #include <sys/param.h>
72 #include <sys/malloc.h>
73 #include <sys/mbuf.h>
74 #include <sys/socket.h>
75 #include <sys/sockio.h>
76 #include <sys/systm.h>
77 #include <sys/proc.h>
78 #include <sys/errno.h>
79 #include <sys/kernel.h>
80 #include <sys/queue.h>
81 #include <sys/kauth.h>
82
83 #ifdef __FreeBSD__
84 #include <sys/limits.h>
85 #endif
86
87 #include <net/if.h>
88 #include <net/if_types.h>
89
90 #include <altq/altq.h>
91 #include <altq/altq_conf.h>
92 #include <altq/altq_jobs.h>
93
94 #ifdef ALTQ3_COMPAT
95 /*
96 * function prototypes
97 */
98 static struct jobs_if *jobs_attach(struct ifaltq *, u_int, u_int, u_int);
99 static int jobs_detach(struct jobs_if *);
100 static int jobs_clear_interface(struct jobs_if *);
101 static int jobs_request(struct ifaltq *, int, void *);
102 static void jobs_purge(struct jobs_if *);
103 static struct jobs_class *jobs_class_create(struct jobs_if *,
104 int, int64_t, int64_t, int64_t, int64_t, int64_t, int);
105 static int jobs_class_destroy(struct jobs_class *);
106 static int jobs_enqueue(struct ifaltq *, struct mbuf *, struct altq_pktattr *);
107 static struct mbuf *jobs_dequeue(struct ifaltq *, int);
108
109 static int jobs_addq(struct jobs_class *, struct mbuf *, struct jobs_if*);
110 static struct mbuf *jobs_getq(struct jobs_class *);
111 static struct mbuf *jobs_pollq(struct jobs_class *);
112 static void jobs_purgeq(struct jobs_class *);
113
114 static int jobscmd_if_attach(struct jobs_attach *);
115 static int jobscmd_if_detach(struct jobs_interface *);
116 static int jobscmd_add_class(struct jobs_add_class *);
117 static int jobscmd_delete_class(struct jobs_delete_class *);
118 static int jobscmd_modify_class(struct jobs_modify_class *);
119 static int jobscmd_add_filter(struct jobs_add_filter *);
120 static int jobscmd_delete_filter(struct jobs_delete_filter *);
121 static int jobscmd_class_stats(struct jobs_class_stats *);
122 static void get_class_stats(struct class_stats *, struct jobs_class *);
123 static struct jobs_class *clh_to_clp(struct jobs_if *, u_long);
124 static u_long clp_to_clh(struct jobs_class *);
125
126 static TSLIST *tslist_alloc(void);
127 static void tslist_destroy(struct jobs_class *);
128 static int tslist_enqueue(struct jobs_class *, u_int64_t);
129 static void tslist_dequeue(struct jobs_class *);
130 static void tslist_drop(struct jobs_class *);
131
132 static int enforce_wc(struct jobs_if *);
133 static int64_t* adjust_rates_rdc(struct jobs_if *);
134 static int64_t* assign_rate_drops_adc(struct jobs_if *);
135 static int64_t* update_error(struct jobs_if *);
136 static int min_rates_adc(struct jobs_if *);
137 static int64_t proj_delay(struct jobs_if *, int);
138 static int pick_dropped_rlc(struct jobs_if *);
139
140 altqdev_decl(jobs);
141
142 /* jif_list keeps all jobs_if's allocated. */
143 static struct jobs_if *jif_list = NULL;
144
145 typedef unsigned long long ull;
146
147 /* setup functions */
148
149 static struct jobs_if *
150 jobs_attach(struct ifaltq *ifq, u_int bandwidth, u_int qlimit, u_int separate)
151 {
152 struct jobs_if *jif;
153
154 jif = malloc(sizeof(struct jobs_if), M_DEVBUF, M_WAITOK|M_ZERO);
155 if (jif == NULL)
156 return (NULL);
157
158 jif->jif_bandwidth = bandwidth;
159 jif->jif_qlimit = qlimit;
160 jif->jif_separate = separate;
161 #ifdef ALTQ_DEBUG
162 printf("JoBS bandwidth = %d bps\n", (int)bandwidth);
163 printf("JoBS buffer size = %d pkts [%s]\n",
164 (int)qlimit, separate?"separate buffers":"shared buffer");
165 #endif
166 jif->jif_maxpri = -1;
167 jif->jif_ifq = ifq;
168
169 jif->wc_cycles_enqueue = 0;
170 jif->avg_cycles_enqueue = 0;
171 jif->avg_cycles2_enqueue = 0;
172 jif->bc_cycles_enqueue = INFINITY;
173 jif->wc_cycles_dequeue = 0;
174 jif->avg_cycles_dequeue = 0;
175 jif->avg_cycles2_dequeue = 0;
176 jif->bc_cycles_dequeue = INFINITY;
177 jif->total_enqueued = 0;
178 jif->total_dequeued = 0;
179
180 /* add this state to the jobs list */
181 jif->jif_next = jif_list;
182 jif_list = jif;
183
184 return (jif);
185 }
186
187 static int
188 jobs_detach(struct jobs_if *jif)
189 {
190 (void)jobs_clear_interface(jif);
191
192 /* remove this interface from the jif list */
193 if (jif_list == jif)
194 jif_list = jif->jif_next;
195 else {
196 struct jobs_if *p;
197
198 for (p = jif_list; p != NULL; p = p->jif_next)
199 if (p->jif_next == jif) {
200 p->jif_next = jif->jif_next;
201 break;
202 }
203 ASSERT(p != NULL);
204 }
205 free(jif, M_DEVBUF);
206 return (0);
207 }
208
209 /*
210 * bring the interface back to the initial state by discarding
211 * all the filters and classes.
212 */
213 static int
214 jobs_clear_interface(struct jobs_if *jif)
215 {
216 struct jobs_class *cl;
217 int pri;
218
219 /* free the filters for this interface */
220 acc_discard_filters(&jif->jif_classifier, NULL, 1);
221
222 /* clear out the classes */
223 for (pri = 0; pri <= jif->jif_maxpri; pri++)
224 if ((cl = jif->jif_classes[pri]) != NULL)
225 jobs_class_destroy(cl);
226
227 return (0);
228 }
229
230 static int
231 jobs_request(struct ifaltq *ifq, int req, void *arg)
232 {
233 struct jobs_if *jif = (struct jobs_if *)ifq->altq_disc;
234
235 switch (req) {
236 case ALTRQ_PURGE:
237 jobs_purge(jif);
238 break;
239 }
240 return (0);
241 }
242
243 /* discard all the queued packets on the interface */
244 static void
245 jobs_purge(struct jobs_if *jif)
246 {
247 struct jobs_class *cl;
248 int pri;
249
250 for (pri = 0; pri <= jif->jif_maxpri; pri++) {
251 if ((cl = jif->jif_classes[pri]) != NULL && !qempty(cl->cl_q))
252 jobs_purgeq(cl);
253 }
254 if (ALTQ_IS_ENABLED(jif->jif_ifq))
255 jif->jif_ifq->ifq_len = 0;
256 }
257
258 static struct jobs_class *
259 jobs_class_create(struct jobs_if *jif, int pri, int64_t adc, int64_t rdc,
260 int64_t alc, int64_t rlc, int64_t arc, int flags)
261 {
262 struct jobs_class *cl, *scan1, *scan2;
263 int s;
264 int class_exists1, class_exists2;
265 int i, j;
266 int64_t tmp[JOBS_MAXPRI];
267 u_int64_t now;
268
269 if ((cl = jif->jif_classes[pri]) != NULL) {
270 /* modify the class instead of creating a new one */
271 s = splnet();
272 if (!qempty(cl->cl_q))
273 jobs_purgeq(cl);
274 splx(s);
275 } else {
276 cl = malloc(sizeof(struct jobs_class), M_DEVBUF,
277 M_WAITOK|M_ZERO);
278 if (cl == NULL)
279 return (NULL);
280
281 cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF,
282 M_WAITOK|M_ZERO);
283 if (cl->cl_q == NULL)
284 goto err_ret;
285
286 cl->arv_tm = tslist_alloc();
287 if (cl->arv_tm == NULL)
288 goto err_ret;
289 }
290
291 jif->jif_classes[pri] = cl;
292
293 if (flags & JOCF_DEFAULTCLASS)
294 jif->jif_default = cl;
295
296 qtype(cl->cl_q) = Q_DROPTAIL;
297 qlen(cl->cl_q) = 0;
298 cl->service_rate = 0;
299 cl->min_rate_adc = 0;
300 cl->current_loss = 0;
301 cl->cl_period = 0;
302 PKTCNTR_RESET(&cl->cl_arrival);
303 PKTCNTR_RESET(&cl->cl_rin);
304 PKTCNTR_RESET(&cl->cl_rout);
305 PKTCNTR_RESET(&cl->cl_rout_th);
306 PKTCNTR_RESET(&cl->cl_dropcnt);
307 PKTCNTR_RESET(&cl->st_arrival);
308 PKTCNTR_RESET(&cl->st_rin);
309 PKTCNTR_RESET(&cl->st_rout);
310 PKTCNTR_RESET(&cl->st_dropcnt);
311 cl->st_service_rate = 0;
312 cl->cl_lastdel = 0;
313 cl->cl_avgdel = 0;
314 cl->adc_violations = 0;
315
316 if (adc == -1) {
317 cl->concerned_adc = 0;
318 adc = INFINITY;
319 } else
320 cl->concerned_adc = 1;
321
322 if (alc == -1) {
323 cl->concerned_alc = 0;
324 alc = INFINITY;
325 } else
326 cl->concerned_alc = 1;
327
328 if (rdc == -1) {
329 rdc = 0;
330 cl->concerned_rdc = 0;
331 } else
332 cl->concerned_rdc = 1;
333
334 if (rlc == -1) {
335 rlc = 0;
336 cl->concerned_rlc = 0;
337 } else
338 cl->concerned_rlc = 1;
339
340 if (arc == -1) {
341 arc = 0;
342 cl->concerned_arc = 0;
343 } else
344 cl->concerned_arc = 1;
345
346 cl->cl_rdc=rdc;
347
348 if (cl->concerned_adc) {
349 /* adc is given in us, convert it to clock ticks */
350 cl->cl_adc = (u_int64_t)(adc*machclk_freq/GRANULARITY);
351 } else
352 cl->cl_adc = adc;
353
354 if (cl->concerned_arc) {
355 /* arc is given in bps, convert it to internal unit */
356 cl->cl_arc = (u_int64_t)(bps_to_internal(arc));
357 } else
358 cl->cl_arc = arc;
359
360 cl->cl_rlc=rlc;
361 cl->cl_alc=alc;
362 cl->delay_prod_others = 0;
363 cl->loss_prod_others = 0;
364 cl->cl_flags = flags;
365 cl->cl_pri = pri;
366 if (pri > jif->jif_maxpri)
367 jif->jif_maxpri = pri;
368 cl->cl_jif = jif;
369 cl->cl_handle = (u_long)cl; /* just a pointer to this class */
370
371 /*
372 * update delay_prod_others and loss_prod_others
373 * in all classes if needed
374 */
375
376 if (cl->concerned_rdc) {
377 for (i = 0; i <= jif->jif_maxpri; i++) {
378 scan1 = jif->jif_classes[i];
379 class_exists1 = (scan1 != NULL);
380 if (class_exists1) {
381 tmp[i] = 1;
382 for (j = 0; j <= i-1; j++) {
383 scan2 = jif->jif_classes[j];
384 class_exists2 = (scan2 != NULL);
385 if (class_exists2
386 && scan2->concerned_rdc)
387 tmp[i] *= scan2->cl_rdc;
388 }
389 } else
390 tmp[i] = 0;
391 }
392
393 for (i = 0; i <= jif->jif_maxpri; i++) {
394 scan1 = jif->jif_classes[i];
395 class_exists1 = (scan1 != NULL);
396 if (class_exists1) {
397 scan1->delay_prod_others = 1;
398 for (j = 0; j <= jif->jif_maxpri; j++) {
399 scan2 = jif->jif_classes[j];
400 class_exists2 = (scan2 != NULL);
401 if (class_exists2 && j != i
402 && scan2->concerned_rdc)
403 scan1->delay_prod_others *= tmp[j];
404 }
405 }
406 }
407 }
408
409 if (cl->concerned_rlc) {
410 for (i = 0; i <= jif->jif_maxpri; i++) {
411 scan1 = jif->jif_classes[i];
412 class_exists1 = (scan1 != NULL);
413 if (class_exists1) {
414 tmp[i] = 1;
415 for (j = 0; j <= i-1; j++) {
416 scan2 = jif->jif_classes[j];
417 class_exists2 = (scan2 != NULL);
418 if (class_exists2
419 && scan2->concerned_rlc)
420 tmp[i] *= scan2->cl_rlc;
421 }
422 } else
423 tmp[i] = 0;
424 }
425
426 for (i = 0; i <= jif->jif_maxpri; i++) {
427 scan1 = jif->jif_classes[i];
428 class_exists1 = (scan1 != NULL);
429 if (class_exists1) {
430 scan1->loss_prod_others = 1;
431 for (j = 0; j <= jif->jif_maxpri; j++) {
432 scan2 = jif->jif_classes[j];
433 class_exists2 = (scan2 != NULL);
434 if (class_exists2 && j != i
435 && scan2->concerned_rlc)
436 scan1->loss_prod_others *= tmp[j];
437 }
438 }
439 }
440 }
441
442 now = read_machclk();
443 cl->idletime = now;
444 return (cl);
445
446 err_ret:
447 if (cl->cl_q != NULL)
448 free(cl->cl_q, M_DEVBUF);
449 if (cl->arv_tm != NULL)
450 free(cl->arv_tm, M_DEVBUF);
451
452 free(cl, M_DEVBUF);
453 return (NULL);
454 }
455
456 static int
457 jobs_class_destroy(struct jobs_class *cl)
458 {
459 struct jobs_if *jif;
460 int s, pri;
461
462 s = splnet();
463
464 /* delete filters referencing to this class */
465 acc_discard_filters(&cl->cl_jif->jif_classifier, cl, 0);
466
467 if (!qempty(cl->cl_q))
468 jobs_purgeq(cl);
469
470 jif = cl->cl_jif;
471 jif->jif_classes[cl->cl_pri] = NULL;
472 if (jif->jif_maxpri == cl->cl_pri) {
473 for (pri = cl->cl_pri; pri >= 0; pri--)
474 if (jif->jif_classes[pri] != NULL) {
475 jif->jif_maxpri = pri;
476 break;
477 }
478 if (pri < 0)
479 jif->jif_maxpri = -1;
480 }
481 splx(s);
482
483 tslist_destroy(cl);
484 free(cl->cl_q, M_DEVBUF);
485 free(cl, M_DEVBUF);
486 return (0);
487 }
488
489 /*
490 * jobs_enqueue is an enqueue function to be registered to
491 * (*altq_enqueue) in struct ifaltq.
492 */
493 static int
494 jobs_enqueue(struct ifaltq *ifq, struct mbuf *m, struct altq_pktattr *pktattr)
495 {
496 struct jobs_if *jif = (struct jobs_if *)ifq->altq_disc;
497 struct jobs_class *cl, *scan;
498 int len;
499 int return_flag;
500 int pri;
501 u_int64_t now;
502 u_int64_t old_arv;
503 int64_t* delta_rate;
504 u_int64_t tstamp1, tstamp2, cycles; /* used for benchmarking only */
505
506 jif->total_enqueued++;
507 now = read_machclk();
508 tstamp1 = now;
509
510 return_flag = 0;
511
512 /* proceed with packet enqueuing */
513
514 if (IFQ_IS_EMPTY(ifq)) {
515 for (pri=0; pri <= jif->jif_maxpri; pri++) {
516 scan = jif->jif_classes[pri];
517 if (scan != NULL) {
518 /*
519 * reset all quantities, except:
520 * average delay, number of violations
521 */
522 PKTCNTR_RESET(&scan->cl_rin);
523 PKTCNTR_RESET(&scan->cl_rout);
524 PKTCNTR_RESET(&scan->cl_rout_th);
525 PKTCNTR_RESET(&scan->cl_arrival);
526 PKTCNTR_RESET(&scan->cl_dropcnt);
527 scan->cl_lastdel = 0;
528 scan->current_loss = 0;
529 scan->service_rate = 0;
530 scan->idletime = now;
531 scan->cl_last_rate_update = now;
532 }
533 }
534 }
535
536 /* grab class set by classifier */
537 if (pktattr == NULL || (cl = pktattr->pattr_class) == NULL)
538 cl = jif->jif_default;
539
540 len = m_pktlen(m);
541 old_arv = cl->cl_arrival.bytes;
542 PKTCNTR_ADD(&cl->cl_arrival, (int)len);
543 PKTCNTR_ADD(&cl->cl_rin, (int)len);
544 PKTCNTR_ADD(&cl->st_arrival, (int)len);
545 PKTCNTR_ADD(&cl->st_rin, (int)len);
546
547 if (cl->cl_arrival.bytes < old_arv) {
548 /* deals w/ overflow */
549 for (pri=0; pri <= jif->jif_maxpri; pri++) {
550 scan = jif->jif_classes[pri];
551 if (scan != NULL) {
552 /*
553 * reset all quantities, except:
554 * average delay, number of violations
555 */
556 PKTCNTR_RESET(&scan->cl_rin);
557 PKTCNTR_RESET(&scan->cl_rout);
558 PKTCNTR_RESET(&scan->cl_rout_th);
559 PKTCNTR_RESET(&scan->cl_arrival);
560 PKTCNTR_RESET(&scan->cl_dropcnt);
561 scan->current_loss = 0;
562 scan->service_rate = 0;
563 scan->idletime = now;
564 scan->cl_last_rate_update = now;
565 }
566 }
567 PKTCNTR_ADD(&cl->cl_arrival, (int)len);
568 PKTCNTR_ADD(&cl->cl_rin, (int)len);
569 }
570
571 if (cl->cl_arrival.bytes > cl->cl_rin.bytes)
572 cl->current_loss =
573 ((cl->cl_arrival.bytes - cl->cl_rin.bytes) << SCALE_LOSS)
574 / cl->cl_arrival.bytes;
575 else
576 cl->current_loss = 0;
577
578 /* for MDRR: update theoretical value of the output curve */
579
580 for (pri=0; pri <= jif->jif_maxpri; pri++) {
581 scan = jif->jif_classes[pri];
582 if (scan != NULL) {
583 if (scan->cl_last_rate_update == scan->idletime
584 || scan->cl_last_rate_update == 0)
585 scan->cl_last_rate_update = now; /* initial case */
586 else
587 scan->cl_rout_th.bytes +=
588 delay_diff(now, scan->cl_last_rate_update)
589 * scan->service_rate;
590
591 /*
592 * we don't really care about packets here
593 * WARNING: rout_th is SCALED
594 * (b/c of the service rate)
595 * for precision, as opposed to rout.
596 */
597
598 scan->cl_last_rate_update = now;
599 }
600 }
601
602 if (jobs_addq(cl, m, jif) != 0)
603 return_flag = ENOBUFS; /* signals there's a buffer overflow */
604 else
605 IFQ_INC_LEN(ifq);
606
607 /* successfully queued. */
608
609 enforce_wc(jif);
610
611 if (!min_rates_adc(jif)) {
612 delta_rate = assign_rate_drops_adc(jif);
613 if (delta_rate != NULL) {
614 for (pri = 0; pri <= jif->jif_maxpri; pri++)
615 if ((cl = jif->jif_classes[pri]) != NULL &&
616 !qempty(cl->cl_q))
617 cl->service_rate += delta_rate[pri];
618 free(delta_rate, M_DEVBUF);
619 }
620 }
621
622 delta_rate = adjust_rates_rdc(jif);
623
624 if (delta_rate != NULL) {
625 for (pri = 0; pri <= jif->jif_maxpri; pri++)
626 if ((cl = jif->jif_classes[pri]) != NULL &&
627 !qempty(cl->cl_q))
628 cl->service_rate += delta_rate[pri];
629 free(delta_rate, M_DEVBUF);
630 }
631
632 tstamp2 = read_machclk();
633 cycles = delay_diff(tstamp2, tstamp1);
634 if (cycles > jif->wc_cycles_enqueue)
635 jif->wc_cycles_enqueue=cycles;
636 if (cycles < jif->bc_cycles_enqueue)
637 jif->bc_cycles_enqueue=cycles;
638
639 jif->avg_cycles_enqueue += cycles;
640 jif->avg_cycles2_enqueue += cycles * cycles;
641
642 return (return_flag);
643 }
644
645 /*
646 * jobs_dequeue is a dequeue function to be registered to
647 * (*altq_dequeue) in struct ifaltq.
648 *
649 * note: ALTDQ_POLL returns the next packet without removing the packet
650 * from the queue. ALTDQ_REMOVE is a normal dequeue operation.
651 * ALTDQ_REMOVE must return the same packet if called immediately
652 * after ALTDQ_POLL.
653 */
654
655 static struct mbuf *
656 jobs_dequeue(struct ifaltq *ifq, int op)
657 {
658 struct jobs_if *jif = (struct jobs_if *)ifq->altq_disc;
659 struct jobs_class *cl;
660 struct mbuf *m;
661 int pri;
662 int svc_class;
663 int64_t max_error;
664 int64_t error;
665 u_int64_t now;
666 u_int64_t tstamp1, tstamp2, cycles;
667
668 jif->total_dequeued++;
669
670 now = read_machclk();
671 tstamp1 = now;
672
673 if (IFQ_IS_EMPTY(ifq)) {
674 /* no packet in the queue */
675 for (pri=0; pri <= jif->jif_maxpri; pri++) {
676 cl = jif->jif_classes[pri];
677 if (cl != NULL)
678 cl->idletime = now;
679 }
680
681 tstamp2 = read_machclk();
682 cycles = delay_diff(tstamp2, tstamp1);
683 if (cycles > jif->wc_cycles_dequeue)
684 jif->wc_cycles_dequeue = cycles;
685 if (cycles < jif->bc_cycles_dequeue)
686 jif->bc_cycles_dequeue = cycles;
687
688 jif->avg_cycles_dequeue += cycles;
689 jif->avg_cycles2_dequeue += cycles * cycles;
690
691 return (NULL);
692 }
693
694 /*
695 * select the class whose actual tranmissions are the furthest
696 * from the promised transmissions
697 */
698
699 max_error = -1;
700 svc_class = -1;
701
702 for (pri=0; pri <= jif->jif_maxpri; pri++) {
703 if (((cl = jif->jif_classes[pri]) != NULL)
704 && !qempty(cl->cl_q)) {
705 error = (int64_t)cl->cl_rout_th.bytes
706 -(int64_t)scale_rate(cl->cl_rout.bytes);
707 if (max_error == -1) {
708 max_error = error;
709 svc_class = pri;
710 } else if (error > max_error) {
711 max_error = error;
712 svc_class = pri;
713 }
714 }
715 }
716
717 if (svc_class != -1)
718 cl = jif->jif_classes[svc_class];
719 else
720 cl = NULL;
721
722 if (op == ALTDQ_POLL) {
723 tstamp2 = read_machclk();
724 cycles = delay_diff(tstamp2, tstamp1);
725 if (cycles > jif->wc_cycles_dequeue)
726 jif->wc_cycles_dequeue = cycles;
727 if (cycles < jif->bc_cycles_dequeue)
728 jif->bc_cycles_dequeue = cycles;
729
730 jif->avg_cycles_dequeue += cycles;
731 jif->avg_cycles2_dequeue += cycles * cycles;
732
733 return (jobs_pollq(cl));
734 }
735
736 if (cl != NULL)
737 m = jobs_getq(cl);
738 else
739 m = NULL;
740
741 if (m != NULL) {
742 IFQ_DEC_LEN(ifq);
743 if (qempty(cl->cl_q))
744 cl->cl_period++;
745
746 cl->cl_lastdel = (u_int64_t)delay_diff(now,
747 tslist_first(cl->arv_tm)->timestamp);
748 if (cl->concerned_adc
749 && (int64_t)cl->cl_lastdel > cl->cl_adc)
750 cl->adc_violations++;
751 cl->cl_avgdel += ticks_to_secs(GRANULARITY*cl->cl_lastdel);
752
753 PKTCNTR_ADD(&cl->cl_rout, m_pktlen(m));
754 PKTCNTR_ADD(&cl->st_rout, m_pktlen(m));
755 }
756 if (cl != NULL)
757 tslist_dequeue(cl); /* dequeue the timestamp */
758
759 tstamp2 = read_machclk();
760 cycles = delay_diff(tstamp2, tstamp1);
761 if (cycles > jif->wc_cycles_dequeue)
762 jif->wc_cycles_dequeue = cycles;
763 if (cycles < jif->bc_cycles_dequeue)
764 jif->bc_cycles_dequeue = cycles;
765
766 jif->avg_cycles_dequeue += cycles;
767 jif->avg_cycles2_dequeue += cycles * cycles;
768
769 return (m);
770 }
771
772 static int
773 jobs_addq(struct jobs_class *cl, struct mbuf *m, struct jobs_if *jif)
774 {
775 int victim;
776 u_int64_t len;
777 u_int64_t now;
778 struct jobs_class* victim_class;
779
780 victim = -1;
781 victim_class = NULL;
782 len = 0;
783
784 now = read_machclk();
785
786 if (jif->jif_separate && qlen(cl->cl_q) >= jif->jif_qlimit) {
787 /*
788 * separate buffers: no guarantees on packet drops
789 * can be offered
790 * thus we drop the incoming packet
791 */
792 len = (u_int64_t)m_pktlen(m);
793 PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
794 PKTCNTR_SUB(&cl->cl_rin, (int)len);
795 PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
796 PKTCNTR_SUB(&cl->st_rin, (int)len);
797 cl->current_loss += (len << SCALE_LOSS)
798 /cl->cl_arrival.bytes;
799 m_freem(m);
800 return (-1);
801
802 } else if (!jif->jif_separate
803 && jif->jif_ifq->ifq_len >= jif->jif_qlimit) {
804 /* shared buffer: supports guarantees on losses */
805 if (!cl->concerned_rlc) {
806 if (!cl->concerned_alc) {
807 /*
808 * no ALC, no RLC on this class:
809 * drop the incoming packet
810 */
811 len = (u_int64_t)m_pktlen(m);
812 PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
813 PKTCNTR_SUB(&cl->cl_rin, (int)len);
814 PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
815 PKTCNTR_SUB(&cl->st_rin, (int)len);
816 cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes;
817 m_freem(m);
818 return (-1);
819 } else {
820 /*
821 * no RLC, but an ALC:
822 * drop the incoming packet if possible
823 */
824 len = (u_int64_t)m_pktlen(m);
825 if (cl->current_loss + (len << SCALE_LOSS)
826 / cl->cl_arrival.bytes <= cl->cl_alc) {
827 PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
828 PKTCNTR_SUB(&cl->cl_rin, (int)len);
829 PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
830 PKTCNTR_SUB(&cl->st_rin, (int)len);
831 cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes;
832 m_freem(m);
833 return (-1);
834 } else {
835 /*
836 * the ALC would be violated:
837 * pick another class
838 */
839 _addq(cl->cl_q, m);
840 tslist_enqueue(cl, now);
841
842 victim = pick_dropped_rlc(jif);
843
844 if (victim == -1) {
845 /*
846 * something went wrong
847 * let us discard
848 * the incoming packet,
849 * regardless of what
850 * may happen...
851 */
852 victim_class = cl;
853 } else
854 victim_class = jif->jif_classes[victim];
855
856 if (victim_class != NULL) {
857 /*
858 * test for safety
859 * purposes...
860 * it must be true
861 */
862 m = _getq_tail(victim_class->cl_q);
863 len = (u_int64_t)m_pktlen(m);
864 PKTCNTR_ADD(&victim_class->cl_dropcnt, (int)len);
865 PKTCNTR_SUB(&victim_class->cl_rin, (int)len);
866 PKTCNTR_ADD(&victim_class->st_dropcnt, (int)len);
867 PKTCNTR_SUB(&victim_class->st_rin, (int)len);
868 victim_class->current_loss += (len << SCALE_LOSS)/victim_class->cl_arrival.bytes;
869 m_freem(m); /* the packet is trashed here */
870 tslist_drop(victim_class); /* and its timestamp as well */
871 }
872 return (-1);
873 }
874 }
875 } else {
876 /*
877 * RLC on that class:
878 * pick class according to RLCs
879 */
880 _addq(cl->cl_q, m);
881 tslist_enqueue(cl, now);
882
883 victim = pick_dropped_rlc(jif);
884 if (victim == -1) {
885 /*
886 * something went wrong
887 * let us discard the incoming packet,
888 * regardless of what may happen...
889 */
890 victim_class = cl;
891 } else
892 victim_class = jif->jif_classes[victim];
893
894 if (victim_class != NULL) {
895 /*
896 * test for safety purposes...
897 * it must be true
898 */
899 m = _getq_tail(victim_class->cl_q);
900 len = (u_int64_t)m_pktlen(m);
901 PKTCNTR_ADD(&victim_class->cl_dropcnt, (int)len);
902 PKTCNTR_SUB(&victim_class->cl_rin, (int)len);
903 PKTCNTR_ADD(&victim_class->st_dropcnt, (int)len);
904 PKTCNTR_SUB(&victim_class->st_rin, (int)len);
905 victim_class->current_loss += (len << SCALE_LOSS)/victim_class->cl_arrival.bytes;
906 m_freem(m); /* the packet is trashed here */
907 tslist_drop(victim_class); /* and its timestamp as well */
908 }
909 return (-1);
910 }
911 }
912 /* else: no drop */
913
914 _addq(cl->cl_q, m);
915 tslist_enqueue(cl, now);
916
917 return (0);
918 }
919
920 static struct mbuf *
921 jobs_getq(struct jobs_class *cl)
922 {
923 return _getq(cl->cl_q);
924 }
925
926 static struct mbuf *
927 jobs_pollq(struct jobs_class *cl)
928 {
929 return qhead(cl->cl_q);
930 }
931
932 static void
933 jobs_purgeq(struct jobs_class *cl)
934 {
935 struct mbuf *m;
936
937 if (qempty(cl->cl_q))
938 return;
939
940 while ((m = _getq(cl->cl_q)) != NULL) {
941 PKTCNTR_ADD(&cl->cl_dropcnt, m_pktlen(m));
942 PKTCNTR_ADD(&cl->st_dropcnt, m_pktlen(m));
943 m_freem(m);
944 tslist_drop(cl);
945 }
946 ASSERT(qlen(cl->cl_q) == 0);
947 }
948
949 /*
950 * timestamp list support routines
951 *
952 * this implementation has been revamped and
953 * now uses a TAILQ structure.
954 * timestamp list holds class timestamps
955 * there is one timestamp list per class.
956 */
957 static TSLIST *
958 tslist_alloc(void)
959 {
960 TSLIST *list_init;
961
962 list_init = malloc(sizeof(TSLIST), M_DEVBUF, M_WAITOK);
963 TAILQ_INIT(list_init);
964 return (list_init);
965 }
966
967 static void
968 tslist_destroy(struct jobs_class *cl)
969 {
970 while (tslist_first(cl->arv_tm) != NULL)
971 tslist_dequeue(cl);
972
973 free(cl->arv_tm, M_DEVBUF);
974 }
975
976 static int
977 tslist_enqueue(struct jobs_class *cl, u_int64_t arv)
978 {
979 TSENTRY *pushed;
980 pushed = malloc(sizeof(TSENTRY), M_DEVBUF, M_WAITOK);
981 if (pushed == NULL)
982 return (0);
983
984 pushed->timestamp = arv;
985 TAILQ_INSERT_TAIL(cl->arv_tm, pushed, ts_list);
986 return (1);
987 }
988
989 static void
990 tslist_dequeue(struct jobs_class *cl)
991 {
992 TSENTRY *popped;
993 popped = tslist_first(cl->arv_tm);
994 if (popped != NULL) {
995 TAILQ_REMOVE(cl->arv_tm, popped, ts_list);
996 free(popped, M_DEVBUF);
997 }
998 return;
999 }
1000
1001 static void
1002 tslist_drop(struct jobs_class *cl)
1003 {
1004 TSENTRY *popped;
1005 popped = tslist_last(cl->arv_tm);
1006 if (popped != NULL) {
1007 TAILQ_REMOVE(cl->arv_tm, popped, ts_list);
1008 free(popped, M_DEVBUF);
1009 }
1010 return;
1011 }
1012
1013 /*
1014 * rate allocation support routines
1015 */
1016 /*
1017 * enforce_wc: enforce that backlogged classes have non-zero
1018 * service rate, and that non-backlogged classes have zero
1019 * service rate.
1020 */
1021
1022 static int
1023 enforce_wc(struct jobs_if *jif)
1024 {
1025 struct jobs_class *cl;
1026
1027 int64_t active_classes;
1028 int pri;
1029 int is_backlogged, class_exists, updated;
1030
1031 updated = 0;
1032 active_classes = 0;
1033
1034 for (pri = 0; pri <= jif->jif_maxpri; pri++) {
1035 cl = jif->jif_classes[pri];
1036 class_exists = (cl != NULL);
1037 is_backlogged = (class_exists && !qempty(cl->cl_q));
1038
1039 if (is_backlogged)
1040 active_classes++;
1041 if ((is_backlogged && cl->service_rate <= 0)
1042 ||(class_exists
1043 && !is_backlogged && cl->service_rate > 0))
1044 updated = 1;
1045 }
1046
1047 if (updated) {
1048 for (pri = 0; pri <= jif->jif_maxpri; pri++) {
1049 cl = jif->jif_classes[pri];
1050 class_exists = (cl != NULL);
1051 is_backlogged = (class_exists && !qempty(cl->cl_q));
1052
1053 if (class_exists && !is_backlogged)
1054 cl->service_rate = 0;
1055 else if (is_backlogged)
1056 cl->service_rate = (int64_t)(bps_to_internal((u_int64_t)jif->jif_bandwidth)/active_classes);
1057 }
1058 }
1059
1060 return (updated);
1061 }
1062
1063 /*
1064 * adjust_rates_rdc: compute the service rates adjustments
1065 * needed to realize the desired proportional delay differentiation.
1066 * essentially, the rate adjustement delta_rate = prop_control*error,
1067 * where error is the difference between the measured "weighted"
1068 * delay and the mean of the weighted delays. see paper for more
1069 * information.
1070 * prop_control has slightly changed since the INFOCOM paper,
1071 * this condition seems to provide better results.
1072 */
1073
1074 static int64_t *
1075 adjust_rates_rdc(struct jobs_if *jif)
1076 {
1077 int64_t *result;
1078 int64_t credit, available, lower_bound, upper_bound;
1079 int64_t bk;
1080 int i, j;
1081 int rdc_classes, active_classes;
1082 int class_exists, is_backlogged;
1083 struct jobs_class *cl;
1084 int64_t *error;
1085 int64_t prop_control;
1086 u_int64_t max_prod;
1087 u_int64_t min_share;
1088 u_int64_t max_avg_pkt_size;
1089
1090 /*
1091 * min_share is scaled
1092 * to avoid dealing with doubles
1093 */
1094 active_classes = 0;
1095 rdc_classes = 0;
1096 max_prod = 0;
1097 max_avg_pkt_size = 0;
1098
1099 upper_bound = (int64_t)jif->jif_bandwidth;
1100
1101 for (i = 0; i <= jif->jif_maxpri; i++) {
1102 cl = jif->jif_classes[i];
1103 class_exists = (cl != NULL);
1104 is_backlogged = (class_exists && !qempty(cl->cl_q));
1105 if (is_backlogged) {
1106 active_classes++;
1107 if (cl->concerned_rdc)
1108 rdc_classes++;
1109 else
1110 upper_bound -=
1111 internal_to_bps(cl->service_rate);
1112 }
1113 }
1114
1115 result = malloc((jif->jif_maxpri+1)*sizeof(int64_t),
1116 M_DEVBUF, M_WAITOK);
1117
1118 if (result == NULL)
1119 return NULL;
1120
1121 for (i = 0; i <= jif->jif_maxpri; i++)
1122 result[i] = 0;
1123
1124 if (upper_bound <= 0 || rdc_classes == 0)
1125 return result;
1126
1127 credit = 0;
1128 lower_bound = 0;
1129 min_share = ((u_int64_t)1 << SCALE_SHARE);
1130 bk = 0;
1131
1132 for (i = 0; i <= jif->jif_maxpri; i++) {
1133 cl = jif->jif_classes[i];
1134 class_exists = (cl != NULL);
1135 is_backlogged = (class_exists && !qempty(cl->cl_q));
1136 if (is_backlogged && cl->concerned_rdc)
1137 bk += cl->cl_rin.bytes;
1138 }
1139
1140 if (bk == 0)
1141 return (result);
1142
1143 for (i = 0; i <= jif->jif_maxpri; i++) {
1144 cl = jif->jif_classes[i];
1145 class_exists = (cl != NULL);
1146 is_backlogged = (class_exists && !qempty(cl->cl_q));
1147 if (is_backlogged
1148 && (cl->cl_rin.bytes << SCALE_SHARE)/bk < min_share)
1149 min_share = (cl->cl_rin.bytes << SCALE_SHARE)/bk;
1150 if (is_backlogged && cl->concerned_rdc
1151 && cl->delay_prod_others > max_prod)
1152 max_prod = cl->delay_prod_others;
1153
1154 if (is_backlogged && cl->concerned_rdc
1155 && cl->cl_rin.bytes > max_avg_pkt_size*cl->cl_rin.packets)
1156 max_avg_pkt_size = (u_int64_t)((u_int)cl->cl_rin.bytes/(u_int)cl->cl_rin.packets);
1157 }
1158
1159 error = update_error(jif);
1160 if (!error)
1161 return (NULL);
1162
1163 prop_control = (upper_bound*upper_bound*min_share)
1164 /(max_prod*(max_avg_pkt_size << 2));
1165
1166 prop_control = bps_to_internal(ticks_to_secs(prop_control)); /* in BT-1 */
1167
1168 credit = 0;
1169 for (i = 0; i <= jif->jif_maxpri; i++) {
1170 cl = jif->jif_classes[i];
1171 class_exists = (cl != NULL);
1172 is_backlogged = (class_exists && !qempty(cl->cl_q));
1173 if (is_backlogged && cl->concerned_rdc) {
1174 result[i] = -prop_control*error[i]; /* in BT-1 */
1175 result[i] >>= (SCALE_SHARE);
1176 }
1177 }
1178
1179 free(error, M_DEVBUF); /* we don't need these anymore */
1180
1181 /* saturation */
1182
1183 for (i = 0; i <= jif->jif_maxpri; i++) {
1184 cl = jif->jif_classes[i];
1185 class_exists = (cl != NULL);
1186 is_backlogged = (class_exists && !qempty(cl->cl_q));
1187
1188 if (is_backlogged && cl->concerned_rdc)
1189 lower_bound += cl->min_rate_adc;
1190 /*
1191 * note: if there's no ADC or ARC on cl,
1192 * this is equal to zero, which is fine
1193 */
1194 }
1195
1196 for (i = 0; i <= jif->jif_maxpri; i++) {
1197 cl = jif->jif_classes[i];
1198 class_exists = (cl != NULL);
1199 is_backlogged = (class_exists && !qempty(cl->cl_q));
1200
1201 if (is_backlogged && cl->concerned_rdc
1202 && result[i] + cl->service_rate > upper_bound) {
1203 for (j = 0; j <= jif->jif_maxpri; j++) {
1204 cl = jif->jif_classes[j];
1205 class_exists = (cl != NULL);
1206 is_backlogged = (class_exists
1207 && !qempty(cl->cl_q));
1208 if (is_backlogged && cl->concerned_rdc) {
1209 if (j == i)
1210 result[j] = upper_bound
1211 -cl->service_rate
1212 + cl->min_rate_adc
1213 - lower_bound;
1214 else
1215 result[j] =
1216 -cl->service_rate
1217 +cl->min_rate_adc;
1218 }
1219 }
1220 return result;
1221 }
1222
1223 cl = jif->jif_classes[i];
1224 /* do this again since it may have been modified */
1225 class_exists = (cl != NULL);
1226 is_backlogged = (class_exists && !qempty(cl->cl_q));
1227
1228 if (is_backlogged && cl->concerned_rdc
1229 && result[i] + cl->service_rate < cl->min_rate_adc) {
1230 credit += cl->service_rate+result[i]
1231 -cl->min_rate_adc;
1232 /* "credit" is in fact a negative number */
1233 result[i] = -cl->service_rate+cl->min_rate_adc;
1234 }
1235 }
1236
1237 for (i = jif->jif_maxpri; (i >= 0 && credit < 0); i--) {
1238 cl = jif->jif_classes[i];
1239 class_exists = (cl != NULL);
1240 is_backlogged = (class_exists && !qempty(cl->cl_q));
1241
1242 if (is_backlogged && cl->concerned_rdc) {
1243 available = result[i]
1244 + cl->service_rate-cl->min_rate_adc;
1245 if (available >= -credit) {
1246 result[i] += credit;
1247 credit = 0;
1248 } else {
1249 result[i] -= available;
1250 credit += available;
1251 }
1252 }
1253 }
1254 return result;
1255 }
1256
1257 /*
1258 * assign_rate_drops_adc: returns the adjustment needed to
1259 * the service rates to meet the absolute delay/rate constraints
1260 * (delay/throughput bounds) and drops traffic if need be.
1261 * see tech. report UVA/T.R. CS-2000-24/CS-2001-21 for more info.
1262 */
1263
1264 static int64_t *
1265 assign_rate_drops_adc(struct jobs_if *jif)
1266 {
1267 int64_t *result;
1268 int class_exists, is_backlogged;
1269 struct jobs_class *cl;
1270
1271 int64_t *c, *n, *k;
1272 int64_t *available;
1273
1274 int lowest, highest;
1275 int keep_going;
1276 int i;
1277 u_int64_t now, oldest_arv;
1278 int64_t remaining_time;
1279 struct mbuf* pkt;
1280 u_int64_t len;
1281
1282 now = read_machclk();
1283 oldest_arv = now;
1284
1285 result = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK);
1286 if (result == NULL)
1287 return NULL;
1288 c = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK);
1289 if (c == NULL)
1290 return NULL;
1291 n = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK);
1292 if (n == NULL)
1293 return NULL;
1294 k = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK);
1295 if (k == NULL)
1296 return NULL;
1297 available = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK);
1298 if (available == NULL)
1299 return NULL;
1300
1301 for (i = 0; i <= jif->jif_maxpri; i++)
1302 result[i] = 0;
1303
1304 keep_going = 1;
1305
1306 for (i = 0; i <= jif->jif_maxpri; i++) {
1307 cl = jif->jif_classes[i];
1308 class_exists = (cl != NULL);
1309 is_backlogged = (class_exists && !qempty(cl->cl_q));
1310
1311 if (is_backlogged) {
1312 if (cl->concerned_adc) {
1313 /*
1314 * get the arrival time of the oldest
1315 * class-i packet
1316 */
1317 if (tslist_first(cl->arv_tm) == NULL)
1318 oldest_arv = now; /* NOTREACHED */
1319 else
1320 oldest_arv = (tslist_first(cl->arv_tm))->timestamp;
1321
1322 n[i] = cl->service_rate;
1323 k[i] = scale_rate((int64_t)(cl->cl_rin.bytes - cl->cl_rout.bytes));
1324
1325 remaining_time = cl->cl_adc
1326 - (int64_t)delay_diff(now, oldest_arv);
1327 if (remaining_time > 0) {
1328 c[i] = remaining_time;
1329 /*
1330 * c is the remaining time before
1331 * the deadline is violated
1332 * (in ticks)
1333 */
1334 available[i] = n[i]-k[i]/c[i];
1335 } else {
1336 /*
1337 * deadline has passed...
1338 * we allocate the whole link
1339 * capacity to hopefully
1340 * solve the problem
1341 */
1342 c[i] = 0;
1343 available[i] = -((int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth));
1344 }
1345 if (cl->concerned_arc) {
1346 /*
1347 * there's an ARC in addition
1348 * to the ADC
1349 */
1350 if (n[i] - cl->cl_arc < available[i])
1351 available[i] = n[i]
1352 - cl->cl_arc;
1353 }
1354 } else if (cl->concerned_arc) {
1355 /*
1356 * backlogged, concerned by ARC
1357 * but not by ADC
1358 */
1359 n[i] = cl->service_rate;
1360 available[i] = n[i] - cl->cl_arc;
1361 } else {
1362 /*
1363 * backlogged but not concerned by ADC
1364 * or ARC -> can give everything
1365 */
1366 n[i] = cl->service_rate;
1367 available[i] = n[i];
1368 }
1369 } else {
1370 /* not backlogged */
1371 n[i] = 0;
1372 k[i] = 0;
1373 c[i] = 0;
1374 if (class_exists)
1375 available[i] = cl->service_rate;
1376 else
1377 available[i] = 0;
1378 }
1379 }
1380
1381 /* step 1: adjust rates (greedy algorithm) */
1382
1383 highest = 0;
1384 lowest = jif->jif_maxpri;
1385
1386 while (highest < jif->jif_maxpri+1 && available[highest] >= 0)
1387 highest++; /* which is the highest class that needs more service? */
1388 while (lowest > 0 && available[lowest] <= 0)
1389 lowest--; /* which is the lowest class that needs less service? */
1390
1391 while (highest != jif->jif_maxpri+1 && lowest != -1) {
1392 /* give the excess service from lowest to highest */
1393 if (available[lowest]+available[highest] > 0) {
1394 /*
1395 * still some "credit" left
1396 * give all that is needed by "highest"
1397 */
1398 n[lowest] += available[highest];
1399 n[highest] -= available[highest];
1400 available[lowest] += available[highest];
1401 available[highest] = 0;
1402
1403 while (highest < jif->jif_maxpri+1
1404 && available[highest] >= 0)
1405 highest++; /* which is the highest class that needs more service now? */
1406
1407 } else if (available[lowest]+available[highest] == 0) {
1408 /* no more credit left but it's fine */
1409 n[lowest] += available[highest];
1410 n[highest] -= available[highest];
1411 available[highest] = 0;
1412 available[lowest] = 0;
1413
1414 while (highest < jif->jif_maxpri+1
1415 && available[highest] >= 0)
1416 highest++; /* which is the highest class that needs more service? */
1417 while (lowest >= 0 && available[lowest] <= 0)
1418 lowest--; /* which is the lowest class that needs less service? */
1419
1420 } else if (available[lowest]+available[highest] < 0) {
1421 /*
1422 * no more credit left and we need to switch
1423 * to another class
1424 */
1425 n[lowest] -= available[lowest];
1426 n[highest] += available[lowest];
1427 available[highest] += available[lowest];
1428 available[lowest] = 0;
1429
1430 while ((lowest >= 0)&&(available[lowest] <= 0))
1431 lowest--; /* which is the lowest class that needs less service? */
1432 }
1433 }
1434
1435 for (i = 0; i <= jif->jif_maxpri; i++) {
1436 cl = jif->jif_classes[i];
1437 class_exists = (cl != NULL);
1438 is_backlogged = (class_exists && !qempty(cl->cl_q));
1439 if (is_backlogged) {
1440 result[i] = n[i] - cl->service_rate;
1441 } else {
1442 if (class_exists)
1443 result[i] = - cl->service_rate;
1444 else
1445 result[i] = 0;
1446 }
1447 }
1448
1449 /* step 2: adjust drops (for ADC) */
1450
1451 if (highest != jif->jif_maxpri+1) {
1452 /* some class(es) still need(s) additional service */
1453 for (i = 0; i <= jif->jif_maxpri; i++) {
1454 cl = jif->jif_classes[i];
1455 class_exists = (cl != NULL);
1456 is_backlogged = (class_exists
1457 && !qempty(cl->cl_q));
1458 if (is_backlogged && available[i] < 0) {
1459 if (cl->concerned_adc) {
1460 k[i] = c[i]*n[i];
1461 while (keep_going && scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes)) > k[i]) {
1462 pkt = qtail(cl->cl_q);
1463 if (pkt != NULL) {
1464 /* "safeguard" test (a packet SHOULD be in there) */
1465 len = (u_int64_t)m_pktlen(pkt);
1466 /* access packet at the tail */
1467 if (cl->concerned_alc
1468 && cl->current_loss+(len << SCALE_LOSS)/cl->cl_arrival.bytes > cl->cl_alc) {
1469 keep_going = 0; /* relax ADC in favor of ALC */
1470 } else {
1471 /* drop packet at the tail of the class-i queue, update values */
1472 pkt = _getq_tail(cl->cl_q);
1473 len = (u_int64_t)m_pktlen(pkt);
1474 PKTCNTR_ADD(&cl->cl_dropcnt, (int)len);
1475 PKTCNTR_SUB(&cl->cl_rin, (int)len);
1476 PKTCNTR_ADD(&cl->st_dropcnt, (int)len);
1477 PKTCNTR_SUB(&cl->st_rin, (int)len);
1478 cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes;
1479 m_freem(pkt); /* the packet is trashed here */
1480 tslist_drop(cl);
1481 IFQ_DEC_LEN(cl->cl_jif->jif_ifq);
1482 }
1483 } else
1484 keep_going = 0; /* NOTREACHED */
1485 }
1486 k[i] = scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes));
1487 }
1488 /*
1489 * n[i] is the max rate we can give.
1490 * the above drops as much as possible
1491 * to respect a delay bound.
1492 * for throughput bounds,
1493 * there's nothing that can be done
1494 * after the greedy reallocation.
1495 */
1496 }
1497 }
1498 }
1499
1500 /* update the values of min_rate_adc */
1501 for (i = 0; i <= jif->jif_maxpri; i++) {
1502 cl = jif->jif_classes[i];
1503 class_exists = (cl != NULL);
1504 is_backlogged = (class_exists && !qempty(cl->cl_q));
1505 if (is_backlogged && cl->concerned_adc) {
1506 if (c[i] != 0) {
1507 if (cl->concerned_adc
1508 && !cl->concerned_arc)
1509 cl->min_rate_adc = k[i]/c[i];
1510 else
1511 cl->min_rate_adc = n[i];
1512 } else
1513 cl->min_rate_adc = (int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth);
1514 } else if (is_backlogged && cl->concerned_arc)
1515 cl->min_rate_adc = n[i]; /* the best we can give */
1516 else {
1517 if (class_exists)
1518 cl->min_rate_adc = 0;
1519 }
1520 }
1521
1522 free(c, M_DEVBUF);
1523 free(n, M_DEVBUF);
1524 free(k, M_DEVBUF);
1525 free(available, M_DEVBUF);
1526
1527 return (result);
1528 }
1529
1530 /*
1531 * update_error: returns the difference between the mean weighted
1532 * delay and the weighted delay for each class. if proportional
1533 * delay differentiation is perfectly achieved, it should return
1534 * zero for each class.
1535 */
1536 static int64_t *
1537 update_error(struct jobs_if *jif)
1538 {
1539 int i;
1540 int active_classes, backlogged_classes;
1541 u_int64_t mean_weighted_delay;
1542 u_int64_t delays[JOBS_MAXPRI];
1543 int64_t* error;
1544 int class_exists, is_backlogged;
1545 struct jobs_class *cl;
1546
1547 error = malloc(sizeof(int64_t)*(jif->jif_maxpri+1), M_DEVBUF,
1548 M_WAITOK|M_ZERO);
1549
1550 if (error == NULL)
1551 return NULL;
1552
1553 mean_weighted_delay = 0;
1554 active_classes = 0;
1555 backlogged_classes = 0;
1556
1557 for (i = 0; i <= jif->jif_maxpri; i++) {
1558 cl = jif->jif_classes[i];
1559 class_exists = (cl != NULL);
1560 is_backlogged = (class_exists && !qempty(cl->cl_q));
1561
1562 if (is_backlogged) {
1563 backlogged_classes++;
1564 if (cl->concerned_rdc) {
1565 delays[i] = proj_delay(jif, i);
1566 mean_weighted_delay += cl->delay_prod_others*delays[i];
1567 active_classes ++;
1568 }
1569 }
1570 }
1571
1572 if (active_classes == 0)
1573 return error;
1574 else
1575 mean_weighted_delay /= active_classes;
1576
1577 for (i = 0; i <= jif->jif_maxpri; i++) {
1578 cl = jif->jif_classes[i];
1579 class_exists = (cl != NULL);
1580 is_backlogged = (class_exists && !qempty(cl->cl_q));
1581
1582 if (is_backlogged && cl->concerned_rdc)
1583 error[i] = ((int64_t)mean_weighted_delay)-((int64_t)cl->delay_prod_others*delays[i]);
1584 else
1585 error[i] = 0; /*
1586 * either the class isn't concerned,
1587 * or it's not backlogged.
1588 * in any case, the rate shouldn't
1589 * be adjusted.
1590 */
1591 }
1592 return error;
1593 }
1594
1595 /*
1596 * min_rates_adc: computes the minimum service rates needed in
1597 * each class to meet the absolute delay bounds. if, for any
1598 * class i, the current service rate of class i is less than
1599 * the computed minimum service rate, this function returns
1600 * false, true otherwise.
1601 */
1602 static int
1603 min_rates_adc(struct jobs_if *jif)
1604 {
1605 int result;
1606 int i;
1607 int class_exists, is_backlogged;
1608 int64_t remaining_time;
1609 struct jobs_class *cl;
1610 result = 1;
1611
1612 for (i = 0; i <= jif->jif_maxpri; i++) {
1613 cl = jif->jif_classes[i];
1614 class_exists = (cl != NULL);
1615 is_backlogged = (class_exists && !qempty(cl->cl_q));
1616 if (is_backlogged && cl->concerned_adc) {
1617 remaining_time = cl->cl_adc - proj_delay(jif, i);
1618 if (remaining_time > 0 ) {
1619 /* min rate needed for ADC */
1620 cl->min_rate_adc = scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes))/remaining_time;
1621 if (cl->concerned_arc
1622 && cl->cl_arc > cl->min_rate_adc) {
1623 /* min rate needed for ADC + ARC */
1624 cl->min_rate_adc = cl->cl_arc;
1625 }
1626 } else {
1627 /* the deadline has been exceeded: give the whole link capacity to hopefully fix the situation */
1628 cl->min_rate_adc = (int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth);
1629 }
1630 } else if (is_backlogged && cl->concerned_arc)
1631 cl->min_rate_adc = cl->cl_arc; /* no ADC, an ARC */
1632 else if (class_exists)
1633 cl->min_rate_adc = 0; /*
1634 * either the class is not
1635 * backlogged
1636 * or there is no ADC and
1637 * no ARC
1638 */
1639 if (is_backlogged && cl->min_rate_adc > cl->service_rate)
1640 result = 0;
1641 }
1642
1643 return result;
1644 }
1645
1646 /*
1647 * proj_delay: computes the difference between the current time
1648 * and the time the oldest class-i packet still in the class-i
1649 * queue i arrived in the system.
1650 */
1651 static int64_t
1652 proj_delay(struct jobs_if *jif, int i)
1653 {
1654 u_int64_t now;
1655 int class_exists, is_backlogged;
1656 struct jobs_class *cl;
1657
1658 now = read_machclk();
1659 cl = jif->jif_classes[i];
1660 class_exists = (cl != NULL);
1661 is_backlogged = (class_exists && !qempty(cl->cl_q));
1662
1663 if (is_backlogged)
1664 return ((int64_t)delay_diff(now, tslist_first(cl->arv_tm)->timestamp));
1665
1666 return (0); /* NOTREACHED */
1667 }
1668
1669 /*
1670 * pick_dropped_rlc: returns the class index of the class to be
1671 * dropped for meeting the relative loss constraints.
1672 */
1673 static int
1674 pick_dropped_rlc(struct jobs_if *jif)
1675 {
1676 int64_t mean;
1677 int64_t* loss_error;
1678 int i, active_classes, backlogged_classes;
1679 int class_exists, is_backlogged;
1680 int class_dropped;
1681 int64_t max_error;
1682 int64_t max_alc;
1683 struct mbuf* pkt;
1684 struct jobs_class *cl;
1685 u_int64_t len;
1686
1687 loss_error = malloc(sizeof(int64_t)*(jif->jif_maxpri+1),
1688 M_DEVBUF, M_WAITOK);
1689
1690 if (loss_error == NULL)
1691 return -1;
1692
1693 class_dropped = -1;
1694 max_error = 0;
1695 mean = 0;
1696 active_classes = 0;
1697 backlogged_classes = 0;
1698
1699 for (i = 0; i <= jif->jif_maxpri; i++) {
1700 cl = jif->jif_classes[i];
1701 class_exists = (cl != NULL);
1702 is_backlogged = (class_exists && !qempty(cl->cl_q));
1703 if (is_backlogged) {
1704 backlogged_classes ++;
1705 if (cl->concerned_rlc) {
1706 mean += cl->loss_prod_others
1707 * cl->current_loss;
1708 active_classes++;
1709 }
1710 }
1711 }
1712
1713 if (active_classes > 0)
1714 mean /= active_classes;
1715
1716 if (active_classes == 0)
1717 class_dropped = JOBS_MAXPRI+1; /*
1718 * no classes are concerned
1719 * by RLCs (JOBS_MAXPRI+1
1720 * means "ignore RLC" here)
1721 */
1722 else {
1723 for (i = 0; i <= jif->jif_maxpri; i++) {
1724 cl = jif->jif_classes[i];
1725 class_exists = (cl != NULL);
1726 is_backlogged = (class_exists
1727 && !qempty(cl->cl_q));
1728
1729 if ((is_backlogged)&&(cl->cl_rlc))
1730 loss_error[i]=cl->loss_prod_others
1731 *cl->current_loss-mean;
1732 else
1733 loss_error[i] = INFINITY;
1734 }
1735
1736 for (i = 0; i <= jif->jif_maxpri; i++) {
1737 cl = jif->jif_classes[i];
1738 class_exists = (cl != NULL);
1739 is_backlogged = (class_exists
1740 && !qempty(cl->cl_q));
1741 if (is_backlogged && loss_error[i] <= max_error) {
1742 /*
1743 * find out which class is the most
1744 * below the mean.
1745 * it's the one that needs to be dropped
1746 * ties are broken in favor of the higher
1747 * priority classes (i.e., if two classes
1748 * present the same deviation, the lower
1749 * priority class will get dropped).
1750 */
1751 max_error = loss_error[i];
1752 class_dropped = i;
1753 }
1754 }
1755
1756 if (class_dropped != -1) {
1757 cl = jif->jif_classes[class_dropped];
1758 pkt = qtail(cl->cl_q);
1759 if (pkt != NULL) {
1760 /*
1761 * "safeguard" test (a packet SHOULD be
1762 * in there)
1763 */
1764 len = (u_int64_t)m_pktlen(pkt);
1765 /* access packet at the tail */
1766 if (cl->current_loss+(len << SCALE_LOSS)/cl->cl_arrival.bytes > cl->cl_alc) {
1767 /*
1768 * the class to drop for meeting
1769 * the RLC will defeat the ALC:
1770 * ignore RLC.
1771 */
1772 class_dropped = JOBS_MAXPRI+1;
1773 }
1774 } else
1775 class_dropped = JOBS_MAXPRI+1; /* NOTREACHED */
1776 } else
1777 class_dropped = JOBS_MAXPRI+1;
1778 }
1779
1780 if (class_dropped == JOBS_MAXPRI+1) {
1781 max_alc = -((int64_t)1 << SCALE_LOSS);
1782 for (i = jif->jif_maxpri; i >= 0; i--) {
1783 cl = jif->jif_classes[i];
1784 class_exists = (cl != NULL);
1785 is_backlogged = (class_exists
1786 && !qempty(cl->cl_q));
1787 if (is_backlogged) {
1788 if (cl->concerned_alc && cl->cl_alc - cl->current_loss > max_alc) {
1789 max_alc = cl->cl_alc-cl->current_loss; /* pick the class which is the furthest from its ALC */
1790 class_dropped = i;
1791 } else if (!cl->concerned_alc && ((int64_t) 1 << SCALE_LOSS)-cl->current_loss > max_alc) {
1792 max_alc = ((int64_t) 1 << SCALE_LOSS)-cl->current_loss;
1793 class_dropped = i;
1794 }
1795 }
1796 }
1797 }
1798
1799 free(loss_error, M_DEVBUF);
1800 return (class_dropped);
1801 }
1802
1803 /*
1804 * ALTQ binding/setup functions
1805 */
1806 /*
1807 * jobs device interface
1808 */
1809 int
1810 jobsopen(dev_t dev, int flag, int fmt,
1811 struct lwp *l)
1812 {
1813 if (machclk_freq == 0)
1814 init_machclk();
1815
1816 if (machclk_freq == 0) {
1817 printf("jobs: no CPU clock available!\n");
1818 return (ENXIO);
1819 }
1820 /* everything will be done when the queueing scheme is attached. */
1821 return 0;
1822 }
1823
1824 int
1825 jobsclose(dev_t dev, int flag, int fmt,
1826 struct lwp *l)
1827 {
1828 struct jobs_if *jif;
1829 int err, error = 0;
1830
1831 while ((jif = jif_list) != NULL) {
1832 /* destroy all */
1833 if (ALTQ_IS_ENABLED(jif->jif_ifq))
1834 altq_disable(jif->jif_ifq);
1835
1836 err = altq_detach(jif->jif_ifq);
1837 if (err == 0)
1838 err = jobs_detach(jif);
1839 if (err != 0 && error == 0)
1840 error = err;
1841 }
1842
1843 return error;
1844 }
1845
1846 int
1847 jobsioctl(dev_t dev, ioctlcmd_t cmd, void *addr, int flag,
1848 struct lwp *l)
1849 {
1850 struct jobs_if *jif;
1851 struct jobs_interface *ifacep;
1852 struct proc *p = l->l_proc;
1853 int error = 0;
1854
1855 /* check super-user privilege */
1856 switch (cmd) {
1857 case JOBS_GETSTATS:
1858 break;
1859 default:
1860 #if (__FreeBSD_version > 400000)
1861 if ((error = suser(p)) != 0)
1862 return (error);
1863 #else
1864 if ((error = kauth_authorize_network(p->p_cred,
1865 KAUTH_NETWORK_ALTQ, KAUTH_REQ_NETWORK_ALTQ_JOBS, NULL,
1866 NULL, NULL)) != 0)
1867 return (error);
1868 #endif
1869 break;
1870 }
1871
1872 switch (cmd) {
1873
1874 case JOBS_IF_ATTACH:
1875 error = jobscmd_if_attach((struct jobs_attach *)addr);
1876 break;
1877
1878 case JOBS_IF_DETACH:
1879 error = jobscmd_if_detach((struct jobs_interface *)addr);
1880 break;
1881
1882 case JOBS_ENABLE:
1883 case JOBS_DISABLE:
1884 case JOBS_CLEAR:
1885 ifacep = (struct jobs_interface *)addr;
1886 if ((jif = altq_lookup(ifacep->jobs_ifname,
1887 ALTQT_JOBS)) == NULL) {
1888 error = EBADF;
1889 break;
1890 }
1891
1892 switch (cmd) {
1893 case JOBS_ENABLE:
1894 if (jif->jif_default == NULL) {
1895 #if 1
1896 printf("jobs: no default class\n");
1897 #endif
1898 error = EINVAL;
1899 break;
1900 }
1901 error = altq_enable(jif->jif_ifq);
1902 break;
1903
1904 case JOBS_DISABLE:
1905 error = altq_disable(jif->jif_ifq);
1906 break;
1907
1908 case JOBS_CLEAR:
1909 jobs_clear_interface(jif);
1910 break;
1911 }
1912 break;
1913
1914 case JOBS_ADD_CLASS:
1915 error = jobscmd_add_class((struct jobs_add_class *)addr);
1916 break;
1917
1918 case JOBS_DEL_CLASS:
1919 error = jobscmd_delete_class((struct jobs_delete_class *)addr);
1920 break;
1921
1922 case JOBS_MOD_CLASS:
1923 error = jobscmd_modify_class((struct jobs_modify_class *)addr);
1924 break;
1925
1926 case JOBS_ADD_FILTER:
1927 error = jobscmd_add_filter((struct jobs_add_filter *)addr);
1928 break;
1929
1930 case JOBS_DEL_FILTER:
1931 error = jobscmd_delete_filter((struct jobs_delete_filter *)addr);
1932 break;
1933
1934 case JOBS_GETSTATS:
1935 error = jobscmd_class_stats((struct jobs_class_stats *)addr);
1936 break;
1937
1938 default:
1939 error = EINVAL;
1940 break;
1941 }
1942 return error;
1943 }
1944
1945 static int
1946 jobscmd_if_attach(struct jobs_attach *ap)
1947 {
1948 struct jobs_if *jif;
1949 struct ifnet *ifp;
1950 int error;
1951
1952 if ((ifp = ifunit(ap->iface.jobs_ifname)) == NULL)
1953 return (ENXIO);
1954 if ((jif = jobs_attach(&ifp->if_snd, ap->bandwidth, ap->qlimit, ap->separate)) == NULL)
1955 return (ENOMEM);
1956
1957 /*
1958 * set JOBS to this ifnet structure.
1959 */
1960 if ((error = altq_attach(&ifp->if_snd, ALTQT_JOBS, jif,
1961 jobs_enqueue, jobs_dequeue, jobs_request,
1962 &jif->jif_classifier, acc_classify)) != 0)
1963 (void)jobs_detach(jif);
1964
1965 return (error);
1966 }
1967
1968 static int
1969 jobscmd_if_detach(struct jobs_interface *ap)
1970 {
1971 struct jobs_if *jif;
1972 int error;
1973
1974 if ((jif = altq_lookup(ap->jobs_ifname, ALTQT_JOBS)) == NULL)
1975 return (EBADF);
1976
1977 if (ALTQ_IS_ENABLED(jif->jif_ifq))
1978 altq_disable(jif->jif_ifq);
1979
1980 if ((error = altq_detach(jif->jif_ifq)))
1981 return (error);
1982
1983 return jobs_detach(jif);
1984 }
1985
1986 static int
1987 jobscmd_add_class(struct jobs_add_class *ap)
1988 {
1989 struct jobs_if *jif;
1990 struct jobs_class *cl;
1991
1992 if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
1993 return (EBADF);
1994
1995 if (ap->pri < 0 || ap->pri >= JOBS_MAXPRI)
1996 return (EINVAL);
1997
1998 if ((cl = jobs_class_create(jif, ap->pri,
1999 ap->cl_adc, ap->cl_rdc,
2000 ap->cl_alc, ap->cl_rlc, ap-> cl_arc,
2001 ap->flags)) == NULL)
2002 return (ENOMEM);
2003
2004 /* return a class handle to the user */
2005 ap->class_handle = clp_to_clh(cl);
2006 return (0);
2007 }
2008
2009 static int
2010 jobscmd_delete_class(struct jobs_delete_class *ap)
2011 {
2012 struct jobs_if *jif;
2013 struct jobs_class *cl;
2014
2015 if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
2016 return (EBADF);
2017
2018 if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL)
2019 return (EINVAL);
2020
2021 return jobs_class_destroy(cl);
2022 }
2023
2024 static int
2025 jobscmd_modify_class(struct jobs_modify_class *ap)
2026 {
2027 struct jobs_if *jif;
2028 struct jobs_class *cl;
2029
2030 if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
2031 return (EBADF);
2032
2033 if (ap->pri < 0 || ap->pri >= JOBS_MAXPRI)
2034 return (EINVAL);
2035
2036 if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL)
2037 return (EINVAL);
2038
2039 /*
2040 * if priority is changed, move the class to the new priority
2041 */
2042 if (jif->jif_classes[ap->pri] != cl) {
2043 if (jif->jif_classes[ap->pri] != NULL)
2044 return (EEXIST);
2045 jif->jif_classes[cl->cl_pri] = NULL;
2046 jif->jif_classes[ap->pri] = cl;
2047 cl->cl_pri = ap->pri;
2048 }
2049
2050 /* call jobs_class_create to change class parameters */
2051 if ((cl = jobs_class_create(jif, ap->pri,
2052 ap->cl_adc, ap->cl_rdc,
2053 ap->cl_alc, ap->cl_rlc, ap->cl_arc,
2054 ap->flags)) == NULL)
2055 return (ENOMEM);
2056 return 0;
2057 }
2058
2059 static int
2060 jobscmd_add_filter(struct jobs_add_filter *ap)
2061 {
2062 struct jobs_if *jif;
2063 struct jobs_class *cl;
2064
2065 if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
2066 return (EBADF);
2067
2068 if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL)
2069 return (EINVAL);
2070
2071 return acc_add_filter(&jif->jif_classifier, &ap->filter,
2072 cl, &ap->filter_handle);
2073 }
2074
2075 static int
2076 jobscmd_delete_filter(struct jobs_delete_filter *ap)
2077 {
2078 struct jobs_if *jif;
2079
2080 if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
2081 return (EBADF);
2082
2083 return acc_delete_filter(&jif->jif_classifier, ap->filter_handle);
2084 }
2085
2086 static int
2087 jobscmd_class_stats(struct jobs_class_stats *ap)
2088 {
2089 struct jobs_if *jif;
2090 struct jobs_class *cl;
2091 struct class_stats stats, *usp;
2092 int pri, error;
2093
2094 if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL)
2095 return (EBADF);
2096
2097 ap->maxpri = jif->jif_maxpri;
2098
2099 /* then, read the next N classes */
2100 usp = ap->stats;
2101 for (pri = 0; pri <= jif->jif_maxpri; pri++) {
2102 cl = jif->jif_classes[pri];
2103 if (cl != NULL)
2104 get_class_stats(&stats, cl);
2105 else
2106 (void)memset(&stats, 0, sizeof(stats));
2107 if ((error = copyout((void *)&stats, (void *)usp++,
2108 sizeof(stats))) != 0)
2109 return (error);
2110 }
2111 return (0);
2112 }
2113
2114 static void
2115 get_class_stats(struct class_stats *sp, struct jobs_class *cl)
2116 {
2117 u_int64_t now;
2118 now = read_machclk();
2119
2120 sp->class_handle = clp_to_clh(cl);
2121 sp->qlength = qlen(cl->cl_q);
2122
2123 sp->period = cl->cl_period;
2124 sp->rin = cl->st_rin;
2125 sp->arrival = cl->st_arrival;
2126 sp->arrivalbusy = cl->cl_arrival;
2127 sp->rout = cl->st_rout;
2128 sp->dropcnt = cl->cl_dropcnt;
2129
2130 /* PKTCNTR_RESET(&cl->st_arrival);*/
2131 PKTCNTR_RESET(&cl->st_rin);
2132 PKTCNTR_RESET(&cl->st_rout);
2133
2134 sp->totallength = cl->cl_jif->jif_ifq->ifq_len;
2135 sp->lastdel = ticks_to_secs(GRANULARITY*cl->cl_lastdel);
2136 sp->avgdel = cl->cl_avgdel;
2137
2138 cl->cl_avgdel = 0;
2139
2140 sp->busylength = ticks_to_secs(1000*delay_diff(now, cl->idletime));
2141 sp->adc_violations = cl->adc_violations;
2142
2143 sp->wc_cycles_enqueue = cl->cl_jif->wc_cycles_enqueue;
2144 sp->wc_cycles_dequeue = cl->cl_jif->wc_cycles_dequeue;
2145 sp->bc_cycles_enqueue = cl->cl_jif->bc_cycles_enqueue;
2146 sp->bc_cycles_dequeue = cl->cl_jif->bc_cycles_dequeue;
2147 sp->avg_cycles_enqueue = cl->cl_jif->avg_cycles_enqueue;
2148 sp->avg_cycles_dequeue = cl->cl_jif->avg_cycles_dequeue;
2149 sp->avg_cycles2_enqueue = cl->cl_jif->avg_cycles2_enqueue;
2150 sp->avg_cycles2_dequeue = cl->cl_jif->avg_cycles2_dequeue;
2151 sp->total_enqueued = cl->cl_jif->total_enqueued;
2152 sp->total_dequeued = cl->cl_jif->total_dequeued;
2153 }
2154
2155 /* convert a class handle to the corresponding class pointer */
2156 static struct jobs_class *
2157 clh_to_clp(struct jobs_if *jif, u_long chandle)
2158 {
2159 struct jobs_class *cl;
2160
2161 cl = (struct jobs_class *)chandle;
2162 if (chandle != ALIGN(cl)) {
2163 #if 1
2164 printf("clh_to_cl: unaligned pointer %p\n", cl);
2165 #endif
2166 return (NULL);
2167 }
2168
2169 if (cl == NULL || cl->cl_handle != chandle || cl->cl_jif != jif)
2170 return (NULL);
2171 return (cl);
2172 }
2173
2174 /* convert a class pointer to the corresponding class handle */
2175 static u_long
2176 clp_to_clh(struct jobs_class *cl)
2177 {
2178 return (cl->cl_handle);
2179 }
2180
2181 #ifdef KLD_MODULE
2182
2183 static struct altqsw jobs_sw =
2184 {"jobs", jobsopen, jobsclose, jobsioctl};
2185
2186 ALTQ_MODULE(altq_jobs, ALTQT_JOBS, &jobs_sw);
2187
2188 #endif /* KLD_MODULE */
2189
2190 #endif /* ALTQ3_COMPAT */
2191 #endif /* ALTQ_JOBS */
NetBSD on the FriendlyARM MINI2440