sys/net/altq/altq_cbq.c

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