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