bsd/net/classq/classq_rio.c

   1 /*
   2  * Copyright (c) 2007-2013 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 /*      $OpenBSD: altq_rio.c,v 1.11 2007/09/13 20:40:02 chl Exp $       */
  30 /*      $KAME: altq_rio.c,v 1.8 2000/12/14 08:12:46 thorpej Exp $       */
  31
  32 /*
  33  * Copyright (C) 1998-2003
  34  *      Sony Computer Science Laboratories Inc.  All rights reserved.
  35  *
  36  * Redistribution and use in source and binary forms, with or without
  37  * modification, are permitted provided that the following conditions
  38  * are met:
  39  * 1. Redistributions of source code must retain the above copyright
  40  *    notice, this list of conditions and the following disclaimer.
  41  * 2. Redistributions in binary form must reproduce the above copyright
  42  *    notice, this list of conditions and the following disclaimer in the
  43  *    documentation and/or other materials provided with the distribution.
  44  *
  45  * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND
  46  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  47  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  48  * ARE DISCLAIMED.  IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE
  49  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  50  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  51  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  52  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  53  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  54  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  55  * SUCH DAMAGE.
  56  */
  57 /*
  58  * Copyright (c) 1990-1994 Regents of the University of California.
  59  * All rights reserved.
  60  *
  61  * Redistribution and use in source and binary forms, with or without
  62  * modification, are permitted provided that the following conditions
  63  * are met:
  64  * 1. Redistributions of source code must retain the above copyright
  65  *    notice, this list of conditions and the following disclaimer.
  66  * 2. Redistributions in binary form must reproduce the above copyright
  67  *    notice, this list of conditions and the following disclaimer in the
  68  *    documentation and/or other materials provided with the distribution.
  69  * 3. All advertising materials mentioning features or use of this software
  70  *    must display the following acknowledgement:
  71  *      This product includes software developed by the Computer Systems
  72  *      Engineering Group at Lawrence Berkeley Laboratory.
  73  * 4. Neither the name of the University nor of the Laboratory may be used
  74  *    to endorse or promote products derived from this software without
  75  *    specific prior written permission.
  76  *
  77  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  78  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  79  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  80  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  81  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  82  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  83  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  84  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  85  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  86  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  87  * SUCH DAMAGE.
  88  */
  89
  90 #include <sys/cdefs.h>
  91
  92 #if CLASSQ_RIO
  93
  94 #include <sys/param.h>
  95 #include <sys/malloc.h>
  96 #include <sys/mbuf.h>
  97 #include <sys/socket.h>
  98 #include <sys/systm.h>
  99 #include <sys/syslog.h>
 100 #include <sys/errno.h>
 101 #include <sys/kauth.h>
 102 #include <sys/kauth.h>
 103
 104 #include <kern/zalloc.h>
 105
 106 #include <net/if.h>
 107
 108 #include <netinet/in.h>
 109 #include <netinet/in_systm.h>
 110 #include <netinet/ip.h>
 111 #if INET6
 112 #include <netinet/ip6.h>
 113 #endif
 114
 115 #include <net/classq/classq_red.h>
 116 #include <net/classq/classq_rio.h>
 117 #include <net/net_osdep.h>
 118
 119 /*
 120  * RIO: RED with IN/OUT bit
 121  *   described in
 122  *      "Explicit Allocation of Best Effort Packet Delivery Service"
 123  *      David D. Clark and Wenjia Fang, MIT Lab for Computer Science
 124  *      http://diffserv.lcs.mit.edu/Papers/exp-alloc-ddc-wf.{ps,pdf}
 125  *
 126  * this implementation is extended to support more than 2 drop precedence
 127  * values as described in RFC2597 (Assured Forwarding PHB Group).
 128  *
 129  */
 130 /*
 131  * AF DS (differentiated service) codepoints.
 132  * (classes can be mapped to CBQ or H-FSC classes.)
 133  *
 134  *      0   1   2   3   4   5   6   7
 135  *    +---+---+---+---+---+---+---+---+
 136  *    |   CLASS   |DropPre| 0 |  CU   |
 137  *    +---+---+---+---+---+---+---+---+
 138  *
 139  *    class 1: 001
 140  *    class 2: 010
 141  *    class 3: 011
 142  *    class 4: 100
 143  *
 144  *    low drop prec:    01
 145  *    medium drop prec: 10
 146  *    high drop prec:   11
 147  */
 148
 149 /* normal red parameters */
 150 #define W_WEIGHT        512     /* inverse of weight of EWMA (511/512) */
 151                                 /* q_weight = 0.00195 */
 152
 153 /* red parameters for a slow link */
 154 #define W_WEIGHT_1      128     /* inverse of weight of EWMA (127/128) */
 155                                 /* q_weight = 0.0078125 */
 156
 157 /* red parameters for a very slow link (e.g., dialup) */
 158 #define W_WEIGHT_2      64      /* inverse of weight of EWMA (63/64) */
 159                                 /* q_weight = 0.015625 */
 160
 161 /* fixed-point uses 12-bit decimal places */
 162 #define FP_SHIFT        12      /* fixed-point shift */
 163
 164 /* red parameters for drop probability */
 165 #define INV_P_MAX       10      /* inverse of max drop probability */
 166 #define TH_MIN           5      /* min threshold */
 167 #define TH_MAX          15      /* max threshold */
 168
 169 #define RIO_LIMIT       60      /* default max queue lenght */
 170
 171 /* default rio parameter values */
 172 static struct redparams default_rio_params[RIO_NDROPPREC] = {
 173   /* th_min,             th_max,     inv_pmax */
 174   { TH_MAX * 2 + TH_MIN, TH_MAX * 3, INV_P_MAX }, /* low drop precedence */
 175   { TH_MAX + TH_MIN,     TH_MAX * 2, INV_P_MAX }, /* medium drop precedence */
 176   { TH_MIN,              TH_MAX,     INV_P_MAX }  /* high drop precedence */
 177 };
 178
 179 #define RIO_ZONE_MAX    32              /* maximum elements in zone */
 180 #define RIO_ZONE_NAME   "classq_rio"    /* zone name */
 181
 182 static unsigned int rio_size;           /* size of zone element */
 183 static struct zone *rio_zone;           /* zone for rio */
 184
 185 /* internal function prototypes */
 186 static struct mbuf *rio_getq_flow(struct rio *, class_queue_t *,
 187     u_int32_t, boolean_t);
 188 static int dscp2index(u_int8_t);
 189
 190 void
 191 rio_init(void)
 192 {
 193         _CASSERT(RIOF_ECN4 == CLASSQF_ECN4);
 194         _CASSERT(RIOF_ECN6 == CLASSQF_ECN6);
 195
 196         rio_size = sizeof (rio_t);
 197         rio_zone = zinit(rio_size, RIO_ZONE_MAX * rio_size,
 198             0, RIO_ZONE_NAME);
 199         if (rio_zone == NULL) {
 200                 panic("%s: failed allocating %s", __func__, RIO_ZONE_NAME);
 201                 /* NOTREACHED */
 202         }
 203         zone_change(rio_zone, Z_EXPAND, TRUE);
 204         zone_change(rio_zone, Z_CALLERACCT, TRUE);
 205 }
 206
 207 rio_t *
 208 rio_alloc(struct ifnet *ifp, int weight, struct redparams *params,
 209     int flags, int pkttime)
 210 {
 211         rio_t   *rp;
 212         int      w, i;
 213         int      npkts_per_sec;
 214
 215         VERIFY(ifp != NULL);
 216
 217         rp = zalloc(rio_zone);
 218         if (rp == NULL)
 219                 return (NULL);
 220
 221         bzero(rp, rio_size);
 222         rp->rio_ifp = ifp;
 223         rp->rio_flags = (flags & RIOF_USERFLAGS);
 224 #if !PF_ECN
 225         if (rp->rio_flags & RIOF_ECN) {
 226                 rp->rio_flags &= ~RIOF_ECN;
 227                 log(LOG_ERR, "%s: RIO ECN not available; ignoring "
 228                     "RIOF_ECN flag!\n", if_name(ifp));
 229         }
 230         if (rp->rio_flags & RIOF_CLEARDSCP) {
 231                 rp->rio_flags &= ~RIOF_CLEARDSCP;
 232                 log(LOG_ERR, "%s: RIO ECN not available; ignoring "
 233                     "RIOF_CLEARDSCP flag!\n", if_name(ifp));
 234         }
 235 #endif /* !PF_ECN */
 236
 237         if (pkttime == 0)
 238                 /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */
 239                 rp->rio_pkttime = 800;
 240         else
 241                 rp->rio_pkttime = pkttime;
 242
 243         if (weight != 0)
 244                 rp->rio_weight = weight;
 245         else {
 246                 /* use default */
 247                 rp->rio_weight = W_WEIGHT;
 248
 249                 /* when the link is very slow, adjust red parameters */
 250                 npkts_per_sec = 1000000 / rp->rio_pkttime;
 251                 if (npkts_per_sec < 50) {
 252                         /* up to about 400Kbps */
 253                         rp->rio_weight = W_WEIGHT_2;
 254                 } else if (npkts_per_sec < 300) {
 255                         /* up to about 2.4Mbps */
 256                         rp->rio_weight = W_WEIGHT_1;
 257                 }
 258         }
 259
 260         /* calculate wshift.  weight must be power of 2 */
 261         w = rp->rio_weight;
 262         for (i = 0; w > 1; i++)
 263                 w = w >> 1;
 264         rp->rio_wshift = i;
 265         w = 1 << rp->rio_wshift;
 266         if (w != rp->rio_weight) {
 267                 printf("invalid weight value %d for red! use %d\n",
 268                     rp->rio_weight, w);
 269                 rp->rio_weight = w;
 270         }
 271
 272         /* allocate weight table */
 273         rp->rio_wtab = wtab_alloc(rp->rio_weight);
 274         if (rp->rio_wtab == NULL) {
 275                 rio_destroy(rp);
 276                 return (NULL);
 277         }
 278
 279         for (i = 0; i < RIO_NDROPPREC; i++) {
 280                 struct dropprec_state *prec = &rp->rio_precstate[i];
 281
 282                 prec->avg = 0;
 283                 prec->idle = 1;
 284
 285                 if (params == NULL || params[i].inv_pmax == 0)
 286                         prec->inv_pmax = default_rio_params[i].inv_pmax;
 287                 else
 288                         prec->inv_pmax = params[i].inv_pmax;
 289                 if (params == NULL || params[i].th_min == 0)
 290                         prec->th_min = default_rio_params[i].th_min;
 291                 else
 292                         prec->th_min = params[i].th_min;
 293                 if (params == NULL || params[i].th_max == 0)
 294                         prec->th_max = default_rio_params[i].th_max;
 295                 else
 296                         prec->th_max = params[i].th_max;
 297
 298                 /*
 299                  * th_min_s and th_max_s are scaled versions of th_min
 300                  * and th_max to be compared with avg.
 301                  */
 302                 prec->th_min_s = prec->th_min << (rp->rio_wshift + FP_SHIFT);
 303                 prec->th_max_s = prec->th_max << (rp->rio_wshift + FP_SHIFT);
 304
 305                 /*
 306                  * precompute probability denominator
 307                  *  probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point
 308                  */
 309                 prec->probd = (2 * (prec->th_max - prec->th_min) *
 310                     prec->inv_pmax) << FP_SHIFT;
 311
 312                 microuptime(&prec->last);
 313         }
 314
 315         return (rp);
 316 }
 317
 318 void
 319 rio_destroy(rio_t *rp)
 320 {
 321         if (rp->rio_wtab != NULL) {
 322                 wtab_destroy(rp->rio_wtab);
 323                 rp->rio_wtab = NULL;
 324         }
 325         zfree(rio_zone, rp);
 326 }
 327
 328 void
 329 rio_getstats(rio_t *rp, struct red_stats *sp)
 330 {
 331         int     i;
 332
 333         for (i = 0; i < RIO_NDROPPREC; i++) {
 334                 bcopy(&rp->q_stats[i], sp, sizeof (struct red_stats));
 335                 sp->q_avg = rp->rio_precstate[i].avg >> rp->rio_wshift;
 336                 sp++;
 337         }
 338 }
 339
 340 #if (RIO_NDROPPREC == 3)
 341 /*
 342  * internally, a drop precedence value is converted to an index
 343  * starting from 0.
 344  */
 345 static int
 346 dscp2index(u_int8_t dscp)
 347 {
 348 #define AF_DROPPRECMASK 0x18
 349
 350         int     dpindex = dscp & AF_DROPPRECMASK;
 351
 352         if (dpindex == 0)
 353                 return (0);
 354         return ((dpindex >> 3) - 1);
 355 }
 356 #endif
 357
 358 /* Store RIO precindex in the module private scratch space */
 359 #define pkt_precidx     pkt_mpriv.__mpriv_u.__mpriv32[0].__mpriv32_u.__val32
 360
 361 #define RIOM_SET_PRECINDEX(pkt, idx) do {               \
 362         (pkt)->pkt_precidx = (idx);                     \
 363 } while (0)
 364
 365 #define RIOM_GET_PRECINDEX(pkt)                         \
 366         ({ u_int32_t idx; idx = (pkt)->pkt_precidx;     \
 367         RIOM_SET_PRECINDEX(pkt, 0); idx; })
 368
 369 int
 370 rio_addq(rio_t *rp, class_queue_t *q, struct mbuf *m, struct pf_mtag *tag)
 371 {
 372 #if !PF_ECN
 373 #pragma unused(tag)
 374 #endif /* !PF_ECN */
 375 #define DSCP_MASK       0xfc
 376         int                      avg, droptype;
 377         u_int8_t                 dsfield, odsfield;
 378         int                      dpindex, i, n, t;
 379         struct timeval           now;
 380         struct dropprec_state   *prec;
 381
 382 #if PF_ECN
 383         dsfield = odsfield = read_dsfield(m, tag);
 384 #else
 385         dsfield = odsfield = 0;
 386 #endif /* !PF_ECN */
 387         dpindex = dscp2index(dsfield);
 388
 389         /*
 390          * update avg of the precedence states whose drop precedence
 391          * is larger than or equal to the drop precedence of the packet
 392          */
 393         now.tv_sec = 0;
 394         for (i = dpindex; i < RIO_NDROPPREC; i++) {
 395                 prec = &rp->rio_precstate[i];
 396                 avg = prec->avg;
 397                 if (prec->idle) {
 398                         prec->idle = 0;
 399                         if (now.tv_sec == 0)
 400                                 microuptime(&now);
 401                         t = (now.tv_sec - prec->last.tv_sec);
 402                         if (t > 60)
 403                                 avg = 0;
 404                         else {
 405                                 t = t * 1000000 +
 406                                     (now.tv_usec - prec->last.tv_usec);
 407                                 n = t / rp->rio_pkttime;
 408                                 /* calculate (avg = (1 - Wq)^n * avg) */
 409                                 if (n > 0) {
 410                                         avg = (avg >> FP_SHIFT) *
 411                                             pow_w(rp->rio_wtab, n);
 412                                 }
 413                         }
 414                 }
 415
 416                 /* run estimator. (avg is scaled by WEIGHT in fixed-point) */
 417                 avg += (prec->qlen << FP_SHIFT) - (avg >> rp->rio_wshift);
 418                 prec->avg = avg;                /* save the new value */
 419                 /*
 420                  * count keeps a tally of arriving traffic that has not
 421                  * been dropped.
 422                  */
 423                 prec->count++;
 424         }
 425
 426         prec = &rp->rio_precstate[dpindex];
 427         avg = prec->avg;
 428
 429         /* see if we drop early */
 430         droptype = DTYPE_NODROP;
 431         if (avg >= prec->th_min_s && prec->qlen > 1) {
 432                 if (avg >= prec->th_max_s) {
 433                         /* avg >= th_max: forced drop */
 434                         droptype = DTYPE_FORCED;
 435                 } else if (prec->old == 0) {
 436                         /* first exceeds th_min */
 437                         prec->count = 1;
 438                         prec->old = 1;
 439                 } else if (drop_early((avg - prec->th_min_s) >> rp->rio_wshift,
 440                     prec->probd, prec->count)) {
 441                         /* unforced drop by red */
 442                         droptype = DTYPE_EARLY;
 443                 }
 444         } else {
 445                 /* avg < th_min */
 446                 prec->old = 0;
 447         }
 448
 449         /*
 450          * if the queue length hits the hard limit, it's a forced drop.
 451          */
 452         if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
 453                 droptype = DTYPE_FORCED;
 454
 455         if (droptype != DTYPE_NODROP) {
 456                 /* always drop incoming packet (as opposed to randomdrop) */
 457                 for (i = dpindex; i < RIO_NDROPPREC; i++)
 458                         rp->rio_precstate[i].count = 0;
 459
 460                 if (droptype == DTYPE_EARLY)
 461                         rp->q_stats[dpindex].drop_unforced++;
 462                 else
 463                         rp->q_stats[dpindex].drop_forced++;
 464
 465                 IFCQ_CONVERT_LOCK(&rp->rio_ifp->if_snd);
 466                 m_freem(m);
 467                 return (CLASSQEQ_DROPPED);
 468         }
 469
 470         for (i = dpindex; i < RIO_NDROPPREC; i++)
 471                 rp->rio_precstate[i].qlen++;
 472
 473         /* save drop precedence index in mbuf hdr */
 474         RIOM_SET_PRECINDEX(&m->m_pkthdr, dpindex);
 475
 476         if (rp->rio_flags & RIOF_CLEARDSCP)
 477                 dsfield &= ~DSCP_MASK;
 478
 479 #if PF_ECN
 480         if (dsfield != odsfield)
 481                 write_dsfield(m, tag, dsfield);
 482 #endif /* PF_ECN */
 483
 484         _addq(q, m);
 485
 486         return (CLASSQEQ_SUCCESS);
 487 }
 488
 489 static struct mbuf *
 490 rio_getq_flow(struct rio *rp, class_queue_t *q, u_int32_t flow, boolean_t purge)
 491 {
 492 #pragma unused(purge)
 493         struct mbuf *m;
 494         int dpindex, i;
 495
 496         /* flow of 0 means head of queue */
 497         if ((m = ((flow == 0) ? _getq(q) : _getq_flow(q, flow))) == NULL)
 498                 return (NULL);
 499
 500         VERIFY(m->m_flags & M_PKTHDR);
 501
 502         dpindex = RIOM_GET_PRECINDEX(&m->m_pkthdr);
 503         for (i = dpindex; i < RIO_NDROPPREC; i++) {
 504                 if (--rp->rio_precstate[i].qlen == 0) {
 505                         if (rp->rio_precstate[i].idle == 0) {
 506                                 rp->rio_precstate[i].idle = 1;
 507                                 microuptime(&rp->rio_precstate[i].last);
 508                         }
 509                 }
 510         }
 511         return (m);
 512 }
 513
 514 struct mbuf *
 515 rio_getq(rio_t *rp, class_queue_t *q)
 516 {
 517         return (rio_getq_flow(rp, q, 0, FALSE));
 518 }
 519
 520 void
 521 rio_purgeq(struct rio *rp, class_queue_t *q, u_int32_t flow, u_int32_t *packets,
 522     u_int32_t *bytes)
 523 {
 524         u_int32_t cnt = 0, len = 0;
 525         struct mbuf *m;
 526
 527         IFCQ_CONVERT_LOCK(&rp->rio_ifp->if_snd);
 528
 529         while ((m = rio_getq_flow(rp, q, flow, TRUE)) != NULL) {
 530                 cnt++;
 531                 len += m_pktlen(m);
 532                 m_freem(m);
 533         }
 534
 535         if (packets != NULL)
 536                 *packets = cnt;
 537         if (bytes != NULL)
 538                 *bytes = len;
 539 }
 540
 541 void
 542 rio_updateq(rio_t *rp, cqev_t ev)
 543 {
 544 #pragma unused(rp, ev)
 545         /* nothing for now */
 546 }
 547
 548 int
 549 rio_suspendq(rio_t *rp, class_queue_t *q, boolean_t on)
 550 {
 551 #pragma unused(rp, q, on)
 552         return (ENOTSUP);
 553 }
 554 #endif /* CLASSQ_RIO */