sys/net/altq/altq_rio.c

   1 /*      $KAME: altq_rio.c,v 1.17 2003/07/10 12:07:49 kjc Exp $  */
   2 /*      $DragonFly: src/sys/net/altq/altq_rio.c,v 1.3 2006/12/22 23:44:55 swildner Exp $ */
   3
   4 /*
   5  * Copyright (C) 1998-2003
   6  *      Sony Computer Science Laboratories Inc.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29 /*
  30  * Copyright (c) 1990-1994 Regents of the University of California.
  31  * All rights reserved.
  32  *
  33  * Redistribution and use in source and binary forms, with or without
  34  * modification, are permitted provided that the following conditions
  35  * are met:
  36  * 1. Redistributions of source code must retain the above copyright
  37  *    notice, this list of conditions and the following disclaimer.
  38  * 2. Redistributions in binary form must reproduce the above copyright
  39  *    notice, this list of conditions and the following disclaimer in the
  40  *    documentation and/or other materials provided with the distribution.
  41  * 3. All advertising materials mentioning features or use of this software
  42  *    must display the following acknowledgement:
  43  *      This product includes software developed by the Computer Systems
  44  *      Engineering Group at Lawrence Berkeley Laboratory.
  45  * 4. Neither the name of the University nor of the Laboratory may be used
  46  *    to endorse or promote products derived from this software without
  47  *    specific prior written permission.
  48  *
  49  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  50  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  51  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  52  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  53  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  54  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  55  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  56  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  57  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  58  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  59  * SUCH DAMAGE.
  60  */
  61
  62 #include "opt_altq.h"
  63 #include "opt_inet.h"
  64 #include "opt_inet6.h"
  65
  66 #ifdef ALTQ_RIO /* rio is enabled by ALTQ_RIO option in opt_altq.h */
  67
  68 #include <sys/param.h>
  69 #include <sys/malloc.h>
  70 #include <sys/mbuf.h>
  71 #include <sys/socket.h>
  72 #include <sys/systm.h>
  73 #include <sys/errno.h>
  74
  75 #include <net/if.h>
  76
  77 #include <netinet/in.h>
  78 #include <netinet/in_systm.h>
  79 #include <netinet/ip.h>
  80 #ifdef INET6
  81 #include <netinet/ip6.h>
  82 #endif
  83
  84 #include <net/pf/pfvar.h>
  85 #include <net/altq/altq.h>
  86 #include <net/altq/altq_red.h>
  87 #include <net/altq/altq_rio.h>
  88
  89 /*
  90  * RIO: RED with IN/OUT bit
  91  *   described in
  92  *      "Explicit Allocation of Best Effort Packet Delivery Service"
  93  *      David D. Clark and Wenjia Fang, MIT Lab for Computer Science
  94  *      http://diffserv.lcs.mit.edu/Papers/exp-alloc-ddc-wf.{ps,pdf}
  95  *
  96  * this implementation is extended to support more than 2 drop precedence
  97  * values as described in RFC2597 (Assured Forwarding PHB Group).
  98  *
  99  */
 100 /*
 101  * AF DS (differentiated service) codepoints.
 102  * (classes can be mapped to CBQ or H-FSC classes.)
 103  *
 104  *      0   1   2   3   4   5   6   7
 105  *    +---+---+---+---+---+---+---+---+
 106  *    |   CLASS   |DropPre| 0 |  CU   |
 107  *    +---+---+---+---+---+---+---+---+
 108  *
 109  *    class 1: 001
 110  *    class 2: 010
 111  *    class 3: 011
 112  *    class 4: 100
 113  *
 114  *    low drop prec:    01
 115  *    medium drop prec: 10
 116  *    high drop prec:   11
 117  */
 118
 119 /* normal red parameters */
 120 #define W_WEIGHT        512     /* inverse of weight of EWMA (511/512) */
 121                                 /* q_weight = 0.00195 */
 122
 123 /* red parameters for a slow link */
 124 #define W_WEIGHT_1      128     /* inverse of weight of EWMA (127/128) */
 125                                 /* q_weight = 0.0078125 */
 126
 127 /* red parameters for a very slow link (e.g., dialup) */
 128 #define W_WEIGHT_2      64      /* inverse of weight of EWMA (63/64) */
 129                                 /* q_weight = 0.015625 */
 130
 131 /* fixed-point uses 12-bit decimal places */
 132 #define FP_SHIFT        12      /* fixed-point shift */
 133
 134 /* red parameters for drop probability */
 135 #define INV_P_MAX       10      /* inverse of max drop probability */
 136 #define TH_MIN           5      /* min threshold */
 137 #define TH_MAX          15      /* max threshold */
 138
 139 #define RIO_LIMIT       60      /* default max queue lenght */
 140 #define RIO_STATS               /* collect statistics */
 141
 142 /* default rio parameter values */
 143 static struct redparams default_rio_params[RIO_NDROPPREC] = {
 144   /* th_min,             th_max,     inv_pmax */
 145   { TH_MAX * 2 + TH_MIN, TH_MAX * 3, INV_P_MAX }, /* low drop precedence */
 146   { TH_MAX + TH_MIN,     TH_MAX * 2, INV_P_MAX }, /* medium drop precedence */
 147   { TH_MIN,              TH_MAX,     INV_P_MAX }  /* high drop precedence */
 148 };
 149
 150 /* internal function prototypes */
 151 static int      dscp2index(uint8_t);
 152 /* YYY Do we really need this? */
 153 #define AF_DROPPRECMASK         0x18
 154 #define DSCP_MASK       0xfc
 155
 156 rio_t *
 157 rio_alloc(int weight, struct redparams *params, int flags, int pkttime)
 158 {
 159         rio_t *rp;
 160         int w, i;
 161         int npkts_per_sec;
 162
 163         rp = kmalloc(sizeof(*rp), M_ALTQ, M_WAITOK | M_ZERO);
 164
 165         rp->rio_flags = flags;
 166         if (pkttime == 0)
 167                 /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */
 168                 rp->rio_pkttime = 800;
 169         else
 170                 rp->rio_pkttime = pkttime;
 171
 172         if (weight != 0)
 173                 rp->rio_weight = weight;
 174         else {
 175                 /* use default */
 176                 rp->rio_weight = W_WEIGHT;
 177
 178                 /* when the link is very slow, adjust red parameters */
 179                 npkts_per_sec = 1000000 / rp->rio_pkttime;
 180                 if (npkts_per_sec < 50) {
 181                         /* up to about 400Kbps */
 182                         rp->rio_weight = W_WEIGHT_2;
 183                 } else if (npkts_per_sec < 300) {
 184                         /* up to about 2.4Mbps */
 185                         rp->rio_weight = W_WEIGHT_1;
 186                 }
 187         }
 188
 189         /* calculate wshift.  weight must be power of 2 */
 190         w = rp->rio_weight;
 191         for (i = 0; w > 1; i++)
 192                 w = w >> 1;
 193         rp->rio_wshift = i;
 194         w = 1 << rp->rio_wshift;
 195         if (w != rp->rio_weight) {
 196                 kprintf("invalid weight value %d for red! use %d\n",
 197                        rp->rio_weight, w);
 198                 rp->rio_weight = w;
 199         }
 200
 201         /* allocate weight table */
 202         rp->rio_wtab = wtab_alloc(rp->rio_weight);
 203
 204         for (i = 0; i < RIO_NDROPPREC; i++) {
 205                 struct dropprec_state *prec = &rp->rio_precstate[i];
 206
 207                 prec->avg = 0;
 208                 prec->idle = 1;
 209
 210                 if (params == NULL || params[i].inv_pmax == 0)
 211                         prec->inv_pmax = default_rio_params[i].inv_pmax;
 212                 else
 213                         prec->inv_pmax = params[i].inv_pmax;
 214                 if (params == NULL || params[i].th_min == 0)
 215                         prec->th_min = default_rio_params[i].th_min;
 216                 else
 217                         prec->th_min = params[i].th_min;
 218                 if (params == NULL || params[i].th_max == 0)
 219                         prec->th_max = default_rio_params[i].th_max;
 220                 else
 221                         prec->th_max = params[i].th_max;
 222
 223                 /*
 224                  * th_min_s and th_max_s are scaled versions of th_min
 225                  * and th_max to be compared with avg.
 226                  */
 227                 prec->th_min_s = prec->th_min << (rp->rio_wshift + FP_SHIFT);
 228                 prec->th_max_s = prec->th_max << (rp->rio_wshift + FP_SHIFT);
 229
 230                 /*
 231                  * precompute probability denominator
 232                  *  probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point
 233                  */
 234                 prec->probd = (2 * (prec->th_max - prec->th_min)
 235                                * prec->inv_pmax) << FP_SHIFT;
 236
 237                 microtime(&prec->last);
 238         }
 239
 240         return (rp);
 241 }
 242
 243 void
 244 rio_destroy(rio_t *rp)
 245 {
 246         wtab_destroy(rp->rio_wtab);
 247         kfree(rp, M_ALTQ);
 248 }
 249
 250 void
 251 rio_getstats(rio_t *rp, struct redstats *sp)
 252 {
 253         int i;
 254
 255         for (i = 0; i < RIO_NDROPPREC; i++) {
 256                 bcopy(&rp->q_stats[i], sp, sizeof(struct redstats));
 257                 sp->q_avg = rp->rio_precstate[i].avg >> rp->rio_wshift;
 258                 sp++;
 259         }
 260 }
 261
 262 #if (RIO_NDROPPREC == 3)
 263 /*
 264  * internally, a drop precedence value is converted to an index
 265  * starting from 0.
 266  */
 267 static int
 268 dscp2index(uint8_t dscp)
 269 {
 270         int dpindex = dscp & AF_DROPPRECMASK;
 271
 272         if (dpindex == 0)
 273                 return (0);
 274         return ((dpindex >> 3) - 1);
 275 }
 276 #endif
 277
 278 #if 1
 279 /*
 280  * kludge: when a packet is dequeued, we need to know its drop precedence
 281  * in order to keep the queue length of each drop precedence.
 282  * use m_pkthdr.rcvif to pass this info.
 283  */
 284 #define RIOM_SET_PRECINDEX(m, idx)      \
 285         do { (m)->m_pkthdr.rcvif = (struct ifnet *)((long)(idx)); } while (0)
 286 #define RIOM_GET_PRECINDEX(m)   \
 287         ({ long idx; idx = (long)((m)->m_pkthdr.rcvif); \
 288         (m)->m_pkthdr.rcvif = NULL; idx; })
 289 #endif
 290
 291 int
 292 rio_addq(rio_t *rp, class_queue_t *q, struct mbuf *m, struct altq_pktattr *pktattr)
 293 {
 294         int avg, droptype;
 295         uint8_t dsfield, odsfield;
 296         int dpindex, i, n, t;
 297         struct timeval now;
 298         struct dropprec_state *prec;
 299
 300         dsfield = odsfield = read_dsfield(m, pktattr);
 301         dpindex = dscp2index(dsfield);
 302
 303         /*
 304          * update avg of the precedence states whose drop precedence
 305          * is larger than or equal to the drop precedence of the packet
 306          */
 307         now.tv_sec = 0;
 308         for (i = dpindex; i < RIO_NDROPPREC; i++) {
 309                 prec = &rp->rio_precstate[i];
 310                 avg = prec->avg;
 311                 if (prec->idle) {
 312                         prec->idle = 0;
 313                         if (now.tv_sec == 0)
 314                                 microtime(&now);
 315                         t = (now.tv_sec - prec->last.tv_sec);
 316                         if (t > 60)
 317                                 avg = 0;
 318                         else {
 319                                 t = t * 1000000 +
 320                                         (now.tv_usec - prec->last.tv_usec);
 321                                 n = t / rp->rio_pkttime;
 322                                 /* calculate (avg = (1 - Wq)^n * avg) */
 323                                 if (n > 0)
 324                                         avg = (avg >> FP_SHIFT) *
 325                                                 pow_w(rp->rio_wtab, n);
 326                         }
 327                 }
 328
 329                 /* run estimator. (avg is scaled by WEIGHT in fixed-point) */
 330                 avg += (prec->qlen << FP_SHIFT) - (avg >> rp->rio_wshift);
 331                 prec->avg = avg;                /* save the new value */
 332                 /*
 333                  * count keeps a tally of arriving traffic that has not
 334                  * been dropped.
 335                  */
 336                 prec->count++;
 337         }
 338
 339         prec = &rp->rio_precstate[dpindex];
 340         avg = prec->avg;
 341
 342         /* see if we drop early */
 343         droptype = DTYPE_NODROP;
 344         if (avg >= prec->th_min_s && prec->qlen > 1) {
 345                 if (avg >= prec->th_max_s) {
 346                         /* avg >= th_max: forced drop */
 347                         droptype = DTYPE_FORCED;
 348                 } else if (prec->old == 0) {
 349                         /* first exceeds th_min */
 350                         prec->count = 1;
 351                         prec->old = 1;
 352                 } else if (drop_early((avg - prec->th_min_s) >> rp->rio_wshift,
 353                                       prec->probd, prec->count)) {
 354                         /* unforced drop by red */
 355                         droptype = DTYPE_EARLY;
 356                 }
 357         } else {
 358                 /* avg < th_min */
 359                 prec->old = 0;
 360         }
 361
 362         /*
 363          * if the queue length hits the hard limit, it's a forced drop.
 364          */
 365         if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
 366                 droptype = DTYPE_FORCED;
 367
 368         if (droptype != DTYPE_NODROP) {
 369                 /* always drop incoming packet (as opposed to randomdrop) */
 370                 for (i = dpindex; i < RIO_NDROPPREC; i++)
 371                         rp->rio_precstate[i].count = 0;
 372 #ifdef RIO_STATS
 373                 if (droptype == DTYPE_EARLY)
 374                         rp->q_stats[dpindex].drop_unforced++;
 375                 else
 376                         rp->q_stats[dpindex].drop_forced++;
 377                 PKTCNTR_ADD(&rp->q_stats[dpindex].drop_cnt, m_pktlen(m));
 378 #endif
 379                 m_freem(m);
 380                 return (-1);
 381         }
 382
 383         for (i = dpindex; i < RIO_NDROPPREC; i++)
 384                 rp->rio_precstate[i].qlen++;
 385
 386         /* save drop precedence index in mbuf hdr */
 387         RIOM_SET_PRECINDEX(m, dpindex);
 388
 389         if (rp->rio_flags & RIOF_CLEARDSCP)
 390                 dsfield &= ~DSCP_MASK;
 391
 392         if (dsfield != odsfield)
 393                 write_dsfield(m, pktattr, dsfield);
 394
 395         _addq(q, m);
 396
 397 #ifdef RIO_STATS
 398         PKTCNTR_ADD(&rp->q_stats[dpindex].xmit_cnt, m_pktlen(m));
 399 #endif
 400         return (0);
 401 }
 402
 403 struct mbuf *
 404 rio_getq(rio_t *rp, class_queue_t *q)
 405 {
 406         struct mbuf *m;
 407         int dpindex, i;
 408
 409         if ((m = _getq(q)) == NULL)
 410                 return (NULL);
 411
 412         dpindex = RIOM_GET_PRECINDEX(m);
 413         for (i = dpindex; i < RIO_NDROPPREC; i++) {
 414                 if (--rp->rio_precstate[i].qlen == 0) {
 415                         if (rp->rio_precstate[i].idle == 0) {
 416                                 rp->rio_precstate[i].idle = 1;
 417                                 microtime(&rp->rio_precstate[i].last);
 418                         }
 419                 }
 420         }
 421         return (m);
 422 }
 423
 424 #endif /* ALTQ_RIO */