bsd/net/classq/classq_blue.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 /*      $NetBSD: altq_blue.c,v 1.21 2006/11/16 01:32:37 christos Exp $  */
  30 /*      $KAME: altq_blue.c,v 1.15 2005/04/13 03:44:24 suz Exp $ */
  31
  32 /*
  33  * Copyright (C) 1997-2002
  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 /*
  59  * Copyright (c) 1990-1994 Regents of the University of California.
  60  * All rights reserved.
  61  *
  62  * Redistribution and use in source and binary forms, with or without
  63  * modification, are permitted provided that the following conditions
  64  * are met:
  65  * 1. Redistributions of source code must retain the above copyright
  66  *    notice, this list of conditions and the following disclaimer.
  67  * 2. Redistributions in binary form must reproduce the above copyright
  68  *    notice, this list of conditions and the following disclaimer in the
  69  *    documentation and/or other materials provided with the distribution.
  70  * 3. All advertising materials mentioning features or use of this software
  71  *    must display the following acknowledgement:
  72  *      This product includes software developed by the Computer Systems
  73  *      Engineering Group at Lawrence Berkeley Laboratory.
  74  * 4. Neither the name of the University nor of the Laboratory may be used
  75  *    to endorse or promote products derived from this software without
  76  *    specific prior written permission.
  77  *
  78  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  79  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  80  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  81  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  82  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  83  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  84  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  85  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  86  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  87  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  88  * SUCH DAMAGE.
  89  */
  90
  91 #include <sys/cdefs.h>
  92
  93 #if CLASSQ_BLUE
  94
  95 #include <sys/param.h>
  96 #include <sys/malloc.h>
  97 #include <sys/mbuf.h>
  98 #include <sys/socket.h>
  99 #include <sys/sockio.h>
 100 #include <sys/systm.h>
 101 #include <sys/syslog.h>
 102 #include <sys/proc.h>
 103 #include <sys/errno.h>
 104 #include <sys/kernel.h>
 105 #include <sys/kauth.h>
 106
 107 #include <kern/zalloc.h>
 108
 109 #include <net/if.h>
 110 #include <net/if_var.h>
 111 #include <net/if_types.h>
 112
 113 #include <netinet/in.h>
 114 #include <netinet/in_systm.h>
 115 #include <netinet/ip.h>
 116 #if INET6
 117 #include <netinet/ip6.h>
 118 #endif
 119
 120 #include <net/classq/classq_blue.h>
 121 #include <net/net_osdep.h>
 122 #include <dev/random/randomdev.h>
 123
 124 /*
 125  * Blue is proposed and implemented by Wu-chang Feng <wuchang@eecs.umich.edu>.
 126  * more information on Blue is available from
 127  * http://www.eecs.umich.edu/~wuchang/blue/
 128  */
 129
 130 #define BLUE_LIMIT      200             /* default max queue lenght */
 131
 132 #define BLUE_ZONE_MAX   32              /* maximum elements in zone */
 133 #define BLUE_ZONE_NAME  "classq_blue"   /* zone name */
 134
 135 static unsigned int blue_size;          /* size of zone element */
 136 static struct zone *blue_zone;          /* zone for blue */
 137
 138 /* internal function prototypes */
 139 static struct mbuf *blue_getq_flow(struct blue *, class_queue_t *,
 140     u_int32_t, boolean_t);
 141 static int blue_drop_early(struct blue *);
 142
 143 void
 144 blue_init(void)
 145 {
 146         _CASSERT(BLUEF_ECN4 == CLASSQF_ECN4);
 147         _CASSERT(BLUEF_ECN6 == CLASSQF_ECN6);
 148
 149         blue_size = sizeof (struct blue);
 150         blue_zone = zinit(blue_size, BLUE_ZONE_MAX * blue_size,
 151             0, BLUE_ZONE_NAME);
 152         if (blue_zone == NULL) {
 153                 panic("%s: failed allocating %s", __func__, BLUE_ZONE_NAME);
 154                 /* NOTREACHED */
 155         }
 156         zone_change(blue_zone, Z_EXPAND, TRUE);
 157         zone_change(blue_zone, Z_CALLERACCT, TRUE);
 158 }
 159
 160 /*
 161  * blue support routines
 162  */
 163 struct blue *
 164 blue_alloc(struct ifnet *ifp, u_int32_t max_pmark, u_int32_t hold_time,
 165     u_int32_t flags)
 166 {
 167         struct blue *bp;
 168
 169         VERIFY(ifp != NULL);
 170
 171         bp = zalloc(blue_zone);
 172         if (bp == NULL)
 173                 return (NULL);
 174
 175         bzero(bp, blue_size);
 176         bp->blue_idle = 1;
 177         bp->blue_ifp = ifp;
 178         bp->blue_flags = (flags & BLUEF_USERFLAGS);
 179 #if !PF_ECN
 180         if (bp->blue_flags & BLUEF_ECN) {
 181                 bp->blue_flags &= ~BLUEF_ECN;
 182                 log(LOG_ERR, "%s: BLUE ECN not available; ignoring "
 183                     "BLUEF_ECN flag!\n", if_name(ifp));
 184         }
 185 #endif /* !PF_ECN */
 186
 187
 188         if (max_pmark == 0)
 189                 bp->blue_max_pmark = 1000;
 190         else
 191                 bp->blue_max_pmark = max_pmark;
 192
 193         if (hold_time == 0)
 194                 bp->blue_hold_time = 50000;
 195         else
 196                 bp->blue_hold_time = hold_time;
 197
 198         microuptime(&bp->blue_last);
 199
 200         return (bp);
 201 }
 202
 203 void
 204 blue_destroy(struct blue *bp)
 205 {
 206         zfree(blue_zone, bp);
 207 }
 208
 209 void
 210 blue_getstats(struct blue *bp, struct blue_stats *sp)
 211 {
 212         sp->q_pmark             = bp->blue_pmark;
 213         sp->drop_forced         = bp->blue_stats.drop_forced;
 214         sp->drop_unforced       = bp->blue_stats.drop_unforced;
 215         sp->marked_packets      = bp->blue_stats.marked_packets;
 216 }
 217
 218 #define DTYPE_NODROP    0       /* no drop */
 219 #define DTYPE_FORCED    1       /* a "forced" drop */
 220 #define DTYPE_EARLY     2       /* an "unforced" (early) drop */
 221
 222 int
 223 blue_addq(struct blue *bp, class_queue_t *q, struct mbuf *m,
 224     struct pf_mtag *tag)
 225 {
 226 #if !PF_ECN
 227 #pragma unused(tag)
 228 #endif /* !PF_ECN */
 229         int droptype;
 230
 231         /*
 232          * if we were idle, this is an enqueue onto an empty queue
 233          * and we should decrement marking probability
 234          */
 235         if (bp->blue_idle) {
 236                 struct timeval now;
 237                 u_int32_t t;
 238
 239                 bp->blue_idle = 0;
 240                 microuptime(&now);
 241                 t = (now.tv_sec - bp->blue_last.tv_sec);
 242                 if (t > 1) {
 243                         bp->blue_pmark = 1;
 244                         microuptime(&bp->blue_last);
 245                 } else {
 246                         t = t * 1000000 + (now.tv_usec - bp->blue_last.tv_usec);
 247                         if (t > bp->blue_hold_time) {
 248                                 bp->blue_pmark--;
 249                                 if (bp->blue_pmark < 0)
 250                                         bp->blue_pmark = 0;
 251                                 microuptime(&bp->blue_last);
 252                         }
 253                 }
 254         }
 255
 256         /* see if we drop early */
 257         droptype = DTYPE_NODROP;
 258         if (blue_drop_early(bp) && qlen(q) > 1) {
 259                 /* mark or drop by blue */
 260 #if PF_ECN
 261                 if ((bp->blue_flags & BLUEF_ECN) &&
 262                     (tag->pftag_proto == IPPROTO_TCP) && /* only for TCP */
 263                     mark_ecn(m, tag, bp->blue_flags)) {
 264                         /* successfully marked.  do not drop. */
 265                         bp->blue_stats.marked_packets++;
 266                 } else
 267 #endif /* PF_ECN */
 268                 {
 269                         /* unforced drop by blue */
 270                         droptype = DTYPE_EARLY;
 271                 }
 272         }
 273
 274         /* if the queue length hits the hard limit, it's a forced drop */
 275         if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
 276                 droptype = DTYPE_FORCED;
 277
 278         /* if successful or forced drop, enqueue this packet. */
 279         if (droptype != DTYPE_EARLY)
 280                 _addq(q, m);
 281
 282         if (droptype != DTYPE_NODROP) {
 283                 if (droptype == DTYPE_EARLY) {
 284                         /* drop the incoming packet */
 285                         bp->blue_stats.drop_unforced++;
 286                 } else {
 287                         struct timeval now;
 288                         u_int32_t t;
 289                         /* forced drop, select a victim packet in the queue. */
 290                         m = _getq_random(q);
 291                         microuptime(&now);
 292                         t = (now.tv_sec - bp->blue_last.tv_sec);
 293                         t = t * 1000000 + (now.tv_usec - bp->blue_last.tv_usec);
 294                         if (t > bp->blue_hold_time) {
 295                                 bp->blue_pmark += bp->blue_max_pmark >> 3;
 296                                 if (bp->blue_pmark > bp->blue_max_pmark)
 297                                         bp->blue_pmark = bp->blue_max_pmark;
 298                                 microuptime(&bp->blue_last);
 299                         }
 300                         bp->blue_stats.drop_forced++;
 301                 }
 302                 IFCQ_CONVERT_LOCK(&bp->blue_ifp->if_snd);
 303                 m_freem(m);
 304                 return (CLASSQEQ_DROPPED);
 305         }
 306         /* successfully queued */
 307         return (CLASSQEQ_SUCCESS);
 308 }
 309
 310 static struct mbuf *
 311 blue_getq_flow(struct blue *bp, class_queue_t *q, u_int32_t flow,
 312     boolean_t purge)
 313 {
 314 #pragma unused(purge)
 315         struct mbuf *m;
 316
 317         /* flow of 0 means head of queue */
 318         if ((m = ((flow == 0) ? _getq(q) : _getq_flow(q, flow))) == NULL) {
 319                 if (bp->blue_idle == 0) {
 320                         bp->blue_idle = 1;
 321                         microuptime(&bp->blue_last);
 322                 }
 323                 return (NULL);
 324         }
 325
 326         bp->blue_idle = 0;
 327         return (m);
 328 }
 329
 330 struct mbuf *
 331 blue_getq(struct blue *bp, class_queue_t *q)
 332 {
 333         return (blue_getq_flow(bp, q, 0, FALSE));
 334 }
 335
 336 void
 337 blue_purgeq(struct blue *bp, class_queue_t *q, u_int32_t flow,
 338     u_int32_t *packets, u_int32_t *bytes)
 339 {
 340         u_int32_t cnt = 0, len = 0;
 341         struct mbuf *m;
 342
 343         IFCQ_CONVERT_LOCK(&bp->blue_ifp->if_snd);
 344
 345         while ((m = blue_getq_flow(bp, q, flow, TRUE)) != NULL) {
 346                 cnt++;
 347                 len += m_pktlen(m);
 348                 m_freem(m);
 349         }
 350
 351         if (packets != NULL)
 352                 *packets = cnt;
 353         if (bytes != NULL)
 354                 *bytes = len;
 355 }
 356
 357 /*
 358  * early-drop probability is kept in blue_pmark
 359  */
 360 static int
 361 blue_drop_early(struct blue *bp)
 362 {
 363         if ((RandomULong() % (unsigned)bp->blue_max_pmark) <
 364             (unsigned)bp->blue_pmark) {
 365                 /* drop or mark */
 366                 return (1);
 367         }
 368         /* no drop/mark */
 369         return (0);
 370 }
 371
 372 void
 373 blue_updateq(struct blue *bp, cqev_t ev)
 374 {
 375 #pragma unused(bp, ev)
 376         /* nothing for now */
 377 }
 378
 379 int
 380 blue_suspendq(struct blue *bp, class_queue_t *q, boolean_t on)
 381 {
 382 #pragma unused(bp, q, on)
 383         return (ENOTSUP);
 384 }
 385 #endif /* CLASSQ_BLUE */