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