1 /* $KAME: altq_cbq.c,v 1.20 2004/04/17 10:54:48 kjc Exp $ */ 2 /* $DragonFly: src/sys/net/altq/altq_cbq.c,v 1.7 2008/05/14 11:59:23 sephe Exp $ */ 3 4 /* 5 * Copyright (c) Sun Microsystems, Inc. 1993-1998 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 * 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the SMCC Technology 21 * Development Group at Sun Microsystems, Inc. 22 * 23 * 4. The name of the Sun Microsystems, Inc nor may not be used to endorse or 24 * promote products derived from this software without specific prior 25 * written permission. 26 * 27 * SUN MICROSYSTEMS DOES NOT CLAIM MERCHANTABILITY OF THIS SOFTWARE OR THE 28 * SUITABILITY OF THIS SOFTWARE FOR ANY PARTICULAR PURPOSE. The software is 29 * provided "as is" without express or implied warranty of any kind. 30 * 31 * These notices must be retained in any copies of any part of this software. 32 */ 33 34 #include "opt_altq.h" 35 #include "opt_inet.h" 36 #include "opt_inet6.h" 37 38 #ifdef ALTQ_CBQ /* cbq is enabled by ALTQ_CBQ option in opt_altq.h */ 39 40 #include <sys/param.h> 41 #include <sys/malloc.h> 42 #include <sys/mbuf.h> 43 #include <sys/socket.h> 44 #include <sys/systm.h> 45 #include <sys/proc.h> 46 #include <sys/callout.h> 47 #include <sys/errno.h> 48 #include <sys/time.h> 49 #include <sys/thread.h> 50 51 #include <net/if.h> 52 #include <net/ifq_var.h> 53 #include <netinet/in.h> 54 55 #include <net/pf/pfvar.h> 56 #include <net/altq/altq.h> 57 #include <net/altq/altq_cbq.h> 58 59 #include <sys/thread2.h> 60 61 #define CBQ_SUBQ_INDEX ALTQ_SUBQ_INDEX_DEFAULT 62 #define CBQ_LOCK(ifq) \ 63 ALTQ_SQ_LOCK(&(ifq)->altq_subq[CBQ_SUBQ_INDEX]) 64 #define CBQ_UNLOCK(ifq) \ 65 ALTQ_SQ_UNLOCK(&(ifq)->altq_subq[CBQ_SUBQ_INDEX]) 66 #define CBQ_ASSERT_LOCKED(ifq) \ 67 ALTQ_SQ_ASSERT_LOCKED(&(ifq)->altq_subq[CBQ_SUBQ_INDEX]) 68 69 /* 70 * Forward Declarations. 71 */ 72 static int cbq_class_destroy(cbq_state_t *, struct rm_class *); 73 static struct rm_class *clh_to_clp(cbq_state_t *, uint32_t); 74 static int cbq_clear_interface(cbq_state_t *); 75 static int cbq_request(struct ifaltq_subque *, int, void *); 76 static int cbq_enqueue(struct ifaltq_subque *, struct mbuf *, 77 struct altq_pktattr *); 78 static struct mbuf *cbq_dequeue(struct ifaltq_subque *, int); 79 static void cbqrestart(struct ifaltq *); 80 static void get_class_stats(class_stats_t *, struct rm_class *); 81 static void cbq_purge(cbq_state_t *); 82 83 /* 84 * int 85 * cbq_class_destroy(cbq_mod_state_t *, struct rm_class *) - This 86 * function destroys a given traffic class. Before destroying 87 * the class, all traffic for that class is released. 88 */ 89 static int 90 cbq_class_destroy(cbq_state_t *cbqp, struct rm_class *cl) 91 { 92 int i; 93 94 /* delete the class */ 95 rmc_delete_class(&cbqp->ifnp, cl); 96 97 /* 98 * free the class handle 99 */ 100 for (i = 0; i < CBQ_MAX_CLASSES; i++) 101 if (cbqp->cbq_class_tbl[i] == cl) 102 cbqp->cbq_class_tbl[i] = NULL; 103 104 if (cl == cbqp->ifnp.root_) 105 cbqp->ifnp.root_ = NULL; 106 if (cl == cbqp->ifnp.default_) 107 cbqp->ifnp.default_ = NULL; 108 return (0); 109 } 110 111 /* convert class handle to class pointer */ 112 static struct rm_class * 113 clh_to_clp(cbq_state_t *cbqp, uint32_t chandle) 114 { 115 int i; 116 struct rm_class *cl; 117 118 if (chandle == 0) 119 return (NULL); 120 /* 121 * first, try optimistically the slot matching the lower bits of 122 * the handle. if it fails, do the linear table search. 123 */ 124 i = chandle % CBQ_MAX_CLASSES; 125 if ((cl = cbqp->cbq_class_tbl[i]) != NULL && 126 cl->stats_.handle == chandle) 127 return (cl); 128 for (i = 0; i < CBQ_MAX_CLASSES; i++) 129 if ((cl = cbqp->cbq_class_tbl[i]) != NULL && 130 cl->stats_.handle == chandle) 131 return (cl); 132 return (NULL); 133 } 134 135 static int 136 cbq_clear_interface(cbq_state_t *cbqp) 137 { 138 int again, i; 139 struct rm_class *cl; 140 141 /* clear out the classes now */ 142 do { 143 again = 0; 144 for (i = 0; i < CBQ_MAX_CLASSES; i++) { 145 if ((cl = cbqp->cbq_class_tbl[i]) != NULL) { 146 if (is_a_parent_class(cl)) 147 again++; 148 else { 149 cbq_class_destroy(cbqp, cl); 150 cbqp->cbq_class_tbl[i] = NULL; 151 if (cl == cbqp->ifnp.root_) 152 cbqp->ifnp.root_ = NULL; 153 if (cl == cbqp->ifnp.default_) 154 cbqp->ifnp.default_ = NULL; 155 } 156 } 157 } 158 } while (again); 159 160 return (0); 161 } 162 163 static int 164 cbq_request(struct ifaltq_subque *ifsq, int req, void *arg) 165 { 166 struct ifaltq *ifq = ifsq->ifsq_altq; 167 cbq_state_t *cbqp = (cbq_state_t *)ifq->altq_disc; 168 169 crit_enter(); 170 switch (req) { 171 case ALTRQ_PURGE: 172 if (ifsq_get_index(ifsq) == CBQ_SUBQ_INDEX) { 173 cbq_purge(cbqp); 174 } else { 175 /* 176 * Race happened, the unrelated subqueue was 177 * picked during the packet scheduler transition. 178 */ 179 ifsq_classic_request(ifsq, ALTRQ_PURGE, NULL); 180 } 181 break; 182 } 183 crit_exit(); 184 return (0); 185 } 186 187 /* copy the stats info in rm_class to class_states_t */ 188 static void 189 get_class_stats(class_stats_t *statsp, struct rm_class *cl) 190 { 191 statsp->xmit_cnt = cl->stats_.xmit_cnt; 192 statsp->drop_cnt = cl->stats_.drop_cnt; 193 statsp->over = cl->stats_.over; 194 statsp->borrows = cl->stats_.borrows; 195 statsp->overactions = cl->stats_.overactions; 196 statsp->delays = cl->stats_.delays; 197 198 statsp->depth = cl->depth_; 199 statsp->priority = cl->pri_; 200 statsp->maxidle = cl->maxidle_; 201 statsp->minidle = cl->minidle_; 202 statsp->offtime = cl->offtime_; 203 statsp->qmax = qlimit(cl->q_); 204 statsp->ns_per_byte = cl->ns_per_byte_; 205 statsp->wrr_allot = cl->w_allotment_; 206 statsp->qcnt = qlen(cl->q_); 207 statsp->avgidle = cl->avgidle_; 208 209 statsp->qtype = qtype(cl->q_); 210 #ifdef ALTQ_RED 211 if (q_is_red(cl->q_)) 212 red_getstats(cl->red_, &statsp->red[0]); 213 #endif 214 #ifdef ALTQ_RIO 215 if (q_is_rio(cl->q_)) 216 rio_getstats((rio_t *)cl->red_, &statsp->red[0]); 217 #endif 218 } 219 220 int 221 cbq_pfattach(struct pf_altq *a, struct ifaltq *ifq) 222 { 223 return altq_attach(ifq, ALTQT_CBQ, a->altq_disc, ifq_mapsubq_default, 224 cbq_enqueue, cbq_dequeue, cbq_request, NULL, NULL); 225 } 226 227 int 228 cbq_add_altq(struct pf_altq *a) 229 { 230 cbq_state_t *cbqp; 231 struct ifnet *ifp; 232 233 ifnet_lock(); 234 235 if ((ifp = ifunit(a->ifname)) == NULL) { 236 ifnet_unlock(); 237 return (EINVAL); 238 } 239 if (!ifq_is_ready(&ifp->if_snd)) { 240 ifnet_unlock(); 241 return (ENODEV); 242 } 243 244 /* allocate and initialize cbq_state_t */ 245 cbqp = kmalloc(sizeof(*cbqp), M_ALTQ, M_WAITOK | M_ZERO); 246 callout_init(&cbqp->cbq_callout); 247 cbqp->cbq_qlen = 0; 248 cbqp->ifnp.ifq_ = &ifp->if_snd; /* keep the ifq */ 249 ifq_purge_all(&ifp->if_snd); 250 251 ifnet_unlock(); 252 253 /* keep the state in pf_altq */ 254 a->altq_disc = cbqp; 255 256 return (0); 257 } 258 259 int 260 cbq_remove_altq(struct pf_altq *a) 261 { 262 cbq_state_t *cbqp; 263 264 if ((cbqp = a->altq_disc) == NULL) 265 return (EINVAL); 266 a->altq_disc = NULL; 267 268 cbq_clear_interface(cbqp); 269 270 if (cbqp->ifnp.default_) 271 cbq_class_destroy(cbqp, cbqp->ifnp.default_); 272 if (cbqp->ifnp.root_) 273 cbq_class_destroy(cbqp, cbqp->ifnp.root_); 274 275 /* deallocate cbq_state_t */ 276 kfree(cbqp, M_ALTQ); 277 278 return (0); 279 } 280 281 static int 282 cbq_add_queue_locked(struct pf_altq *a, cbq_state_t *cbqp) 283 { 284 struct rm_class *borrow, *parent; 285 struct rm_class *cl; 286 struct cbq_opts *opts; 287 int i; 288 289 KKASSERT(a->qid != 0); 290 291 /* 292 * find a free slot in the class table. if the slot matching 293 * the lower bits of qid is free, use this slot. otherwise, 294 * use the first free slot. 295 */ 296 i = a->qid % CBQ_MAX_CLASSES; 297 if (cbqp->cbq_class_tbl[i] != NULL) { 298 for (i = 0; i < CBQ_MAX_CLASSES; i++) 299 if (cbqp->cbq_class_tbl[i] == NULL) 300 break; 301 if (i == CBQ_MAX_CLASSES) 302 return (EINVAL); 303 } 304 305 opts = &a->pq_u.cbq_opts; 306 /* check parameters */ 307 if (a->priority >= CBQ_MAXPRI) 308 return (EINVAL); 309 310 /* Get pointers to parent and borrow classes. */ 311 parent = clh_to_clp(cbqp, a->parent_qid); 312 if (opts->flags & CBQCLF_BORROW) 313 borrow = parent; 314 else 315 borrow = NULL; 316 317 /* 318 * A class must borrow from it's parent or it can not 319 * borrow at all. Hence, borrow can be null. 320 */ 321 if (parent == NULL && (opts->flags & CBQCLF_ROOTCLASS) == 0) { 322 kprintf("cbq_add_queue: no parent class!\n"); 323 return (EINVAL); 324 } 325 326 if ((borrow != parent) && (borrow != NULL)) { 327 kprintf("cbq_add_class: borrow class != parent\n"); 328 return (EINVAL); 329 } 330 331 /* 332 * check parameters 333 */ 334 switch (opts->flags & CBQCLF_CLASSMASK) { 335 case CBQCLF_ROOTCLASS: 336 if (parent != NULL) 337 return (EINVAL); 338 if (cbqp->ifnp.root_) 339 return (EINVAL); 340 break; 341 case CBQCLF_DEFCLASS: 342 if (cbqp->ifnp.default_) 343 return (EINVAL); 344 break; 345 case 0: 346 if (a->qid == 0) 347 return (EINVAL); 348 break; 349 default: 350 /* more than two flags bits set */ 351 return (EINVAL); 352 } 353 354 /* 355 * create a class. if this is a root class, initialize the 356 * interface. 357 */ 358 if ((opts->flags & CBQCLF_CLASSMASK) == CBQCLF_ROOTCLASS) { 359 rmc_init(cbqp->ifnp.ifq_, &cbqp->ifnp, opts->ns_per_byte, 360 cbqrestart, a->qlimit, RM_MAXQUEUED, 361 opts->maxidle, opts->minidle, opts->offtime, 362 opts->flags); 363 cl = cbqp->ifnp.root_; 364 } else { 365 cl = rmc_newclass(a->priority, 366 &cbqp->ifnp, opts->ns_per_byte, 367 rmc_delay_action, a->qlimit, parent, borrow, 368 opts->maxidle, opts->minidle, opts->offtime, 369 opts->pktsize, opts->flags); 370 } 371 if (cl == NULL) 372 return (ENOMEM); 373 374 /* return handle to user space. */ 375 cl->stats_.handle = a->qid; 376 cl->stats_.depth = cl->depth_; 377 378 /* save the allocated class */ 379 cbqp->cbq_class_tbl[i] = cl; 380 381 if ((opts->flags & CBQCLF_CLASSMASK) == CBQCLF_DEFCLASS) 382 cbqp->ifnp.default_ = cl; 383 384 return (0); 385 } 386 387 int 388 cbq_add_queue(struct pf_altq *a) 389 { 390 cbq_state_t *cbqp; 391 struct ifaltq *ifq; 392 int error; 393 394 if (a->qid == 0) 395 return (EINVAL); 396 397 /* XXX not MP safe */ 398 if ((cbqp = a->altq_disc) == NULL) 399 return (EINVAL); 400 ifq = cbqp->ifnp.ifq_; 401 402 CBQ_LOCK(ifq); 403 error = cbq_add_queue_locked(a, cbqp); 404 CBQ_UNLOCK(ifq); 405 406 return error; 407 } 408 409 static int 410 cbq_remove_queue_locked(struct pf_altq *a, cbq_state_t *cbqp) 411 { 412 struct rm_class *cl; 413 int i; 414 415 if ((cl = clh_to_clp(cbqp, a->qid)) == NULL) 416 return (EINVAL); 417 418 /* if we are a parent class, then return an error. */ 419 if (is_a_parent_class(cl)) 420 return (EINVAL); 421 422 /* delete the class */ 423 rmc_delete_class(&cbqp->ifnp, cl); 424 425 /* 426 * free the class handle 427 */ 428 for (i = 0; i < CBQ_MAX_CLASSES; i++) 429 if (cbqp->cbq_class_tbl[i] == cl) { 430 cbqp->cbq_class_tbl[i] = NULL; 431 if (cl == cbqp->ifnp.root_) 432 cbqp->ifnp.root_ = NULL; 433 if (cl == cbqp->ifnp.default_) 434 cbqp->ifnp.default_ = NULL; 435 break; 436 } 437 438 return (0); 439 } 440 441 int 442 cbq_remove_queue(struct pf_altq *a) 443 { 444 cbq_state_t *cbqp; 445 struct ifaltq *ifq; 446 int error; 447 448 /* XXX not MP safe */ 449 if ((cbqp = a->altq_disc) == NULL) 450 return (EINVAL); 451 ifq = cbqp->ifnp.ifq_; 452 453 CBQ_LOCK(ifq); 454 error = cbq_remove_queue_locked(a, cbqp); 455 CBQ_UNLOCK(ifq); 456 457 return error; 458 } 459 460 int 461 cbq_getqstats(struct pf_altq *a, void *ubuf, int *nbytes) 462 { 463 cbq_state_t *cbqp; 464 struct rm_class *cl; 465 class_stats_t stats; 466 int error = 0; 467 struct ifaltq *ifq; 468 469 if (*nbytes < sizeof(stats)) 470 return (EINVAL); 471 472 ifnet_lock(); 473 474 /* XXX not MP safe */ 475 if ((cbqp = altq_lookup(a->ifname, ALTQT_CBQ)) == NULL) { 476 ifnet_unlock(); 477 return (EBADF); 478 } 479 ifq = cbqp->ifnp.ifq_; 480 481 CBQ_LOCK(ifq); 482 483 if ((cl = clh_to_clp(cbqp, a->qid)) == NULL) { 484 CBQ_UNLOCK(ifq); 485 ifnet_unlock(); 486 return (EINVAL); 487 } 488 489 get_class_stats(&stats, cl); 490 491 CBQ_UNLOCK(ifq); 492 493 ifnet_unlock(); 494 495 if ((error = copyout((caddr_t)&stats, ubuf, sizeof(stats))) != 0) 496 return (error); 497 *nbytes = sizeof(stats); 498 return (0); 499 } 500 501 /* 502 * int 503 * cbq_enqueue(struct ifaltq_subqueue *ifq, struct mbuf *m, 504 * struct altq_pktattr *pattr) 505 * - Queue data packets. 506 * 507 * cbq_enqueue is set to ifp->if_altqenqueue and called by an upper 508 * layer (e.g. ether_output). cbq_enqueue queues the given packet 509 * to the cbq, then invokes the driver's start routine. 510 * 511 * Returns: 0 if the queueing is successful. 512 * ENOBUFS if a packet dropping occurred as a result of 513 * the queueing. 514 */ 515 516 static int 517 cbq_enqueue(struct ifaltq_subque *ifsq, struct mbuf *m, 518 struct altq_pktattr *pktattr __unused) 519 { 520 struct ifaltq *ifq = ifsq->ifsq_altq; 521 cbq_state_t *cbqp = (cbq_state_t *)ifq->altq_disc; 522 struct rm_class *cl; 523 int len; 524 525 if (ifsq_get_index(ifsq) != CBQ_SUBQ_INDEX) { 526 /* 527 * Race happened, the unrelated subqueue was 528 * picked during the packet scheduler transition. 529 */ 530 ifsq_classic_request(ifsq, ALTRQ_PURGE, NULL); 531 m_freem(m); 532 return (ENOBUFS); 533 } 534 535 /* grab class set by classifier */ 536 M_ASSERTPKTHDR(m); 537 if (m->m_pkthdr.fw_flags & PF_MBUF_STRUCTURE) 538 cl = clh_to_clp(cbqp, m->m_pkthdr.pf.qid); 539 else 540 cl = NULL; 541 if (cl == NULL) { 542 cl = cbqp->ifnp.default_; 543 if (cl == NULL) { 544 m_freem(m); 545 return (ENOBUFS); 546 } 547 } 548 crit_enter(); 549 cl->pktattr_ = NULL; 550 len = m_pktlen(m); 551 if (rmc_queue_packet(cl, m) != 0) { 552 /* drop occurred. some mbuf was freed in rmc_queue_packet. */ 553 PKTCNTR_ADD(&cl->stats_.drop_cnt, len); 554 crit_exit(); 555 return (ENOBUFS); 556 } 557 558 /* successfully queued. */ 559 ++cbqp->cbq_qlen; 560 ALTQ_SQ_PKTCNT_INC(ifsq); 561 crit_exit(); 562 return (0); 563 } 564 565 static struct mbuf * 566 cbq_dequeue(struct ifaltq_subque *ifsq, int op) 567 { 568 struct ifaltq *ifq = ifsq->ifsq_altq; 569 cbq_state_t *cbqp = (cbq_state_t *)ifq->altq_disc; 570 struct mbuf *m; 571 572 if (ifsq_get_index(ifsq) != CBQ_SUBQ_INDEX) { 573 /* 574 * Race happened, the unrelated subqueue was 575 * picked during the packet scheduler transition. 576 */ 577 ifsq_classic_request(ifsq, ALTRQ_PURGE, NULL); 578 return NULL; 579 } 580 581 crit_enter(); 582 m = rmc_dequeue_next(&cbqp->ifnp, op); 583 584 if (m && op == ALTDQ_REMOVE) { 585 --cbqp->cbq_qlen; /* decrement # of packets in cbq */ 586 ALTQ_SQ_PKTCNT_DEC(ifsq); 587 588 /* Update the class. */ 589 rmc_update_class_util(&cbqp->ifnp); 590 } 591 crit_exit(); 592 return (m); 593 } 594 595 /* 596 * void 597 * cbqrestart(queue_t *) - Restart sending of data. 598 * called from rmc_restart in a critical section via timeout after waking up 599 * a suspended class. 600 * Returns: NONE 601 */ 602 603 static void 604 cbqrestart(struct ifaltq *ifq) 605 { 606 cbq_state_t *cbqp; 607 608 CBQ_ASSERT_LOCKED(ifq); 609 610 if (!ifq_is_enabled(ifq)) 611 /* cbq must have been detached */ 612 return; 613 614 if ((cbqp = (cbq_state_t *)ifq->altq_disc) == NULL) 615 /* should not happen */ 616 return; 617 618 if (cbqp->cbq_qlen > 0) { 619 struct ifnet *ifp = ifq->altq_ifp; 620 struct ifaltq_subque *ifsq = &ifq->altq_subq[CBQ_SUBQ_INDEX]; 621 622 /* Release the altq lock to avoid deadlock */ 623 CBQ_UNLOCK(ifq); 624 625 ifsq_serialize_hw(ifsq); 626 if (ifp->if_start && !ifsq_is_oactive(ifsq)) 627 (*ifp->if_start)(ifp, ifsq); 628 ifsq_deserialize_hw(ifsq); 629 630 CBQ_LOCK(ifq); 631 } 632 } 633 634 static void 635 cbq_purge(cbq_state_t *cbqp) 636 { 637 struct rm_class *cl; 638 int i; 639 for (i = 0; i < CBQ_MAX_CLASSES; i++) { 640 if ((cl = cbqp->cbq_class_tbl[i]) != NULL) 641 rmc_dropall(cl); 642 } 643 if (ifq_is_enabled(cbqp->ifnp.ifq_)) 644 ALTQ_SQ_CNTR_RESET(&cbqp->ifnp.ifq_->altq_subq[CBQ_SUBQ_INDEX]); 645 } 646 647 #endif /* ALTQ_CBQ */ 648