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 78 static void get_class_stats(struct priq_classstats *, struct priq_class *); 79 static struct priq_class *clh_to_clp(struct priq_if *, u_int32_t); 80 81 82 int 83 priq_pfattach(struct pf_altq *a) 84 { 85 struct ifnet *ifp; 86 int s, error; 87 88 if ((ifp = ifunit(a->ifname)) == NULL || a->altq_disc == NULL) 89 return (EINVAL); 90 s = splnet(); 91 error = altq_attach(&ifp->if_snd, ALTQT_PRIQ, a->altq_disc, 92 priq_enqueue, priq_dequeue, priq_request, NULL, NULL); 93 splx(s); 94 return (error); 95 } 96 97 int 98 priq_add_altq(struct ifnet * ifp, struct pf_altq *a) 99 { 100 struct priq_if *pif; 101 102 if (ifp == NULL) 103 return (EINVAL); 104 if (!ALTQ_IS_READY(&ifp->if_snd)) 105 return (ENODEV); 106 107 pif = malloc(sizeof(struct priq_if), M_DEVBUF, M_NOWAIT | M_ZERO); 108 if (pif == NULL) 109 return (ENOMEM); 110 pif->pif_bandwidth = a->ifbandwidth; 111 pif->pif_maxpri = -1; 112 pif->pif_ifq = &ifp->if_snd; 113 114 /* keep the state in pf_altq */ 115 a->altq_disc = pif; 116 117 return (0); 118 } 119 120 int 121 priq_remove_altq(struct pf_altq *a) 122 { 123 struct priq_if *pif; 124 125 if ((pif = a->altq_disc) == NULL) 126 return (EINVAL); 127 a->altq_disc = NULL; 128 129 (void)priq_clear_interface(pif); 130 131 free(pif, M_DEVBUF); 132 return (0); 133 } 134 135 int 136 priq_add_queue(struct pf_altq *a) 137 { 138 struct priq_if *pif; 139 struct priq_class *cl; 140 141 if ((pif = a->altq_disc) == NULL) 142 return (EINVAL); 143 144 /* check parameters */ 145 if (a->priority >= PRIQ_MAXPRI) 146 return (EINVAL); 147 if (a->qid == 0) 148 return (EINVAL); 149 if (pif->pif_classes[a->priority] != NULL) 150 return (EBUSY); 151 if (clh_to_clp(pif, a->qid) != NULL) 152 return (EBUSY); 153 154 cl = priq_class_create(pif, a->priority, a->qlimit, 155 a->pq_u.priq_opts.flags, a->qid); 156 if (cl == NULL) 157 return (ENOMEM); 158 159 return (0); 160 } 161 162 int 163 priq_remove_queue(struct pf_altq *a) 164 { 165 struct priq_if *pif; 166 struct priq_class *cl; 167 168 if ((pif = a->altq_disc) == NULL) 169 return (EINVAL); 170 171 if ((cl = clh_to_clp(pif, a->qid)) == NULL) 172 return (EINVAL); 173 174 return (priq_class_destroy(cl)); 175 } 176 177 int 178 priq_getqstats(struct pf_altq *a, void *ubuf, int *nbytes, int version) 179 { 180 struct priq_if *pif; 181 struct priq_class *cl; 182 struct priq_classstats stats; 183 int error = 0; 184 185 if ((pif = altq_lookup(a->ifname, ALTQT_PRIQ)) == NULL) 186 return (EBADF); 187 188 if ((cl = clh_to_clp(pif, a->qid)) == NULL) 189 return (EINVAL); 190 191 if (*nbytes < sizeof(stats)) 192 return (EINVAL); 193 194 get_class_stats(&stats, cl); 195 196 if ((error = copyout((caddr_t)&stats, ubuf, sizeof(stats))) != 0) 197 return (error); 198 *nbytes = sizeof(stats); 199 return (0); 200 } 201 202 /* 203 * bring the interface back to the initial state by discarding 204 * all the filters and classes. 205 */ 206 static int 207 priq_clear_interface(struct priq_if *pif) 208 { 209 struct priq_class *cl; 210 int pri; 211 212 #ifdef ALTQ3_CLFIER_COMPAT 213 /* free the filters for this interface */ 214 acc_discard_filters(&pif->pif_classifier, NULL, 1); 215 #endif 216 217 /* clear out the classes */ 218 for (pri = 0; pri <= pif->pif_maxpri; pri++) 219 if ((cl = pif->pif_classes[pri]) != NULL) 220 priq_class_destroy(cl); 221 222 return (0); 223 } 224 225 static int 226 priq_request(struct ifaltq *ifq, int req, void *arg) 227 { 228 struct priq_if *pif = (struct priq_if *)ifq->altq_disc; 229 230 IFQ_LOCK_ASSERT(ifq); 231 232 switch (req) { 233 case ALTRQ_PURGE: 234 priq_purge(pif); 235 break; 236 } 237 return (0); 238 } 239 240 /* discard all the queued packets on the interface */ 241 static void 242 priq_purge(struct priq_if *pif) 243 { 244 struct priq_class *cl; 245 int pri; 246 247 for (pri = 0; pri <= pif->pif_maxpri; pri++) { 248 if ((cl = pif->pif_classes[pri]) != NULL && !qempty(cl->cl_q)) 249 priq_purgeq(cl); 250 } 251 if (ALTQ_IS_ENABLED(pif->pif_ifq)) 252 pif->pif_ifq->ifq_len = 0; 253 } 254 255 static struct priq_class * 256 priq_class_create(struct priq_if *pif, int pri, int qlimit, int flags, int qid) 257 { 258 struct priq_class *cl; 259 int s; 260 261 #ifndef ALTQ_RED 262 if (flags & PRCF_RED) { 263 #ifdef ALTQ_DEBUG 264 printf("priq_class_create: RED not configured for PRIQ!\n"); 265 #endif 266 return (NULL); 267 } 268 #endif 269 #ifndef ALTQ_CODEL 270 if (flags & PRCF_CODEL) { 271 #ifdef ALTQ_DEBUG 272 printf("priq_class_create: CODEL not configured for PRIQ!\n"); 273 #endif 274 return (NULL); 275 } 276 #endif 277 278 if ((cl = pif->pif_classes[pri]) != NULL) { 279 /* modify the class instead of creating a new one */ 280 s = splnet(); 281 IFQ_LOCK(cl->cl_pif->pif_ifq); 282 if (!qempty(cl->cl_q)) 283 priq_purgeq(cl); 284 IFQ_UNLOCK(cl->cl_pif->pif_ifq); 285 splx(s); 286 #ifdef ALTQ_RIO 287 if (q_is_rio(cl->cl_q)) 288 rio_destroy((rio_t *)cl->cl_red); 289 #endif 290 #ifdef ALTQ_RED 291 if (q_is_red(cl->cl_q)) 292 red_destroy(cl->cl_red); 293 #endif 294 #ifdef ALTQ_CODEL 295 if (q_is_codel(cl->cl_q)) 296 codel_destroy(cl->cl_codel); 297 #endif 298 } else { 299 cl = malloc(sizeof(struct priq_class), M_DEVBUF, 300 M_NOWAIT | M_ZERO); 301 if (cl == NULL) 302 return (NULL); 303 304 cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF, 305 M_NOWAIT | M_ZERO); 306 if (cl->cl_q == NULL) 307 goto err_ret; 308 } 309 310 pif->pif_classes[pri] = cl; 311 if (flags & PRCF_DEFAULTCLASS) 312 pif->pif_default = cl; 313 if (qlimit == 0) 314 qlimit = 50; /* use default */ 315 qlimit(cl->cl_q) = qlimit; 316 qtype(cl->cl_q) = Q_DROPTAIL; 317 qlen(cl->cl_q) = 0; 318 qsize(cl->cl_q) = 0; 319 cl->cl_flags = flags; 320 cl->cl_pri = pri; 321 if (pri > pif->pif_maxpri) 322 pif->pif_maxpri = pri; 323 cl->cl_pif = pif; 324 cl->cl_handle = qid; 325 326 #ifdef ALTQ_RED 327 if (flags & (PRCF_RED|PRCF_RIO)) { 328 int red_flags, red_pkttime; 329 330 red_flags = 0; 331 if (flags & PRCF_ECN) 332 red_flags |= REDF_ECN; 333 #ifdef ALTQ_RIO 334 if (flags & PRCF_CLEARDSCP) 335 red_flags |= RIOF_CLEARDSCP; 336 #endif 337 if (pif->pif_bandwidth < 8) 338 red_pkttime = 1000 * 1000 * 1000; /* 1 sec */ 339 else 340 red_pkttime = (int64_t)pif->pif_ifq->altq_ifp->if_mtu 341 * 1000 * 1000 * 1000 / (pif->pif_bandwidth / 8); 342 #ifdef ALTQ_RIO 343 if (flags & PRCF_RIO) { 344 cl->cl_red = (red_t *)rio_alloc(0, NULL, 345 red_flags, red_pkttime); 346 if (cl->cl_red == NULL) 347 goto err_ret; 348 qtype(cl->cl_q) = Q_RIO; 349 } else 350 #endif 351 if (flags & PRCF_RED) { 352 cl->cl_red = red_alloc(0, 0, 353 qlimit(cl->cl_q) * 10/100, 354 qlimit(cl->cl_q) * 30/100, 355 red_flags, red_pkttime); 356 if (cl->cl_red == NULL) 357 goto err_ret; 358 qtype(cl->cl_q) = Q_RED; 359 } 360 } 361 #endif /* ALTQ_RED */ 362 #ifdef ALTQ_CODEL 363 if (flags & PRCF_CODEL) { 364 cl->cl_codel = codel_alloc(5, 100, 0); 365 if (cl->cl_codel != NULL) 366 qtype(cl->cl_q) = Q_CODEL; 367 } 368 #endif 369 370 return (cl); 371 372 err_ret: 373 if (cl->cl_red != NULL) { 374 #ifdef ALTQ_RIO 375 if (q_is_rio(cl->cl_q)) 376 rio_destroy((rio_t *)cl->cl_red); 377 #endif 378 #ifdef ALTQ_RED 379 if (q_is_red(cl->cl_q)) 380 red_destroy(cl->cl_red); 381 #endif 382 #ifdef ALTQ_CODEL 383 if (q_is_codel(cl->cl_q)) 384 codel_destroy(cl->cl_codel); 385 #endif 386 } 387 if (cl->cl_q != NULL) 388 free(cl->cl_q, M_DEVBUF); 389 free(cl, M_DEVBUF); 390 return (NULL); 391 } 392 393 static int 394 priq_class_destroy(struct priq_class *cl) 395 { 396 struct priq_if *pif; 397 int s, pri; 398 399 s = splnet(); 400 IFQ_LOCK(cl->cl_pif->pif_ifq); 401 402 #ifdef ALTQ3_CLFIER_COMPAT 403 /* delete filters referencing to this class */ 404 acc_discard_filters(&cl->cl_pif->pif_classifier, cl, 0); 405 #endif 406 407 if (!qempty(cl->cl_q)) 408 priq_purgeq(cl); 409 410 pif = cl->cl_pif; 411 pif->pif_classes[cl->cl_pri] = NULL; 412 if (pif->pif_maxpri == cl->cl_pri) { 413 for (pri = cl->cl_pri; pri >= 0; pri--) 414 if (pif->pif_classes[pri] != NULL) { 415 pif->pif_maxpri = pri; 416 break; 417 } 418 if (pri < 0) 419 pif->pif_maxpri = -1; 420 } 421 IFQ_UNLOCK(cl->cl_pif->pif_ifq); 422 splx(s); 423 424 if (cl->cl_red != NULL) { 425 #ifdef ALTQ_RIO 426 if (q_is_rio(cl->cl_q)) 427 rio_destroy((rio_t *)cl->cl_red); 428 #endif 429 #ifdef ALTQ_RED 430 if (q_is_red(cl->cl_q)) 431 red_destroy(cl->cl_red); 432 #endif 433 #ifdef ALTQ_CODEL 434 if (q_is_codel(cl->cl_q)) 435 codel_destroy(cl->cl_codel); 436 #endif 437 } 438 free(cl->cl_q, M_DEVBUF); 439 free(cl, M_DEVBUF); 440 return (0); 441 } 442 443 /* 444 * priq_enqueue is an enqueue function to be registered to 445 * (*altq_enqueue) in struct ifaltq. 446 */ 447 static int 448 priq_enqueue(struct ifaltq *ifq, struct mbuf *m, struct altq_pktattr *pktattr) 449 { 450 struct priq_if *pif = (struct priq_if *)ifq->altq_disc; 451 struct priq_class *cl; 452 struct pf_mtag *t; 453 int len; 454 455 IFQ_LOCK_ASSERT(ifq); 456 457 /* grab class set by classifier */ 458 if ((m->m_flags & M_PKTHDR) == 0) { 459 /* should not happen */ 460 printf("altq: packet for %s does not have pkthdr\n", 461 ifq->altq_ifp->if_xname); 462 m_freem(m); 463 return (ENOBUFS); 464 } 465 cl = NULL; 466 if ((t = pf_find_mtag(m)) != NULL) 467 cl = clh_to_clp(pif, t->qid); 468 if (cl == NULL) { 469 cl = pif->pif_default; 470 if (cl == NULL) { 471 m_freem(m); 472 return (ENOBUFS); 473 } 474 } 475 cl->cl_pktattr = NULL; 476 len = m_pktlen(m); 477 if (priq_addq(cl, m) != 0) { 478 /* drop occurred. mbuf was freed in priq_addq. */ 479 PKTCNTR_ADD(&cl->cl_dropcnt, len); 480 return (ENOBUFS); 481 } 482 IFQ_INC_LEN(ifq); 483 484 /* successfully queued. */ 485 return (0); 486 } 487 488 /* 489 * priq_dequeue is a dequeue function to be registered to 490 * (*altq_dequeue) in struct ifaltq. 491 * 492 * note: ALTDQ_POLL returns the next packet without removing the packet 493 * from the queue. ALTDQ_REMOVE is a normal dequeue operation. 494 * ALTDQ_REMOVE must return the same packet if called immediately 495 * after ALTDQ_POLL. 496 */ 497 static struct mbuf * 498 priq_dequeue(struct ifaltq *ifq, int op) 499 { 500 struct priq_if *pif = (struct priq_if *)ifq->altq_disc; 501 struct priq_class *cl; 502 struct mbuf *m; 503 int pri; 504 505 IFQ_LOCK_ASSERT(ifq); 506 507 if (IFQ_IS_EMPTY(ifq)) 508 /* no packet in the queue */ 509 return (NULL); 510 511 for (pri = pif->pif_maxpri; pri >= 0; pri--) { 512 if ((cl = pif->pif_classes[pri]) != NULL && 513 !qempty(cl->cl_q)) { 514 if (op == ALTDQ_POLL) 515 return (priq_pollq(cl)); 516 517 m = priq_getq(cl); 518 if (m != NULL) { 519 IFQ_DEC_LEN(ifq); 520 if (qempty(cl->cl_q)) 521 cl->cl_period++; 522 PKTCNTR_ADD(&cl->cl_xmitcnt, m_pktlen(m)); 523 } 524 return (m); 525 } 526 } 527 return (NULL); 528 } 529 530 static int 531 priq_addq(struct priq_class *cl, struct mbuf *m) 532 { 533 534 #ifdef ALTQ_RIO 535 if (q_is_rio(cl->cl_q)) 536 return rio_addq((rio_t *)cl->cl_red, cl->cl_q, m, 537 cl->cl_pktattr); 538 #endif 539 #ifdef ALTQ_RED 540 if (q_is_red(cl->cl_q)) 541 return red_addq(cl->cl_red, cl->cl_q, m, cl->cl_pktattr); 542 #endif 543 #ifdef ALTQ_CODEL 544 if (q_is_codel(cl->cl_q)) 545 return codel_addq(cl->cl_codel, cl->cl_q, m); 546 #endif 547 if (qlen(cl->cl_q) >= qlimit(cl->cl_q)) { 548 m_freem(m); 549 return (-1); 550 } 551 552 if (cl->cl_flags & PRCF_CLEARDSCP) 553 write_dsfield(m, cl->cl_pktattr, 0); 554 555 _addq(cl->cl_q, m); 556 557 return (0); 558 } 559 560 static struct mbuf * 561 priq_getq(struct priq_class *cl) 562 { 563 #ifdef ALTQ_RIO 564 if (q_is_rio(cl->cl_q)) 565 return rio_getq((rio_t *)cl->cl_red, cl->cl_q); 566 #endif 567 #ifdef ALTQ_RED 568 if (q_is_red(cl->cl_q)) 569 return red_getq(cl->cl_red, cl->cl_q); 570 #endif 571 #ifdef ALTQ_CODEL 572 if (q_is_codel(cl->cl_q)) 573 return codel_getq(cl->cl_codel, cl->cl_q); 574 #endif 575 return _getq(cl->cl_q); 576 } 577 578 static struct mbuf * 579 priq_pollq(cl) 580 struct priq_class *cl; 581 { 582 return qhead(cl->cl_q); 583 } 584 585 static void 586 priq_purgeq(struct priq_class *cl) 587 { 588 struct mbuf *m; 589 590 if (qempty(cl->cl_q)) 591 return; 592 593 while ((m = _getq(cl->cl_q)) != NULL) { 594 PKTCNTR_ADD(&cl->cl_dropcnt, m_pktlen(m)); 595 m_freem(m); 596 } 597 ASSERT(qlen(cl->cl_q) == 0); 598 } 599 600 static void 601 get_class_stats(struct priq_classstats *sp, struct priq_class *cl) 602 { 603 sp->class_handle = cl->cl_handle; 604 sp->qlength = qlen(cl->cl_q); 605 sp->qlimit = qlimit(cl->cl_q); 606 sp->period = cl->cl_period; 607 sp->xmitcnt = cl->cl_xmitcnt; 608 sp->dropcnt = cl->cl_dropcnt; 609 610 sp->qtype = qtype(cl->cl_q); 611 #ifdef ALTQ_RED 612 if (q_is_red(cl->cl_q)) 613 red_getstats(cl->cl_red, &sp->red[0]); 614 #endif 615 #ifdef ALTQ_RIO 616 if (q_is_rio(cl->cl_q)) 617 rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); 618 #endif 619 #ifdef ALTQ_CODEL 620 if (q_is_codel(cl->cl_q)) 621 codel_getstats(cl->cl_codel, &sp->codel); 622 #endif 623 } 624 625 /* convert a class handle to the corresponding class pointer */ 626 static struct priq_class * 627 clh_to_clp(struct priq_if *pif, u_int32_t chandle) 628 { 629 struct priq_class *cl; 630 int idx; 631 632 if (chandle == 0) 633 return (NULL); 634 635 for (idx = pif->pif_maxpri; idx >= 0; idx--) 636 if ((cl = pif->pif_classes[idx]) != NULL && 637 cl->cl_handle == chandle) 638 return (cl); 639 640 return (NULL); 641 } 642 643 644 #endif /* ALTQ_PRIQ */ 645