bsd/net/classq/classq_rio.c

   1 /*
   2  * Copyright (c) 2007-2012 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/errno.h>
 100 #include <sys/kauth.h>
 101 #include <sys/kauth.h>
 102
 103 #include <kern/zalloc.h>
 104
 105 #include <net/if.h>
 106
 107 #include <netinet/in.h>
 108 #include <netinet/in_systm.h>
 109 #include <netinet/ip.h>
 110 #if INET6
 111 #include <netinet/ip6.h>
 112 #endif
 113
 114 #include <net/classq/classq_red.h>
 115 #include <net/classq/classq_rio.h>
 116
 117 /*
 118  * RIO: RED with IN/OUT bit
 119  *   described in
 120  *      "Explicit Allocation of Best Effort Packet Delivery Service"
 121  *      David D. Clark and Wenjia Fang, MIT Lab for Computer Science
 122  *      http://diffserv.lcs.mit.edu/Papers/exp-alloc-ddc-wf.{ps,pdf}
 123  *
 124  * this implementation is extended to support more than 2 drop precedence
 125  * values as described in RFC2597 (Assured Forwarding PHB Group).
 126  *
 127  */
 128 /*
 129  * AF DS (differentiated service) codepoints.
 130  * (classes can be mapped to CBQ or H-FSC classes.)
 131  *
 132  *      0   1   2   3   4   5   6   7
 133  *    +---+---+---+---+---+---+---+---+
 134  *    |   CLASS   |DropPre| 0 |  CU   |
 135  *    +---+---+---+---+---+---+---+---+
 136  *
 137  *    class 1: 001
 138  *    class 2: 010
 139  *    class 3: 011
 140  *    class 4: 100
 141  *
 142  *    low drop prec:    01
 143  *    medium drop prec: 10
 144  *    high drop prec:   11
 145  */
 146
 147 /* normal red parameters */
 148 #define W_WEIGHT        512     /* inverse of weight of EWMA (511/512) */
 149                                 /* q_weight = 0.00195 */
 150
 151 /* red parameters for a slow link */
 152 #define W_WEIGHT_1      128     /* inverse of weight of EWMA (127/128) */
 153                                 /* q_weight = 0.0078125 */
 154
 155 /* red parameters for a very slow link (e.g., dialup) */
 156 #define W_WEIGHT_2      64      /* inverse of weight of EWMA (63/64) */
 157                                 /* q_weight = 0.015625 */
 158
 159 /* fixed-point uses 12-bit decimal places */
 160 #define FP_SHIFT        12      /* fixed-point shift */
 161
 162 /* red parameters for drop probability */
 163 #define INV_P_MAX       10      /* inverse of max drop probability */
 164 #define TH_MIN           5      /* min threshold */
 165 #define TH_MAX          15      /* max threshold */
 166
 167 #define RIO_LIMIT       60      /* default max queue lenght */
 168
 169 /* default rio parameter values */
 170 static struct redparams default_rio_params[RIO_NDROPPREC] = {
 171   /* th_min,             th_max,     inv_pmax */
 172   { TH_MAX * 2 + TH_MIN, TH_MAX * 3, INV_P_MAX }, /* low drop precedence */
 173   { TH_MAX + TH_MIN,     TH_MAX * 2, INV_P_MAX }, /* medium drop precedence */
 174   { TH_MIN,              TH_MAX,     INV_P_MAX }  /* high drop precedence */
 175 };
 176
 177 #define RIO_ZONE_MAX    32              /* maximum elements in zone */
 178 #define RIO_ZONE_NAME   "classq_rio"    /* zone name */
 179
 180 static unsigned int rio_size;           /* size of zone element */
 181 static struct zone *rio_zone;           /* zone for rio */
 182
 183 /* internal function prototypes */
 184 static struct mbuf *rio_getq_flow(struct rio *, class_queue_t *,
 185     u_int32_t, boolean_t);
 186 static int dscp2index(u_int8_t);
 187
 188 void
 189 rio_init(void)
 190 {
 191         _CASSERT(RIOF_ECN4 == CLASSQF_ECN4);
 192         _CASSERT(RIOF_ECN6 == CLASSQF_ECN6);
 193
 194         rio_size = sizeof (rio_t);
 195         rio_zone = zinit(rio_size, RIO_ZONE_MAX * rio_size,
 196             0, RIO_ZONE_NAME);
 197         if (rio_zone == NULL) {
 198                 panic("%s: failed allocating %s", __func__, RIO_ZONE_NAME);
 199                 /* NOTREACHED */
 200         }
 201         zone_change(rio_zone, Z_EXPAND, TRUE);
 202         zone_change(rio_zone, Z_CALLERACCT, TRUE);
 203 }
 204
 205 rio_t *
 206 rio_alloc(struct ifnet *ifp, int weight, struct redparams *params,
 207     int flags, int pkttime)
 208 {
 209         rio_t   *rp;
 210         int      w, i;
 211         int      npkts_per_sec;
 212
 213         VERIFY(ifp != NULL);
 214
 215         rp = zalloc(rio_zone);
 216         if (rp == NULL)
 217                 return (NULL);
 218
 219         bzero(rp, rio_size);
 220         rp->rio_flags = (flags & RIOF_USERFLAGS);
 221         rp->rio_ifp = ifp;
 222
 223         if (pkttime == 0)
 224                 /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */
 225                 rp->rio_pkttime = 800;
 226         else
 227                 rp->rio_pkttime = pkttime;
 228
 229         if (weight != 0)
 230                 rp->rio_weight = weight;
 231         else {
 232                 /* use default */
 233                 rp->rio_weight = W_WEIGHT;
 234
 235                 /* when the link is very slow, adjust red parameters */
 236                 npkts_per_sec = 1000000 / rp->rio_pkttime;
 237                 if (npkts_per_sec < 50) {
 238                         /* up to about 400Kbps */
 239                         rp->rio_weight = W_WEIGHT_2;
 240                 } else if (npkts_per_sec < 300) {
 241                         /* up to about 2.4Mbps */
 242                         rp->rio_weight = W_WEIGHT_1;
 243                 }
 244         }
 245
 246         /* calculate wshift.  weight must be power of 2 */
 247         w = rp->rio_weight;
 248         for (i = 0; w > 1; i++)
 249                 w = w >> 1;
 250         rp->rio_wshift = i;
 251         w = 1 << rp->rio_wshift;
 252         if (w != rp->rio_weight) {
 253                 printf("invalid weight value %d for red! use %d\n",
 254                     rp->rio_weight, w);
 255                 rp->rio_weight = w;
 256         }
 257
 258         /* allocate weight table */
 259         rp->rio_wtab = wtab_alloc(rp->rio_weight);
 260         if (rp->rio_wtab == NULL) {
 261                 rio_destroy(rp);
 262                 return (NULL);
 263         }
 264
 265         for (i = 0; i < RIO_NDROPPREC; i++) {
 266                 struct dropprec_state *prec = &rp->rio_precstate[i];
 267
 268                 prec->avg = 0;
 269                 prec->idle = 1;
 270
 271                 if (params == NULL || params[i].inv_pmax == 0)
 272                         prec->inv_pmax = default_rio_params[i].inv_pmax;
 273                 else
 274                         prec->inv_pmax = params[i].inv_pmax;
 275                 if (params == NULL || params[i].th_min == 0)
 276                         prec->th_min = default_rio_params[i].th_min;
 277                 else
 278                         prec->th_min = params[i].th_min;
 279                 if (params == NULL || params[i].th_max == 0)
 280                         prec->th_max = default_rio_params[i].th_max;
 281                 else
 282                         prec->th_max = params[i].th_max;
 283
 284                 /*
 285                  * th_min_s and th_max_s are scaled versions of th_min
 286                  * and th_max to be compared with avg.
 287                  */
 288                 prec->th_min_s = prec->th_min << (rp->rio_wshift + FP_SHIFT);
 289                 prec->th_max_s = prec->th_max << (rp->rio_wshift + FP_SHIFT);
 290
 291                 /*
 292                  * precompute probability denominator
 293                  *  probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point
 294                  */
 295                 prec->probd = (2 * (prec->th_max - prec->th_min) *
 296                     prec->inv_pmax) << FP_SHIFT;
 297
 298                 microuptime(&prec->last);
 299         }
 300
 301         return (rp);
 302 }
 303
 304 void
 305 rio_destroy(rio_t *rp)
 306 {
 307         if (rp->rio_wtab != NULL) {
 308                 wtab_destroy(rp->rio_wtab);
 309                 rp->rio_wtab = NULL;
 310         }
 311         zfree(rio_zone, rp);
 312 }
 313
 314 void
 315 rio_getstats(rio_t *rp, struct red_stats *sp)
 316 {
 317         int     i;
 318
 319         for (i = 0; i < RIO_NDROPPREC; i++) {
 320                 bcopy(&rp->q_stats[i], sp, sizeof (struct red_stats));
 321                 sp->q_avg = rp->rio_precstate[i].avg >> rp->rio_wshift;
 322                 sp++;
 323         }
 324 }
 325
 326 #if (RIO_NDROPPREC == 3)
 327 /*
 328  * internally, a drop precedence value is converted to an index
 329  * starting from 0.
 330  */
 331 static int
 332 dscp2index(u_int8_t dscp)
 333 {
 334 #define AF_DROPPRECMASK 0x18
 335
 336         int     dpindex = dscp & AF_DROPPRECMASK;
 337
 338         if (dpindex == 0)
 339                 return (0);
 340         return ((dpindex >> 3) - 1);
 341 }
 342 #endif
 343
 344 #define RIOM_SET_PRECINDEX(t, idx) do {                 \
 345         (t)->pftag_qpriv32 = (idx);                     \
 346 } while (0)
 347
 348 #define RIOM_GET_PRECINDEX(t)                           \
 349         ({ u_int32_t idx; idx = (t)->pftag_qpriv32;     \
 350         RIOM_SET_PRECINDEX(t, 0); idx; })
 351
 352 int
 353 rio_addq(rio_t *rp, class_queue_t *q, struct mbuf *m, struct pf_mtag *tag)
 354 {
 355 #define DSCP_MASK       0xfc
 356         int                      avg, droptype;
 357         u_int8_t                 dsfield, odsfield;
 358         int                      dpindex, i, n, t;
 359         struct timeval           now;
 360         struct dropprec_state   *prec;
 361
 362         dsfield = odsfield = read_dsfield(m, tag);
 363         dpindex = dscp2index(dsfield);
 364
 365         /*
 366          * update avg of the precedence states whose drop precedence
 367          * is larger than or equal to the drop precedence of the packet
 368          */
 369         now.tv_sec = 0;
 370         for (i = dpindex; i < RIO_NDROPPREC; i++) {
 371                 prec = &rp->rio_precstate[i];
 372                 avg = prec->avg;
 373                 if (prec->idle) {
 374                         prec->idle = 0;
 375                         if (now.tv_sec == 0)
 376                                 microuptime(&now);
 377                         t = (now.tv_sec - prec->last.tv_sec);
 378                         if (t > 60)
 379                                 avg = 0;
 380                         else {
 381                                 t = t * 1000000 +
 382                                     (now.tv_usec - prec->last.tv_usec);
 383                                 n = t / rp->rio_pkttime;
 384                                 /* calculate (avg = (1 - Wq)^n * avg) */
 385                                 if (n > 0) {
 386                                         avg = (avg >> FP_SHIFT) *
 387                                             pow_w(rp->rio_wtab, n);
 388                                 }
 389                         }
 390                 }
 391
 392                 /* run estimator. (avg is scaled by WEIGHT in fixed-point) */
 393                 avg += (prec->qlen << FP_SHIFT) - (avg >> rp->rio_wshift);
 394                 prec->avg = avg;                /* save the new value */
 395                 /*
 396                  * count keeps a tally of arriving traffic that has not
 397                  * been dropped.
 398                  */
 399                 prec->count++;
 400         }
 401
 402         prec = &rp->rio_precstate[dpindex];
 403         avg = prec->avg;
 404
 405         /* see if we drop early */
 406         droptype = DTYPE_NODROP;
 407         if (avg >= prec->th_min_s && prec->qlen > 1) {
 408                 if (avg >= prec->th_max_s) {
 409                         /* avg >= th_max: forced drop */
 410                         droptype = DTYPE_FORCED;
 411                 } else if (prec->old == 0) {
 412                         /* first exceeds th_min */
 413                         prec->count = 1;
 414                         prec->old = 1;
 415                 } else if (drop_early((avg - prec->th_min_s) >> rp->rio_wshift,
 416                     prec->probd, prec->count)) {
 417                         /* unforced drop by red */
 418                         droptype = DTYPE_EARLY;
 419                 }
 420         } else {
 421                 /* avg < th_min */
 422                 prec->old = 0;
 423         }
 424
 425         /*
 426          * if the queue length hits the hard limit, it's a forced drop.
 427          */
 428         if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
 429                 droptype = DTYPE_FORCED;
 430
 431         if (droptype != DTYPE_NODROP) {
 432                 /* always drop incoming packet (as opposed to randomdrop) */
 433                 for (i = dpindex; i < RIO_NDROPPREC; i++)
 434                         rp->rio_precstate[i].count = 0;
 435
 436                 if (droptype == DTYPE_EARLY)
 437                         rp->q_stats[dpindex].drop_unforced++;
 438                 else
 439                         rp->q_stats[dpindex].drop_forced++;
 440
 441                 IFCQ_CONVERT_LOCK(&rp->rio_ifp->if_snd);
 442                 m_freem(m);
 443                 return (CLASSQEQ_DROPPED);
 444         }
 445
 446         for (i = dpindex; i < RIO_NDROPPREC; i++)
 447                 rp->rio_precstate[i].qlen++;
 448
 449         /* save drop precedence index in mbuf hdr */
 450         RIOM_SET_PRECINDEX(tag, dpindex);
 451
 452         if (rp->rio_flags & RIOF_CLEARDSCP)
 453                 dsfield &= ~DSCP_MASK;
 454
 455         if (dsfield != odsfield)
 456                 write_dsfield(m, tag, dsfield);
 457
 458         _addq(q, m);
 459
 460         return (CLASSQEQ_SUCCESS);
 461 }
 462
 463 static struct mbuf *
 464 rio_getq_flow(struct rio *rp, class_queue_t *q, u_int32_t flow, boolean_t purge)
 465 {
 466 #pragma unused(purge)
 467         struct mbuf *m;
 468         int dpindex, i;
 469
 470         /* flow of 0 means head of queue */
 471         if ((m = ((flow == 0) ? _getq(q) : _getq_flow(q, flow))) == NULL)
 472                 return (NULL);
 473
 474         VERIFY(m->m_flags & M_PKTHDR);
 475
 476         dpindex = RIOM_GET_PRECINDEX(m_pftag(m));
 477         for (i = dpindex; i < RIO_NDROPPREC; i++) {
 478                 if (--rp->rio_precstate[i].qlen == 0) {
 479                         if (rp->rio_precstate[i].idle == 0) {
 480                                 rp->rio_precstate[i].idle = 1;
 481                                 microuptime(&rp->rio_precstate[i].last);
 482                         }
 483                 }
 484         }
 485         return (m);
 486 }
 487
 488 struct mbuf *
 489 rio_getq(rio_t *rp, class_queue_t *q)
 490 {
 491         return (rio_getq_flow(rp, q, 0, FALSE));
 492 }
 493
 494 void
 495 rio_purgeq(struct rio *rp, class_queue_t *q, u_int32_t flow, u_int32_t *packets,
 496     u_int32_t *bytes)
 497 {
 498         u_int32_t cnt = 0, len = 0;
 499         struct mbuf *m;
 500
 501         IFCQ_CONVERT_LOCK(&rp->rio_ifp->if_snd);
 502
 503         while ((m = rio_getq_flow(rp, q, flow, TRUE)) != NULL) {
 504                 cnt++;
 505                 len += m_pktlen(m);
 506                 m_freem(m);
 507         }
 508
 509         if (packets != NULL)
 510                 *packets = cnt;
 511         if (bytes != NULL)
 512                 *bytes = len;
 513 }
 514
 515 void
 516 rio_updateq(rio_t *rp, cqev_t ev)
 517 {
 518 #pragma unused(rp, ev)
 519         /* nothing for now */
 520 }
 521
 522 int
 523 rio_suspendq(rio_t *rp, class_queue_t *q, boolean_t on)
 524 {
 525 #pragma unused(rp, q, on)
 526         return (ENOTSUP);
 527 }
 528 #endif /* CLASSQ_RIO */