altq_rio.c revision 1.8.10.2
1 /* $NetBSD: altq_rio.c,v 1.8.10.2 2006/03/10 13:29:35 elad 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.8.10.2 2006/03/10 13:29:35 elad 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 = kauth_authorize_generic(p->p_cred, 250 KAUTH_GENERIC_ISSUSER, 251 &p->p_acflag)) != 0) 252 return (error); 253 #endif 254 break; 255 } 256 257 switch (cmd) { 258 259 case RIO_ENABLE: 260 ifacep = (struct rio_interface *)addr; 261 if ((rqp = altq_lookup(ifacep->rio_ifname, ALTQT_RIO)) == NULL) { 262 error = EBADF; 263 break; 264 } 265 error = altq_enable(rqp->rq_ifq); 266 break; 267 268 case RIO_DISABLE: 269 ifacep = (struct rio_interface *)addr; 270 if ((rqp = altq_lookup(ifacep->rio_ifname, ALTQT_RIO)) == NULL) { 271 error = EBADF; 272 break; 273 } 274 error = altq_disable(rqp->rq_ifq); 275 break; 276 277 case RIO_IF_ATTACH: 278 ifp = ifunit(((struct rio_interface *)addr)->rio_ifname); 279 if (ifp == NULL) { 280 error = ENXIO; 281 break; 282 } 283 284 /* allocate and initialize rio_queue_t */ 285 MALLOC(rqp, rio_queue_t *, sizeof(rio_queue_t), M_DEVBUF, M_WAITOK); 286 if (rqp == NULL) { 287 error = ENOMEM; 288 break; 289 } 290 (void)memset(rqp, 0, sizeof(rio_queue_t)); 291 292 MALLOC(rqp->rq_q, class_queue_t *, sizeof(class_queue_t), 293 M_DEVBUF, M_WAITOK); 294 if (rqp->rq_q == NULL) { 295 FREE(rqp, M_DEVBUF); 296 error = ENOMEM; 297 break; 298 } 299 (void)memset(rqp->rq_q, 0, sizeof(class_queue_t)); 300 301 rqp->rq_rio = rio_alloc(0, NULL, 0, 0); 302 if (rqp->rq_rio == NULL) { 303 FREE(rqp->rq_q, M_DEVBUF); 304 FREE(rqp, M_DEVBUF); 305 error = ENOMEM; 306 break; 307 } 308 309 rqp->rq_ifq = &ifp->if_snd; 310 qtail(rqp->rq_q) = NULL; 311 qlen(rqp->rq_q) = 0; 312 qlimit(rqp->rq_q) = RIO_LIMIT; 313 qtype(rqp->rq_q) = Q_RIO; 314 315 /* 316 * set RIO to this ifnet structure. 317 */ 318 error = altq_attach(rqp->rq_ifq, ALTQT_RIO, rqp, 319 rio_enqueue, rio_dequeue, rio_request, 320 NULL, NULL); 321 if (error) { 322 rio_destroy(rqp->rq_rio); 323 FREE(rqp->rq_q, M_DEVBUF); 324 FREE(rqp, M_DEVBUF); 325 break; 326 } 327 328 /* add this state to the rio list */ 329 rqp->rq_next = rio_list; 330 rio_list = rqp; 331 break; 332 333 case RIO_IF_DETACH: 334 ifacep = (struct rio_interface *)addr; 335 if ((rqp = altq_lookup(ifacep->rio_ifname, ALTQT_RIO)) == NULL) { 336 error = EBADF; 337 break; 338 } 339 error = rio_detach(rqp); 340 break; 341 342 case RIO_GETSTATS: 343 do { 344 struct rio_stats *q_stats; 345 rio_t *rp; 346 int i; 347 348 q_stats = (struct rio_stats *)addr; 349 if ((rqp = altq_lookup(q_stats->iface.rio_ifname, 350 ALTQT_RIO)) == NULL) { 351 error = EBADF; 352 break; 353 } 354 355 rp = rqp->rq_rio; 356 357 q_stats->q_limit = qlimit(rqp->rq_q); 358 q_stats->weight = rp->rio_weight; 359 q_stats->flags = rp->rio_flags; 360 361 for (i = 0; i < RIO_NDROPPREC; i++) { 362 q_stats->q_len[i] = rp->rio_precstate[i].qlen; 363 (void)memcpy(&q_stats->q_stats[i], 364 &rp->q_stats[i], sizeof(struct redstats)); 365 q_stats->q_stats[i].q_avg = 366 rp->rio_precstate[i].avg >> rp->rio_wshift; 367 368 q_stats->q_params[i].inv_pmax 369 = rp->rio_precstate[i].inv_pmax; 370 q_stats->q_params[i].th_min 371 = rp->rio_precstate[i].th_min; 372 q_stats->q_params[i].th_max 373 = rp->rio_precstate[i].th_max; 374 } 375 } while (0); 376 break; 377 378 case RIO_CONFIG: 379 do { 380 struct rio_conf *fc; 381 rio_t *new; 382 int s, limit, i; 383 384 fc = (struct rio_conf *)addr; 385 if ((rqp = altq_lookup(fc->iface.rio_ifname, 386 ALTQT_RIO)) == NULL) { 387 error = EBADF; 388 break; 389 } 390 391 new = rio_alloc(fc->rio_weight, &fc->q_params[0], 392 fc->rio_flags, fc->rio_pkttime); 393 if (new == NULL) { 394 error = ENOMEM; 395 break; 396 } 397 398 s = splnet(); 399 _flushq(rqp->rq_q); 400 limit = fc->rio_limit; 401 if (limit < fc->q_params[RIO_NDROPPREC-1].th_max) 402 limit = fc->q_params[RIO_NDROPPREC-1].th_max; 403 qlimit(rqp->rq_q) = limit; 404 405 rio_destroy(rqp->rq_rio); 406 rqp->rq_rio = new; 407 408 splx(s); 409 410 /* write back new values */ 411 fc->rio_limit = limit; 412 for (i = 0; i < RIO_NDROPPREC; i++) { 413 fc->q_params[i].inv_pmax = 414 rqp->rq_rio->rio_precstate[i].inv_pmax; 415 fc->q_params[i].th_min = 416 rqp->rq_rio->rio_precstate[i].th_min; 417 fc->q_params[i].th_max = 418 rqp->rq_rio->rio_precstate[i].th_max; 419 } 420 } while (0); 421 break; 422 423 case RIO_SETDEFAULTS: 424 do { 425 struct redparams *rp; 426 int i; 427 428 rp = (struct redparams *)addr; 429 for (i = 0; i < RIO_NDROPPREC; i++) 430 default_rio_params[i] = rp[i]; 431 } while (0); 432 break; 433 434 default: 435 error = EINVAL; 436 break; 437 } 438 439 return error; 440 } 441 442 static int 443 rio_detach(rqp) 444 rio_queue_t *rqp; 445 { 446 rio_queue_t *tmp; 447 int error = 0; 448 449 if (ALTQ_IS_ENABLED(rqp->rq_ifq)) 450 altq_disable(rqp->rq_ifq); 451 452 if ((error = altq_detach(rqp->rq_ifq))) 453 return (error); 454 455 if (rio_list == rqp) 456 rio_list = rqp->rq_next; 457 else { 458 for (tmp = rio_list; tmp != NULL; tmp = tmp->rq_next) 459 if (tmp->rq_next == rqp) { 460 tmp->rq_next = rqp->rq_next; 461 break; 462 } 463 if (tmp == NULL) 464 printf("rio_detach: no state found in rio_list!\n"); 465 } 466 467 rio_destroy(rqp->rq_rio); 468 FREE(rqp->rq_q, M_DEVBUF); 469 FREE(rqp, M_DEVBUF); 470 return (error); 471 } 472 473 /* 474 * rio support routines 475 */ 476 static int 477 rio_request(ifq, req, arg) 478 struct ifaltq *ifq; 479 int req; 480 void *arg; 481 { 482 rio_queue_t *rqp = (rio_queue_t *)ifq->altq_disc; 483 484 switch (req) { 485 case ALTRQ_PURGE: 486 _flushq(rqp->rq_q); 487 if (ALTQ_IS_ENABLED(ifq)) 488 ifq->ifq_len = 0; 489 break; 490 } 491 return (0); 492 } 493 494 495 rio_t * 496 rio_alloc(weight, params, flags, pkttime) 497 int weight; 498 struct redparams *params; 499 int flags, pkttime; 500 { 501 rio_t *rp; 502 int w, i; 503 int npkts_per_sec; 504 505 MALLOC(rp, rio_t *, sizeof(rio_t), M_DEVBUF, M_WAITOK); 506 if (rp == NULL) 507 return (NULL); 508 (void)memset(rp, 0, sizeof(rio_t)); 509 510 rp->rio_flags = flags; 511 if (pkttime == 0) 512 /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */ 513 rp->rio_pkttime = 800; 514 else 515 rp->rio_pkttime = pkttime; 516 517 if (weight != 0) 518 rp->rio_weight = weight; 519 else { 520 /* use derfault */ 521 rp->rio_weight = W_WEIGHT; 522 523 /* when the link is very slow, adjust red parameters */ 524 npkts_per_sec = 1000000 / rp->rio_pkttime; 525 if (npkts_per_sec < 50) { 526 /* up to about 400Kbps */ 527 rp->rio_weight = W_WEIGHT_2; 528 } else if (npkts_per_sec < 300) { 529 /* up to about 2.4Mbps */ 530 rp->rio_weight = W_WEIGHT_1; 531 } 532 } 533 534 /* calculate wshift. weight must be power of 2 */ 535 w = rp->rio_weight; 536 for (i = 0; w > 1; i++) 537 w = w >> 1; 538 rp->rio_wshift = i; 539 w = 1 << rp->rio_wshift; 540 if (w != rp->rio_weight) { 541 printf("invalid weight value %d for red! use %d\n", 542 rp->rio_weight, w); 543 rp->rio_weight = w; 544 } 545 546 /* allocate weight table */ 547 rp->rio_wtab = wtab_alloc(rp->rio_weight); 548 549 for (i = 0; i < RIO_NDROPPREC; i++) { 550 struct dropprec_state *prec = &rp->rio_precstate[i]; 551 552 prec->avg = 0; 553 prec->idle = 1; 554 555 if (params == NULL || params[i].inv_pmax == 0) 556 prec->inv_pmax = default_rio_params[i].inv_pmax; 557 else 558 prec->inv_pmax = params[i].inv_pmax; 559 if (params == NULL || params[i].th_min == 0) 560 prec->th_min = default_rio_params[i].th_min; 561 else 562 prec->th_min = params[i].th_min; 563 if (params == NULL || params[i].th_max == 0) 564 prec->th_max = default_rio_params[i].th_max; 565 else 566 prec->th_max = params[i].th_max; 567 568 /* 569 * th_min_s and th_max_s are scaled versions of th_min 570 * and th_max to be compared with avg. 571 */ 572 prec->th_min_s = prec->th_min << (rp->rio_wshift + FP_SHIFT); 573 prec->th_max_s = prec->th_max << (rp->rio_wshift + FP_SHIFT); 574 575 /* 576 * precompute probability denominator 577 * probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point 578 */ 579 prec->probd = (2 * (prec->th_max - prec->th_min) 580 * prec->inv_pmax) << FP_SHIFT; 581 582 microtime(&prec->last); 583 } 584 585 return (rp); 586 } 587 588 void 589 rio_destroy(rp) 590 rio_t *rp; 591 { 592 wtab_destroy(rp->rio_wtab); 593 FREE(rp, M_DEVBUF); 594 } 595 596 void 597 rio_getstats(rp, sp) 598 rio_t *rp; 599 struct redstats *sp; 600 { 601 int i; 602 603 for (i = 0; i < RIO_NDROPPREC; i++) { 604 (void)memcpy(sp, &rp->q_stats[i], sizeof(struct redstats)); 605 sp->q_avg = rp->rio_precstate[i].avg >> rp->rio_wshift; 606 sp++; 607 } 608 } 609 610 /* 611 * enqueue routine: 612 * 613 * returns: 0 when successfully queued. 614 * ENOBUFS when drop occurs. 615 */ 616 static int 617 rio_enqueue(ifq, m, pktattr) 618 struct ifaltq *ifq; 619 struct mbuf *m; 620 struct altq_pktattr *pktattr; 621 { 622 rio_queue_t *rqp = (rio_queue_t *)ifq->altq_disc; 623 int error = 0; 624 625 if (rio_addq(rqp->rq_rio, rqp->rq_q, m, pktattr) == 0) 626 ifq->ifq_len++; 627 else 628 error = ENOBUFS; 629 return error; 630 } 631 632 #if (RIO_NDROPPREC == 3) 633 /* 634 * internally, a drop precedence value is converted to an index 635 * starting from 0. 636 */ 637 static int 638 dscp2index(u_int8_t dscp) 639 { 640 int dpindex = dscp & AF_DROPPRECMASK; 641 642 if (dpindex == 0) 643 return (0); 644 return ((dpindex >> 3) - 1); 645 } 646 #endif 647 648 #if 1 649 /* 650 * kludge: when a packet is dequeued, we need to know its drop precedence 651 * in order to keep the queue length of each drop precedence. 652 * use m_pkthdr.rcvif to pass this info. 653 */ 654 #define RIOM_SET_PRECINDEX(m, idx) \ 655 do { (m)->m_pkthdr.rcvif = (struct ifnet *)((long)(idx)); } while (0) 656 #define RIOM_GET_PRECINDEX(m) \ 657 ({ long idx; idx = (long)((m)->m_pkthdr.rcvif); \ 658 (m)->m_pkthdr.rcvif = NULL; idx; }) 659 #endif 660 661 int 662 rio_addq(rp, q, m, pktattr) 663 rio_t *rp; 664 class_queue_t *q; 665 struct mbuf *m; 666 struct altq_pktattr *pktattr; 667 { 668 int avg, droptype; 669 u_int8_t dsfield, odsfield; 670 int dpindex, i, n, t; 671 struct timeval now; 672 struct dropprec_state *prec; 673 674 dsfield = odsfield = read_dsfield(m, pktattr); 675 dpindex = dscp2index(dsfield); 676 677 /* 678 * update avg of the precedence states whose drop precedence 679 * is larger than or equal to the drop precedence of the packet 680 */ 681 now.tv_sec = 0; 682 for (i = dpindex; i < RIO_NDROPPREC; i++) { 683 prec = &rp->rio_precstate[i]; 684 avg = prec->avg; 685 if (prec->idle) { 686 prec->idle = 0; 687 if (now.tv_sec == 0) 688 microtime(&now); 689 t = (now.tv_sec - prec->last.tv_sec); 690 if (t > 60) 691 avg = 0; 692 else { 693 t = t * 1000000 + 694 (now.tv_usec - prec->last.tv_usec); 695 n = t / rp->rio_pkttime; 696 /* calculate (avg = (1 - Wq)^n * avg) */ 697 if (n > 0) 698 avg = (avg >> FP_SHIFT) * 699 pow_w(rp->rio_wtab, n); 700 } 701 } 702 703 /* run estimator. (avg is scaled by WEIGHT in fixed-point) */ 704 avg += (prec->qlen << FP_SHIFT) - (avg >> rp->rio_wshift); 705 prec->avg = avg; /* save the new value */ 706 /* 707 * count keeps a tally of arriving traffic that has not 708 * been dropped. 709 */ 710 prec->count++; 711 } 712 713 prec = &rp->rio_precstate[dpindex]; 714 avg = prec->avg; 715 716 /* see if we drop early */ 717 droptype = DTYPE_NODROP; 718 if (avg >= prec->th_min_s && prec->qlen > 1) { 719 if (avg >= prec->th_max_s) { 720 /* avg >= th_max: forced drop */ 721 droptype = DTYPE_FORCED; 722 } else if (prec->old == 0) { 723 /* first exceeds th_min */ 724 prec->count = 1; 725 prec->old = 1; 726 } else if (drop_early((avg - prec->th_min_s) >> rp->rio_wshift, 727 prec->probd, prec->count)) { 728 /* unforced drop by red */ 729 droptype = DTYPE_EARLY; 730 } 731 } else { 732 /* avg < th_min */ 733 prec->old = 0; 734 } 735 736 /* 737 * if the queue length hits the hard limit, it's a forced drop. 738 */ 739 if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q)) 740 droptype = DTYPE_FORCED; 741 742 if (droptype != DTYPE_NODROP) { 743 /* always drop incoming packet (as opposed to randomdrop) */ 744 for (i = dpindex; i < RIO_NDROPPREC; i++) 745 rp->rio_precstate[i].count = 0; 746 #ifdef RIO_STATS 747 if (droptype == DTYPE_EARLY) 748 rp->q_stats[dpindex].drop_unforced++; 749 else 750 rp->q_stats[dpindex].drop_forced++; 751 PKTCNTR_ADD(&rp->q_stats[dpindex].drop_cnt, m_pktlen(m)); 752 #endif 753 m_freem(m); 754 return (-1); 755 } 756 757 for (i = dpindex; i < RIO_NDROPPREC; i++) 758 rp->rio_precstate[i].qlen++; 759 760 /* save drop precedence index in mbuf hdr */ 761 RIOM_SET_PRECINDEX(m, dpindex); 762 763 if (rp->rio_flags & RIOF_CLEARDSCP) 764 dsfield &= ~DSCP_MASK; 765 766 if (dsfield != odsfield) 767 write_dsfield(m, pktattr, dsfield); 768 769 _addq(q, m); 770 771 #ifdef RIO_STATS 772 PKTCNTR_ADD(&rp->q_stats[dpindex].xmit_cnt, m_pktlen(m)); 773 #endif 774 return (0); 775 } 776 777 /* 778 * dequeue routine: 779 * must be called in splnet. 780 * 781 * returns: mbuf dequeued. 782 * NULL when no packet is available in the queue. 783 */ 784 785 static struct mbuf * 786 rio_dequeue(ifq, op) 787 struct ifaltq *ifq; 788 int op; 789 { 790 rio_queue_t *rqp = (rio_queue_t *)ifq->altq_disc; 791 struct mbuf *m = NULL; 792 793 if (op == ALTDQ_POLL) 794 return qhead(rqp->rq_q); 795 796 m = rio_getq(rqp->rq_rio, rqp->rq_q); 797 if (m != NULL) 798 ifq->ifq_len--; 799 return m; 800 } 801 802 struct mbuf * 803 rio_getq(rp, q) 804 rio_t *rp; 805 class_queue_t *q; 806 { 807 struct mbuf *m; 808 int dpindex, i; 809 810 if ((m = _getq(q)) == NULL) 811 return NULL; 812 813 dpindex = RIOM_GET_PRECINDEX(m); 814 for (i = dpindex; i < RIO_NDROPPREC; i++) { 815 if (--rp->rio_precstate[i].qlen == 0) { 816 if (rp->rio_precstate[i].idle == 0) { 817 rp->rio_precstate[i].idle = 1; 818 microtime(&rp->rio_precstate[i].last); 819 } 820 } 821 } 822 return (m); 823 } 824 825 #ifdef KLD_MODULE 826 827 static struct altqsw rio_sw = 828 {"rio", rioopen, rioclose, rioioctl}; 829 830 ALTQ_MODULE(altq_rio, ALTQT_RIO, &rio_sw); 831 832 #endif /* KLD_MODULE */ 833 834 #endif /* ALTQ_RIO */ 835
Indexes created Thu Oct 23 22:10:10 GMT 2025