altq_rio.c revision 1.1
1 /* $KAME: altq_rio.c,v 1.8 2000/12/14 08:12:46 thorpej Exp $ */ 2 3 /* 4 * Copyright (C) 1998-2000 5 * Sony Computer Science Laboratories Inc. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 /* 29 * Copyright (c) 1990-1994 Regents of the University of California. 30 * All rights reserved. 31 * 32 * Redistribution and use in source and binary forms, with or without 33 * modification, are permitted provided that the following conditions 34 * are met: 35 * 1. Redistributions of source code must retain the above copyright 36 * notice, this list of conditions and the following disclaimer. 37 * 2. Redistributions in binary form must reproduce the above copyright 38 * notice, this list of conditions and the following disclaimer in the 39 * documentation and/or other materials provided with the distribution. 40 * 3. All advertising materials mentioning features or use of this software 41 * must display the following acknowledgement: 42 * This product includes software developed by the Computer Systems 43 * Engineering Group at Lawrence Berkeley Laboratory. 44 * 4. Neither the name of the University nor of the Laboratory may be used 45 * to endorse or promote products derived from this software without 46 * specific prior written permission. 47 * 48 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 49 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 50 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 51 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 52 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 53 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 54 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 55 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 56 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 57 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 58 * SUCH DAMAGE. 59 */ 60 61 #if defined(__FreeBSD__) || defined(__NetBSD__) 62 #include "opt_altq.h" 63 #if (__FreeBSD__ != 2) 64 #include "opt_inet.h" 65 #ifdef __FreeBSD__ 66 #include "opt_inet6.h" 67 #endif 68 #endif 69 #endif /* __FreeBSD__ || __NetBSD__ */ 70 #ifdef ALTQ_RIO /* rio is enabled by ALTQ_RIO option in opt_altq.h */ 71 72 #include <sys/param.h> 73 #include <sys/malloc.h> 74 #include <sys/mbuf.h> 75 #include <sys/socket.h> 76 #include <sys/sockio.h> 77 #include <sys/systm.h> 78 #include <sys/proc.h> 79 #include <sys/errno.h> 80 #include <sys/kernel.h> 81 82 #include <net/if.h> 83 #include <net/if_types.h> 84 85 #include <netinet/in.h> 86 #include <netinet/in_systm.h> 87 #include <netinet/ip.h> 88 #ifdef INET6 89 #include <netinet/ip6.h> 90 #endif 91 92 #include <altq/altq.h> 93 #include <altq/altq_conf.h> 94 #include <altq/altq_cdnr.h> 95 #include <altq/altq_red.h> 96 #include <altq/altq_rio.h> 97 98 /* 99 * RIO: RED with IN/OUT bit 100 * described in 101 * "Explicit Allocation of Best Effort Packet Delivery Service" 102 * David D. Clark and Wenjia Fang, MIT Lab for Computer Science 103 * http://diffserv.lcs.mit.edu/Papers/exp-alloc-ddc-wf.{ps,pdf} 104 * 105 * this implementation is extended to support more than 2 drop precedence 106 * values as described in RFC2597 (Assured Forwarding PHB Group). 107 * 108 */ 109 /* 110 * AF DS (differentiated service) codepoints. 111 * (classes can be mapped to CBQ or H-FSC classes.) 112 * 113 * 0 1 2 3 4 5 6 7 114 * +---+---+---+---+---+---+---+---+ 115 * | CLASS |DropPre| 0 | CU | 116 * +---+---+---+---+---+---+---+---+ 117 * 118 * class 1: 001 119 * class 2: 010 120 * class 3: 011 121 * class 4: 100 122 * 123 * low drop prec: 01 124 * medium drop prec: 10 125 * high drop prec: 01 126 */ 127 128 /* normal red parameters */ 129 #define W_WEIGHT 512 /* inverse of weight of EWMA (511/512) */ 130 /* q_weight = 0.00195 */ 131 132 /* red parameters for a slow link */ 133 #define W_WEIGHT_1 128 /* inverse of weight of EWMA (127/128) */ 134 /* q_weight = 0.0078125 */ 135 136 /* red parameters for a very slow link (e.g., dialup) */ 137 #define W_WEIGHT_2 64 /* inverse of weight of EWMA (63/64) */ 138 /* q_weight = 0.015625 */ 139 140 /* fixed-point uses 12-bit decimal places */ 141 #define FP_SHIFT 12 /* fixed-point shift */ 142 143 /* red parameters for drop probability */ 144 #define INV_P_MAX 10 /* inverse of max drop probability */ 145 #define TH_MIN 5 /* min threshold */ 146 #define TH_MAX 15 /* max threshold */ 147 148 #define RIO_LIMIT 60 /* default max queue lenght */ 149 #define RIO_STATS /* collect statistics */ 150 151 #define TV_DELTA(a, b, delta) { \ 152 register int xxs; \ 153 \ 154 delta = (a)->tv_usec - (b)->tv_usec; \ 155 if ((xxs = (a)->tv_sec - (b)->tv_sec) != 0) { \ 156 if (xxs < 0) { \ 157 printf("rm_class: bogus time values"); \ 158 delta = 60000000; \ 159 } else if (xxs > 4) { \ 160 if (xxs > 60) \ 161 delta = 60000000; \ 162 else \ 163 delta += xxs * 1000000; \ 164 } else while (xxs > 0) { \ 165 delta += 1000000; \ 166 xxs--; \ 167 } \ 168 } \ 169 } 170 171 /* rio_list keeps all rio_queue_t's allocated. */ 172 static rio_queue_t *rio_list = NULL; 173 /* default rio parameter values */ 174 static struct redparams default_rio_params[RIO_NDROPPREC] = { 175 /* th_min, th_max, inv_pmax */ 176 { TH_MAX * 2 + TH_MIN, TH_MAX * 3, INV_P_MAX }, /* low drop precedence */ 177 { TH_MAX + TH_MIN, TH_MAX * 2, INV_P_MAX }, /* medium drop precedence */ 178 { TH_MIN, TH_MAX, INV_P_MAX } /* high drop precedence */ 179 }; 180 181 /* internal function prototypes */ 182 static int rio_enqueue __P((struct ifaltq *, struct mbuf *, 183 struct altq_pktattr *)); 184 static struct mbuf *rio_dequeue __P((struct ifaltq *, int)); 185 static int rio_request __P((struct ifaltq *, int, void *)); 186 static int rio_detach __P((rio_queue_t *)); 187 static int dscp2index __P((u_int8_t)); 188 189 /* 190 * rio device interface 191 */ 192 altqdev_decl(rio); 193 194 int 195 rioopen(dev, flag, fmt, p) 196 dev_t dev; 197 int flag, fmt; 198 struct proc *p; 199 { 200 /* everything will be done when the queueing scheme is attached. */ 201 return 0; 202 } 203 204 int 205 rioclose(dev, flag, fmt, p) 206 dev_t dev; 207 int flag, fmt; 208 struct proc *p; 209 { 210 rio_queue_t *rqp; 211 int err, error = 0; 212 213 while ((rqp = rio_list) != NULL) { 214 /* destroy all */ 215 err = rio_detach(rqp); 216 if (err != 0 && error == 0) 217 error = err; 218 } 219 220 return error; 221 } 222 223 int 224 rioioctl(dev, cmd, addr, flag, p) 225 dev_t dev; 226 ioctlcmd_t cmd; 227 caddr_t addr; 228 int flag; 229 struct proc *p; 230 { 231 rio_queue_t *rqp; 232 struct rio_interface *ifacep; 233 struct ifnet *ifp; 234 int error = 0; 235 236 /* check super-user privilege */ 237 switch (cmd) { 238 case RIO_GETSTATS: 239 break; 240 default: 241 #if (__FreeBSD_version > 400000) 242 if ((error = suser(p)) != 0) 243 return (error); 244 #else 245 if ((error = suser(p->p_ucred, &p->p_acflag)) != 0) 246 return (error); 247 #endif 248 break; 249 } 250 251 switch (cmd) { 252 253 case RIO_ENABLE: 254 ifacep = (struct rio_interface *)addr; 255 if ((rqp = altq_lookup(ifacep->rio_ifname, ALTQT_RIO)) == NULL) { 256 error = EBADF; 257 break; 258 } 259 error = altq_enable(rqp->rq_ifq); 260 break; 261 262 case RIO_DISABLE: 263 ifacep = (struct rio_interface *)addr; 264 if ((rqp = altq_lookup(ifacep->rio_ifname, ALTQT_RIO)) == NULL) { 265 error = EBADF; 266 break; 267 } 268 error = altq_disable(rqp->rq_ifq); 269 break; 270 271 case RIO_IF_ATTACH: 272 ifp = ifunit(((struct rio_interface *)addr)->rio_ifname); 273 if (ifp == NULL) { 274 error = ENXIO; 275 break; 276 } 277 278 /* allocate and initialize rio_queue_t */ 279 MALLOC(rqp, rio_queue_t *, sizeof(rio_queue_t), M_DEVBUF, M_WAITOK); 280 if (rqp == NULL) { 281 error = ENOMEM; 282 break; 283 } 284 bzero(rqp, sizeof(rio_queue_t)); 285 286 MALLOC(rqp->rq_q, class_queue_t *, sizeof(class_queue_t), 287 M_DEVBUF, M_WAITOK); 288 if (rqp->rq_q == NULL) { 289 FREE(rqp, M_DEVBUF); 290 error = ENOMEM; 291 break; 292 } 293 bzero(rqp->rq_q, sizeof(class_queue_t)); 294 295 rqp->rq_rio = rio_alloc(0, NULL, 0, 0); 296 if (rqp->rq_rio == NULL) { 297 FREE(rqp->rq_q, M_DEVBUF); 298 FREE(rqp, M_DEVBUF); 299 error = ENOMEM; 300 break; 301 } 302 303 rqp->rq_ifq = &ifp->if_snd; 304 qtail(rqp->rq_q) = NULL; 305 qlen(rqp->rq_q) = 0; 306 qlimit(rqp->rq_q) = RIO_LIMIT; 307 qtype(rqp->rq_q) = Q_RIO; 308 309 /* 310 * set RIO to this ifnet structure. 311 */ 312 error = altq_attach(rqp->rq_ifq, ALTQT_RIO, rqp, 313 rio_enqueue, rio_dequeue, rio_request, 314 NULL, NULL); 315 if (error) { 316 rio_destroy(rqp->rq_rio); 317 FREE(rqp->rq_q, M_DEVBUF); 318 FREE(rqp, M_DEVBUF); 319 break; 320 } 321 322 /* add this state to the rio list */ 323 rqp->rq_next = rio_list; 324 rio_list = rqp; 325 break; 326 327 case RIO_IF_DETACH: 328 ifacep = (struct rio_interface *)addr; 329 if ((rqp = altq_lookup(ifacep->rio_ifname, ALTQT_RIO)) == NULL) { 330 error = EBADF; 331 break; 332 } 333 error = rio_detach(rqp); 334 break; 335 336 case RIO_GETSTATS: 337 do { 338 struct rio_stats *q_stats; 339 rio_t *rp; 340 int i; 341 342 q_stats = (struct rio_stats *)addr; 343 if ((rqp = altq_lookup(q_stats->iface.rio_ifname, 344 ALTQT_RIO)) == NULL) { 345 error = EBADF; 346 break; 347 } 348 349 rp = rqp->rq_rio; 350 351 q_stats->q_limit = qlimit(rqp->rq_q); 352 q_stats->weight = rp->rio_weight; 353 q_stats->flags = rp->rio_flags; 354 355 for (i = 0; i < RIO_NDROPPREC; i++) { 356 q_stats->q_len[i] = rp->rio_precstate[i].qlen; 357 bcopy(&rp->q_stats[i], &q_stats->q_stats[i], 358 sizeof(struct redstats)); 359 q_stats->q_stats[i].q_avg = 360 rp->rio_precstate[i].avg >> rp->rio_wshift; 361 362 q_stats->q_params[i].inv_pmax 363 = rp->rio_precstate[i].inv_pmax; 364 q_stats->q_params[i].th_min 365 = rp->rio_precstate[i].th_min; 366 q_stats->q_params[i].th_max 367 = rp->rio_precstate[i].th_max; 368 } 369 } while (0); 370 break; 371 372 case RIO_CONFIG: 373 do { 374 struct rio_conf *fc; 375 rio_t *new; 376 int s, limit, i; 377 378 fc = (struct rio_conf *)addr; 379 if ((rqp = altq_lookup(fc->iface.rio_ifname, 380 ALTQT_RIO)) == NULL) { 381 error = EBADF; 382 break; 383 } 384 385 new = rio_alloc(fc->rio_weight, &fc->q_params[0], 386 fc->rio_flags, fc->rio_pkttime); 387 if (new == NULL) { 388 error = ENOMEM; 389 break; 390 } 391 392 s = splimp(); 393 _flushq(rqp->rq_q); 394 limit = fc->rio_limit; 395 if (limit < fc->q_params[RIO_NDROPPREC-1].th_max) 396 limit = fc->q_params[RIO_NDROPPREC-1].th_max; 397 qlimit(rqp->rq_q) = limit; 398 399 rio_destroy(rqp->rq_rio); 400 rqp->rq_rio = new; 401 402 splx(s); 403 404 /* write back new values */ 405 fc->rio_limit = limit; 406 for (i = 0; i < RIO_NDROPPREC; i++) { 407 fc->q_params[i].inv_pmax = 408 rqp->rq_rio->rio_precstate[i].inv_pmax; 409 fc->q_params[i].th_min = 410 rqp->rq_rio->rio_precstate[i].th_min; 411 fc->q_params[i].th_max = 412 rqp->rq_rio->rio_precstate[i].th_max; 413 } 414 } while (0); 415 break; 416 417 case RIO_SETDEFAULTS: 418 do { 419 struct redparams *rp; 420 int i; 421 422 rp = (struct redparams *)addr; 423 for (i = 0; i < RIO_NDROPPREC; i++) 424 default_rio_params[i] = rp[i]; 425 } while (0); 426 break; 427 428 default: 429 error = EINVAL; 430 break; 431 } 432 433 return error; 434 } 435 436 static int 437 rio_detach(rqp) 438 rio_queue_t *rqp; 439 { 440 rio_queue_t *tmp; 441 int error = 0; 442 443 if (ALTQ_IS_ENABLED(rqp->rq_ifq)) 444 altq_disable(rqp->rq_ifq); 445 446 if ((error = altq_detach(rqp->rq_ifq))) 447 return (error); 448 449 if (rio_list == rqp) 450 rio_list = rqp->rq_next; 451 else { 452 for (tmp = rio_list; tmp != NULL; tmp = tmp->rq_next) 453 if (tmp->rq_next == rqp) { 454 tmp->rq_next = rqp->rq_next; 455 break; 456 } 457 if (tmp == NULL) 458 printf("rio_detach: no state found in rio_list!\n"); 459 } 460 461 rio_destroy(rqp->rq_rio); 462 FREE(rqp->rq_q, M_DEVBUF); 463 FREE(rqp, M_DEVBUF); 464 return (error); 465 } 466 467 /* 468 * rio support routines 469 */ 470 static int 471 rio_request(ifq, req, arg) 472 struct ifaltq *ifq; 473 int req; 474 void *arg; 475 { 476 rio_queue_t *rqp = (rio_queue_t *)ifq->altq_disc; 477 478 switch (req) { 479 case ALTRQ_PURGE: 480 _flushq(rqp->rq_q); 481 if (ALTQ_IS_ENABLED(ifq)) 482 ifq->ifq_len = 0; 483 break; 484 } 485 return (0); 486 } 487 488 489 rio_t * 490 rio_alloc(weight, params, flags, pkttime) 491 int weight; 492 struct redparams *params; 493 int flags, pkttime; 494 { 495 rio_t *rp; 496 int w, i; 497 int npkts_per_sec; 498 499 MALLOC(rp, rio_t *, sizeof(rio_t), M_DEVBUF, M_WAITOK); 500 if (rp == NULL) 501 return (NULL); 502 bzero(rp, sizeof(rio_t)); 503 504 rp->rio_flags = flags; 505 if (pkttime == 0) 506 /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */ 507 rp->rio_pkttime = 800; 508 else 509 rp->rio_pkttime = pkttime; 510 511 if (weight != 0) 512 rp->rio_weight = weight; 513 else { 514 /* use derfault */ 515 rp->rio_weight = W_WEIGHT; 516 517 /* when the link is very slow, adjust red parameters */ 518 npkts_per_sec = 1000000 / rp->rio_pkttime; 519 if (npkts_per_sec < 50) { 520 /* up to about 400Kbps */ 521 rp->rio_weight = W_WEIGHT_2; 522 } else if (npkts_per_sec < 300) { 523 /* up to about 2.4Mbps */ 524 rp->rio_weight = W_WEIGHT_1; 525 } 526 } 527 528 /* calculate wshift. weight must be power of 2 */ 529 w = rp->rio_weight; 530 for (i = 0; w > 1; i++) 531 w = w >> 1; 532 rp->rio_wshift = i; 533 w = 1 << rp->rio_wshift; 534 if (w != rp->rio_weight) { 535 printf("invalid weight value %d for red! use %d\n", 536 rp->rio_weight, w); 537 rp->rio_weight = w; 538 } 539 540 /* allocate weight table */ 541 rp->rio_wtab = wtab_alloc(rp->rio_weight); 542 543 for (i = 0; i < RIO_NDROPPREC; i++) { 544 struct dropprec_state *prec = &rp->rio_precstate[i]; 545 546 prec->avg = 0; 547 prec->idle = 1; 548 549 if (params == NULL || params[i].inv_pmax == 0) 550 prec->inv_pmax = default_rio_params[i].inv_pmax; 551 else 552 prec->inv_pmax = params[i].inv_pmax; 553 if (params == NULL || params[i].th_min == 0) 554 prec->th_min = default_rio_params[i].th_min; 555 else 556 prec->th_min = params[i].th_min; 557 if (params == NULL || params[i].th_max == 0) 558 prec->th_max = default_rio_params[i].th_max; 559 else 560 prec->th_max = params[i].th_max; 561 562 /* 563 * th_min_s and th_max_s are scaled versions of th_min 564 * and th_max to be compared with avg. 565 */ 566 prec->th_min_s = prec->th_min << (rp->rio_wshift + FP_SHIFT); 567 prec->th_max_s = prec->th_max << (rp->rio_wshift + FP_SHIFT); 568 569 /* 570 * precompute probability denominator 571 * probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point 572 */ 573 prec->probd = (2 * (prec->th_max - prec->th_min) 574 * prec->inv_pmax) << FP_SHIFT; 575 576 microtime(&prec->last); 577 } 578 579 return (rp); 580 } 581 582 void 583 rio_destroy(rp) 584 rio_t *rp; 585 { 586 wtab_destroy(rp->rio_wtab); 587 FREE(rp, M_DEVBUF); 588 } 589 590 void 591 rio_getstats(rp, sp) 592 rio_t *rp; 593 struct redstats *sp; 594 { 595 int i; 596 597 for (i = 0; i < RIO_NDROPPREC; i++) { 598 bcopy(&rp->q_stats[i], sp, sizeof(struct redstats)); 599 sp->q_avg = rp->rio_precstate[i].avg >> rp->rio_wshift; 600 sp++; 601 } 602 } 603 604 /* 605 * enqueue routine: 606 * 607 * returns: 0 when successfully queued. 608 * ENOBUFS when drop occurs. 609 */ 610 static int 611 rio_enqueue(ifq, m, pktattr) 612 struct ifaltq *ifq; 613 struct mbuf *m; 614 struct altq_pktattr *pktattr; 615 { 616 rio_queue_t *rqp = (rio_queue_t *)ifq->altq_disc; 617 int error = 0; 618 619 if (rio_addq(rqp->rq_rio, rqp->rq_q, m, pktattr) == 0) 620 ifq->ifq_len++; 621 else 622 error = ENOBUFS; 623 return error; 624 } 625 626 #if (RIO_NDROPPREC == 3) 627 /* 628 * internally, a drop precedence value is converted to an index 629 * starting from 0. 630 */ 631 static int 632 dscp2index(u_int8_t dscp) 633 { 634 int dpindex = dscp & AF_DROPPRECMASK; 635 636 if (dpindex == 0) 637 return (0); 638 return ((dpindex >> 3) - 1); 639 } 640 #endif 641 642 #if 1 643 /* 644 * kludge: when a packet is dequeued, we need to know its drop precedence 645 * in order to keep the queue length of each drop precedence. 646 * use m_pkthdr.rcvif to pass this info. 647 */ 648 #define RIOM_SET_PRECINDEX(m, idx) \ 649 do { (m)->m_pkthdr.rcvif = (struct ifnet *)((long)(idx)); } while (0) 650 #define RIOM_GET_PRECINDEX(m) \ 651 ({ long idx; idx = (long)((m)->m_pkthdr.rcvif); \ 652 (m)->m_pkthdr.rcvif = NULL; idx; }) 653 #endif 654 655 int 656 rio_addq(rp, q, m, pktattr) 657 rio_t *rp; 658 class_queue_t *q; 659 struct mbuf *m; 660 struct altq_pktattr *pktattr; 661 { 662 int avg, droptype; 663 u_int8_t dsfield, odsfield; 664 int dpindex, i, n, t; 665 struct timeval now; 666 struct dropprec_state *prec; 667 668 dsfield = odsfield = read_dsfield(m, pktattr); 669 dpindex = dscp2index(dsfield); 670 671 /* 672 * update avg of the precedence states whose drop precedence 673 * is larger than or equal to the drop precedence of the packet 674 */ 675 now.tv_sec = 0; 676 for (i = dpindex; i < RIO_NDROPPREC; i++) { 677 prec = &rp->rio_precstate[i]; 678 avg = prec->avg; 679 if (prec->idle) { 680 prec->idle = 0; 681 if (now.tv_sec == 0) 682 microtime(&now); 683 t = (now.tv_sec - prec->last.tv_sec); 684 if (t > 60) 685 avg = 0; 686 else { 687 t = t * 1000000 + 688 (now.tv_usec - prec->last.tv_usec); 689 n = t / rp->rio_pkttime; 690 /* calculate (avg = (1 - Wq)^n * avg) */ 691 if (n > 0) 692 avg = (avg >> FP_SHIFT) * 693 pow_w(rp->rio_wtab, n); 694 } 695 } 696 697 /* run estimator. (avg is scaled by WEIGHT in fixed-point) */ 698 avg += (prec->qlen << FP_SHIFT) - (avg >> rp->rio_wshift); 699 prec->avg = avg; /* save the new value */ 700 /* 701 * count keeps a tally of arriving traffic that has not 702 * been dropped. 703 */ 704 prec->count++; 705 } 706 707 prec = &rp->rio_precstate[dpindex]; 708 avg = prec->avg; 709 710 /* see if we drop early */ 711 droptype = DTYPE_NODROP; 712 if (avg >= prec->th_min_s && prec->qlen > 1) { 713 if (avg >= prec->th_max_s) { 714 /* avg >= th_max: forced drop */ 715 droptype = DTYPE_FORCED; 716 } else if (prec->old == 0) { 717 /* first exceeds th_min */ 718 prec->count = 1; 719 prec->old = 1; 720 } else if (drop_early((avg - prec->th_min_s) >> rp->rio_wshift, 721 prec->probd, prec->count)) { 722 /* unforced drop by red */ 723 droptype = DTYPE_EARLY; 724 } 725 } else { 726 /* avg < th_min */ 727 prec->old = 0; 728 } 729 730 /* 731 * if the queue length hits the hard limit, it's a forced drop. 732 */ 733 if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q)) 734 droptype = DTYPE_FORCED; 735 736 if (droptype != DTYPE_NODROP) { 737 /* always drop incoming packet (as opposed to randomdrop) */ 738 for (i = dpindex; i < RIO_NDROPPREC; i++) 739 rp->rio_precstate[i].count = 0; 740 #ifdef RIO_STATS 741 if (droptype == DTYPE_EARLY) 742 rp->q_stats[dpindex].drop_unforced++; 743 else 744 rp->q_stats[dpindex].drop_forced++; 745 PKTCNTR_ADD(&rp->q_stats[dpindex].drop_cnt, m_pktlen(m)); 746 #endif 747 m_freem(m); 748 return (-1); 749 } 750 751 for (i = dpindex; i < RIO_NDROPPREC; i++) 752 rp->rio_precstate[i].qlen++; 753 754 /* save drop precedence index in mbuf hdr */ 755 RIOM_SET_PRECINDEX(m, dpindex); 756 757 if (rp->rio_flags & RIOF_CLEARDSCP) 758 dsfield &= ~DSCP_MASK; 759 760 if (dsfield != odsfield) 761 write_dsfield(m, pktattr, dsfield); 762 763 _addq(q, m); 764 765 #ifdef RIO_STATS 766 PKTCNTR_ADD(&rp->q_stats[dpindex].xmit_cnt, m_pktlen(m)); 767 #endif 768 return (0); 769 } 770 771 /* 772 * dequeue routine: 773 * must be called in splimp. 774 * 775 * returns: mbuf dequeued. 776 * NULL when no packet is available in the queue. 777 */ 778 779 static struct mbuf * 780 rio_dequeue(ifq, op) 781 struct ifaltq *ifq; 782 int op; 783 { 784 rio_queue_t *rqp = (rio_queue_t *)ifq->altq_disc; 785 struct mbuf *m = NULL; 786 787 if (op == ALTDQ_POLL) 788 return qhead(rqp->rq_q); 789 790 m = rio_getq(rqp->rq_rio, rqp->rq_q); 791 if (m != NULL) 792 ifq->ifq_len--; 793 return m; 794 } 795 796 struct mbuf * 797 rio_getq(rp, q) 798 rio_t *rp; 799 class_queue_t *q; 800 { 801 struct mbuf *m; 802 int dpindex, i; 803 804 if ((m = _getq(q)) == NULL) 805 return NULL; 806 807 dpindex = RIOM_GET_PRECINDEX(m); 808 for (i = dpindex; i < RIO_NDROPPREC; i++) { 809 if (--rp->rio_precstate[i].qlen == 0) { 810 if (rp->rio_precstate[i].idle == 0) { 811 rp->rio_precstate[i].idle = 1; 812 microtime(&rp->rio_precstate[i].last); 813 } 814 } 815 } 816 return (m); 817 } 818 819 #ifdef KLD_MODULE 820 821 static struct altqsw rio_sw = 822 {"rio", rioopen, rioclose, rioioctl}; 823 824 ALTQ_MODULE(altq_rio, ALTQT_RIO, &rio_sw); 825 826 #endif /* KLD_MODULE */ 827 828 #endif /* ALTQ_RIO */ 829
Indexes created Mon Sep 29 03:10:08 GMT 2025