1 /*- 2 * Copyright (C) 2000-2003 3 * Sony Computer Science Laboratories Inc. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 * 26 * $KAME: altq_priq.c,v 1.11 2003/09/17 14:23:25 kjc Exp $ 27 * $FreeBSD$ 28 */ 29 /* 30 * priority queue 31 */ 32 33 #include "opt_altq.h" 34 #include "opt_inet.h" 35 #include "opt_inet6.h" 36 37 #ifdef ALTQ_PRIQ /* priq is enabled by ALTQ_PRIQ option in opt_altq.h */ 38 39 #include <sys/param.h> 40 #include <sys/malloc.h> 41 #include <sys/mbuf.h> 42 #include <sys/socket.h> 43 #include <sys/sockio.h> 44 #include <sys/systm.h> 45 #include <sys/proc.h> 46 #include <sys/errno.h> 47 #include <sys/kernel.h> 48 #include <sys/queue.h> 49 50 #include <net/if.h> 51 #include <net/if_var.h> 52 #include <netinet/in.h> 53 54 #include <netpfil/pf/pf.h> 55 #include <netpfil/pf/pf_altq.h> 56 #include <netpfil/pf/pf_mtag.h> 57 #include <net/altq/altq.h> 58 #include <net/altq/altq_priq.h> 59 60 /* 61 * function prototypes 62 */ 63 static int priq_clear_interface(struct priq_if *); 64 static int priq_request(struct ifaltq *, int, void *); 65 static void priq_purge(struct priq_if *); 66 static struct priq_class *priq_class_create(struct priq_if *, int, int, int, 67 int); 68 static int priq_class_destroy(struct priq_class *); 69 static int priq_enqueue(struct ifaltq *, struct mbuf *, struct altq_pktattr *); 70 static struct mbuf *priq_dequeue(struct ifaltq *, int); 71 72 static int priq_addq(struct priq_class *, struct mbuf *); 73 static struct mbuf *priq_getq(struct priq_class *); 74 static struct mbuf *priq_pollq(struct priq_class *); 75 static void priq_purgeq(struct priq_class *); 76 77 static void get_class_stats(struct priq_classstats *, struct priq_class *); 78 static struct priq_class *clh_to_clp(struct priq_if *, u_int32_t); 79 80 int 81 priq_pfattach(struct pf_altq *a) 82 { 83 struct ifnet *ifp; 84 int s, error; 85 86 if ((ifp = ifunit(a->ifname)) == NULL || a->altq_disc == NULL) 87 return (EINVAL); 88 s = splnet(); 89 error = altq_attach(&ifp->if_snd, ALTQT_PRIQ, a->altq_disc, 90 priq_enqueue, priq_dequeue, priq_request, NULL, NULL); 91 splx(s); 92 return (error); 93 } 94 95 int 96 priq_add_altq(struct ifnet * ifp, struct pf_altq *a) 97 { 98 struct priq_if *pif; 99 100 if (ifp == NULL) 101 return (EINVAL); 102 if (!ALTQ_IS_READY(&ifp->if_snd)) 103 return (ENODEV); 104 105 pif = malloc(sizeof(struct priq_if), M_DEVBUF, M_NOWAIT | M_ZERO); 106 if (pif == NULL) 107 return (ENOMEM); 108 pif->pif_bandwidth = a->ifbandwidth; 109 pif->pif_maxpri = -1; 110 pif->pif_ifq = &ifp->if_snd; 111 112 /* keep the state in pf_altq */ 113 a->altq_disc = pif; 114 115 return (0); 116 } 117 118 int 119 priq_remove_altq(struct pf_altq *a) 120 { 121 struct priq_if *pif; 122 123 if ((pif = a->altq_disc) == NULL) 124 return (EINVAL); 125 a->altq_disc = NULL; 126 127 (void)priq_clear_interface(pif); 128 129 free(pif, M_DEVBUF); 130 return (0); 131 } 132 133 int 134 priq_add_queue(struct pf_altq *a) 135 { 136 struct priq_if *pif; 137 struct priq_class *cl; 138 139 if ((pif = a->altq_disc) == NULL) 140 return (EINVAL); 141 142 /* check parameters */ 143 if (a->priority >= PRIQ_MAXPRI) 144 return (EINVAL); 145 if (a->qid == 0) 146 return (EINVAL); 147 if (pif->pif_classes[a->priority] != NULL) 148 return (EBUSY); 149 if (clh_to_clp(pif, a->qid) != NULL) 150 return (EBUSY); 151 152 cl = priq_class_create(pif, a->priority, a->qlimit, 153 a->pq_u.priq_opts.flags, a->qid); 154 if (cl == NULL) 155 return (ENOMEM); 156 157 return (0); 158 } 159 160 int 161 priq_remove_queue(struct pf_altq *a) 162 { 163 struct priq_if *pif; 164 struct priq_class *cl; 165 166 if ((pif = a->altq_disc) == NULL) 167 return (EINVAL); 168 169 if ((cl = clh_to_clp(pif, a->qid)) == NULL) 170 return (EINVAL); 171 172 return (priq_class_destroy(cl)); 173 } 174 175 int 176 priq_getqstats(struct pf_altq *a, void *ubuf, int *nbytes, int version) 177 { 178 struct priq_if *pif; 179 struct priq_class *cl; 180 struct priq_classstats stats; 181 int error = 0; 182 183 if ((pif = altq_lookup(a->ifname, ALTQT_PRIQ)) == NULL) 184 return (EBADF); 185 186 if ((cl = clh_to_clp(pif, a->qid)) == NULL) 187 return (EINVAL); 188 189 if (*nbytes < sizeof(stats)) 190 return (EINVAL); 191 192 get_class_stats(&stats, cl); 193 194 if ((error = copyout((caddr_t)&stats, ubuf, sizeof(stats))) != 0) 195 return (error); 196 *nbytes = sizeof(stats); 197 return (0); 198 } 199 200 /* 201 * bring the interface back to the initial state by discarding 202 * all the filters and classes. 203 */ 204 static int 205 priq_clear_interface(struct priq_if *pif) 206 { 207 struct priq_class *cl; 208 int pri; 209 210 #ifdef ALTQ3_CLFIER_COMPAT 211 /* free the filters for this interface */ 212 acc_discard_filters(&pif->pif_classifier, NULL, 1); 213 #endif 214 215 /* clear out the classes */ 216 for (pri = 0; pri <= pif->pif_maxpri; pri++) 217 if ((cl = pif->pif_classes[pri]) != NULL) 218 priq_class_destroy(cl); 219 220 return (0); 221 } 222 223 static int 224 priq_request(struct ifaltq *ifq, int req, void *arg) 225 { 226 struct priq_if *pif = (struct priq_if *)ifq->altq_disc; 227 228 IFQ_LOCK_ASSERT(ifq); 229 230 switch (req) { 231 case ALTRQ_PURGE: 232 priq_purge(pif); 233 break; 234 } 235 return (0); 236 } 237 238 /* discard all the queued packets on the interface */ 239 static void 240 priq_purge(struct priq_if *pif) 241 { 242 struct priq_class *cl; 243 int pri; 244 245 for (pri = 0; pri <= pif->pif_maxpri; pri++) { 246 if ((cl = pif->pif_classes[pri]) != NULL && !qempty(cl->cl_q)) 247 priq_purgeq(cl); 248 } 249 if (ALTQ_IS_ENABLED(pif->pif_ifq)) 250 pif->pif_ifq->ifq_len = 0; 251 } 252 253 static struct priq_class * 254 priq_class_create(struct priq_if *pif, int pri, int qlimit, int flags, int qid) 255 { 256 struct priq_class *cl; 257 int s; 258 259 #ifndef ALTQ_RED 260 if (flags & PRCF_RED) { 261 #ifdef ALTQ_DEBUG 262 printf("priq_class_create: RED not configured for PRIQ!\n"); 263 #endif 264 return (NULL); 265 } 266 #endif 267 #ifndef ALTQ_CODEL 268 if (flags & PRCF_CODEL) { 269 #ifdef ALTQ_DEBUG 270 printf("priq_class_create: CODEL not configured for PRIQ!\n"); 271 #endif 272 return (NULL); 273 } 274 #endif 275 276 if ((cl = pif->pif_classes[pri]) != NULL) { 277 /* modify the class instead of creating a new one */ 278 s = splnet(); 279 IFQ_LOCK(cl->cl_pif->pif_ifq); 280 if (!qempty(cl->cl_q)) 281 priq_purgeq(cl); 282 IFQ_UNLOCK(cl->cl_pif->pif_ifq); 283 splx(s); 284 #ifdef ALTQ_RIO 285 if (q_is_rio(cl->cl_q)) 286 rio_destroy((rio_t *)cl->cl_red); 287 #endif 288 #ifdef ALTQ_RED 289 if (q_is_red(cl->cl_q)) 290 red_destroy(cl->cl_red); 291 #endif 292 #ifdef ALTQ_CODEL 293 if (q_is_codel(cl->cl_q)) 294 codel_destroy(cl->cl_codel); 295 #endif 296 } else { 297 cl = malloc(sizeof(struct priq_class), M_DEVBUF, 298 M_NOWAIT | M_ZERO); 299 if (cl == NULL) 300 return (NULL); 301 302 cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF, 303 M_NOWAIT | M_ZERO); 304 if (cl->cl_q == NULL) 305 goto err_ret; 306 } 307 308 pif->pif_classes[pri] = cl; 309 if (flags & PRCF_DEFAULTCLASS) 310 pif->pif_default = cl; 311 if (qlimit == 0) 312 qlimit = 50; /* use default */ 313 qlimit(cl->cl_q) = qlimit; 314 qtype(cl->cl_q) = Q_DROPTAIL; 315 qlen(cl->cl_q) = 0; 316 qsize(cl->cl_q) = 0; 317 cl->cl_flags = flags; 318 cl->cl_pri = pri; 319 if (pri > pif->pif_maxpri) 320 pif->pif_maxpri = pri; 321 cl->cl_pif = pif; 322 cl->cl_handle = qid; 323 324 #ifdef ALTQ_RED 325 if (flags & (PRCF_RED|PRCF_RIO)) { 326 int red_flags, red_pkttime; 327 328 red_flags = 0; 329 if (flags & PRCF_ECN) 330 red_flags |= REDF_ECN; 331 #ifdef ALTQ_RIO 332 if (flags & PRCF_CLEARDSCP) 333 red_flags |= RIOF_CLEARDSCP; 334 #endif 335 if (pif->pif_bandwidth < 8) 336 red_pkttime = 1000 * 1000 * 1000; /* 1 sec */ 337 else 338 red_pkttime = (int64_t)pif->pif_ifq->altq_ifp->if_mtu 339 * 1000 * 1000 * 1000 / (pif->pif_bandwidth / 8); 340 #ifdef ALTQ_RIO 341 if (flags & PRCF_RIO) { 342 cl->cl_red = (red_t *)rio_alloc(0, NULL, 343 red_flags, red_pkttime); 344 if (cl->cl_red == NULL) 345 goto err_ret; 346 qtype(cl->cl_q) = Q_RIO; 347 } else 348 #endif 349 if (flags & PRCF_RED) { 350 cl->cl_red = red_alloc(0, 0, 351 qlimit(cl->cl_q) * 10/100, 352 qlimit(cl->cl_q) * 30/100, 353 red_flags, red_pkttime); 354 if (cl->cl_red == NULL) 355 goto err_ret; 356 qtype(cl->cl_q) = Q_RED; 357 } 358 } 359 #endif /* ALTQ_RED */ 360 #ifdef ALTQ_CODEL 361 if (flags & PRCF_CODEL) { 362 cl->cl_codel = codel_alloc(5, 100, 0); 363 if (cl->cl_codel != NULL) 364 qtype(cl->cl_q) = Q_CODEL; 365 } 366 #endif 367 368 return (cl); 369 370 err_ret: 371 if (cl->cl_red != NULL) { 372 #ifdef ALTQ_RIO 373 if (q_is_rio(cl->cl_q)) 374 rio_destroy((rio_t *)cl->cl_red); 375 #endif 376 #ifdef ALTQ_RED 377 if (q_is_red(cl->cl_q)) 378 red_destroy(cl->cl_red); 379 #endif 380 #ifdef ALTQ_CODEL 381 if (q_is_codel(cl->cl_q)) 382 codel_destroy(cl->cl_codel); 383 #endif 384 } 385 if (cl->cl_q != NULL) 386 free(cl->cl_q, M_DEVBUF); 387 free(cl, M_DEVBUF); 388 return (NULL); 389 } 390 391 static int 392 priq_class_destroy(struct priq_class *cl) 393 { 394 struct priq_if *pif; 395 int s, pri; 396 397 s = splnet(); 398 IFQ_LOCK(cl->cl_pif->pif_ifq); 399 400 #ifdef ALTQ3_CLFIER_COMPAT 401 /* delete filters referencing to this class */ 402 acc_discard_filters(&cl->cl_pif->pif_classifier, cl, 0); 403 #endif 404 405 if (!qempty(cl->cl_q)) 406 priq_purgeq(cl); 407 408 pif = cl->cl_pif; 409 pif->pif_classes[cl->cl_pri] = NULL; 410 if (pif->pif_maxpri == cl->cl_pri) { 411 for (pri = cl->cl_pri; pri >= 0; pri--) 412 if (pif->pif_classes[pri] != NULL) { 413 pif->pif_maxpri = pri; 414 break; 415 } 416 if (pri < 0) 417 pif->pif_maxpri = -1; 418 } 419 IFQ_UNLOCK(cl->cl_pif->pif_ifq); 420 splx(s); 421 422 if (cl->cl_red != NULL) { 423 #ifdef ALTQ_RIO 424 if (q_is_rio(cl->cl_q)) 425 rio_destroy((rio_t *)cl->cl_red); 426 #endif 427 #ifdef ALTQ_RED 428 if (q_is_red(cl->cl_q)) 429 red_destroy(cl->cl_red); 430 #endif 431 #ifdef ALTQ_CODEL 432 if (q_is_codel(cl->cl_q)) 433 codel_destroy(cl->cl_codel); 434 #endif 435 } 436 free(cl->cl_q, M_DEVBUF); 437 free(cl, M_DEVBUF); 438 return (0); 439 } 440 441 /* 442 * priq_enqueue is an enqueue function to be registered to 443 * (*altq_enqueue) in struct ifaltq. 444 */ 445 static int 446 priq_enqueue(struct ifaltq *ifq, struct mbuf *m, struct altq_pktattr *pktattr) 447 { 448 struct priq_if *pif = (struct priq_if *)ifq->altq_disc; 449 struct priq_class *cl; 450 struct pf_mtag *t; 451 int len; 452 453 IFQ_LOCK_ASSERT(ifq); 454 455 /* grab class set by classifier */ 456 if ((m->m_flags & M_PKTHDR) == 0) { 457 /* should not happen */ 458 printf("altq: packet for %s does not have pkthdr\n", 459 ifq->altq_ifp->if_xname); 460 m_freem(m); 461 return (ENOBUFS); 462 } 463 cl = NULL; 464 if ((t = pf_find_mtag(m)) != NULL) 465 cl = clh_to_clp(pif, t->qid); 466 if (cl == NULL) { 467 cl = pif->pif_default; 468 if (cl == NULL) { 469 m_freem(m); 470 return (ENOBUFS); 471 } 472 } 473 cl->cl_pktattr = NULL; 474 len = m_pktlen(m); 475 if (priq_addq(cl, m) != 0) { 476 /* drop occurred. mbuf was freed in priq_addq. */ 477 PKTCNTR_ADD(&cl->cl_dropcnt, len); 478 return (ENOBUFS); 479 } 480 IFQ_INC_LEN(ifq); 481 482 /* successfully queued. */ 483 return (0); 484 } 485 486 /* 487 * priq_dequeue is a dequeue function to be registered to 488 * (*altq_dequeue) in struct ifaltq. 489 * 490 * note: ALTDQ_POLL returns the next packet without removing the packet 491 * from the queue. ALTDQ_REMOVE is a normal dequeue operation. 492 * ALTDQ_REMOVE must return the same packet if called immediately 493 * after ALTDQ_POLL. 494 */ 495 static struct mbuf * 496 priq_dequeue(struct ifaltq *ifq, int op) 497 { 498 struct priq_if *pif = (struct priq_if *)ifq->altq_disc; 499 struct priq_class *cl; 500 struct mbuf *m; 501 int pri; 502 503 IFQ_LOCK_ASSERT(ifq); 504 505 if (IFQ_IS_EMPTY(ifq)) 506 /* no packet in the queue */ 507 return (NULL); 508 509 for (pri = pif->pif_maxpri; pri >= 0; pri--) { 510 if ((cl = pif->pif_classes[pri]) != NULL && 511 !qempty(cl->cl_q)) { 512 if (op == ALTDQ_POLL) 513 return (priq_pollq(cl)); 514 515 m = priq_getq(cl); 516 if (m != NULL) { 517 IFQ_DEC_LEN(ifq); 518 if (qempty(cl->cl_q)) 519 cl->cl_period++; 520 PKTCNTR_ADD(&cl->cl_xmitcnt, m_pktlen(m)); 521 } 522 return (m); 523 } 524 } 525 return (NULL); 526 } 527 528 static int 529 priq_addq(struct priq_class *cl, struct mbuf *m) 530 { 531 532 #ifdef ALTQ_RIO 533 if (q_is_rio(cl->cl_q)) 534 return rio_addq((rio_t *)cl->cl_red, cl->cl_q, m, 535 cl->cl_pktattr); 536 #endif 537 #ifdef ALTQ_RED 538 if (q_is_red(cl->cl_q)) 539 return red_addq(cl->cl_red, cl->cl_q, m, cl->cl_pktattr); 540 #endif 541 #ifdef ALTQ_CODEL 542 if (q_is_codel(cl->cl_q)) 543 return codel_addq(cl->cl_codel, cl->cl_q, m); 544 #endif 545 if (qlen(cl->cl_q) >= qlimit(cl->cl_q)) { 546 m_freem(m); 547 return (-1); 548 } 549 550 if (cl->cl_flags & PRCF_CLEARDSCP) 551 write_dsfield(m, cl->cl_pktattr, 0); 552 553 _addq(cl->cl_q, m); 554 555 return (0); 556 } 557 558 static struct mbuf * 559 priq_getq(struct priq_class *cl) 560 { 561 #ifdef ALTQ_RIO 562 if (q_is_rio(cl->cl_q)) 563 return rio_getq((rio_t *)cl->cl_red, cl->cl_q); 564 #endif 565 #ifdef ALTQ_RED 566 if (q_is_red(cl->cl_q)) 567 return red_getq(cl->cl_red, cl->cl_q); 568 #endif 569 #ifdef ALTQ_CODEL 570 if (q_is_codel(cl->cl_q)) 571 return codel_getq(cl->cl_codel, cl->cl_q); 572 #endif 573 return _getq(cl->cl_q); 574 } 575 576 static struct mbuf * 577 priq_pollq(cl) 578 struct priq_class *cl; 579 { 580 return qhead(cl->cl_q); 581 } 582 583 static void 584 priq_purgeq(struct priq_class *cl) 585 { 586 struct mbuf *m; 587 588 if (qempty(cl->cl_q)) 589 return; 590 591 while ((m = _getq(cl->cl_q)) != NULL) { 592 PKTCNTR_ADD(&cl->cl_dropcnt, m_pktlen(m)); 593 m_freem(m); 594 } 595 ASSERT(qlen(cl->cl_q) == 0); 596 } 597 598 static void 599 get_class_stats(struct priq_classstats *sp, struct priq_class *cl) 600 { 601 sp->class_handle = cl->cl_handle; 602 sp->qlength = qlen(cl->cl_q); 603 sp->qlimit = qlimit(cl->cl_q); 604 sp->period = cl->cl_period; 605 sp->xmitcnt = cl->cl_xmitcnt; 606 sp->dropcnt = cl->cl_dropcnt; 607 608 sp->qtype = qtype(cl->cl_q); 609 #ifdef ALTQ_RED 610 if (q_is_red(cl->cl_q)) 611 red_getstats(cl->cl_red, &sp->red[0]); 612 #endif 613 #ifdef ALTQ_RIO 614 if (q_is_rio(cl->cl_q)) 615 rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); 616 #endif 617 #ifdef ALTQ_CODEL 618 if (q_is_codel(cl->cl_q)) 619 codel_getstats(cl->cl_codel, &sp->codel); 620 #endif 621 } 622 623 /* convert a class handle to the corresponding class pointer */ 624 static struct priq_class * 625 clh_to_clp(struct priq_if *pif, u_int32_t chandle) 626 { 627 struct priq_class *cl; 628 int idx; 629 630 if (chandle == 0) 631 return (NULL); 632 633 for (idx = pif->pif_maxpri; idx >= 0; idx--) 634 if ((cl = pif->pif_classes[idx]) != NULL && 635 cl->cl_handle == chandle) 636 return (cl); 637 638 return (NULL); 639 } 640 641 #endif /* ALTQ_PRIQ */ 642