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/proc.h>
 102 #include <sys/errno.h>
 103 #include <sys/kernel.h>
 104 #include <sys/kauth.h>
 105
 106 #include <kern/zalloc.h>
 107
 108 #include <net/if.h>
 109 #include <net/if_var.h>
 110 #include <net/if_types.h>
 111
 112 #include <netinet/in.h>
 113 #include <netinet/in_systm.h>
 114 #include <netinet/ip.h>
 115 #if INET6
 116 #include <netinet/ip6.h>
 117 #endif
 118
 119 #include <net/classq/classq_blue.h>
 120 #include <net/net_osdep.h>
 121
 122 /*
 123  * Blue is proposed and implemented by Wu-chang Feng <wuchang@eecs.umich.edu>.
 124  * more information on Blue is available from
 125  * http://www.eecs.umich.edu/~wuchang/blue/
 126  */
 127
 128 #define BLUE_LIMIT      200             /* default max queue lenght */
 129
 130 #define BLUE_ZONE_MAX   32              /* maximum elements in zone */
 131 #define BLUE_ZONE_NAME  "classq_blue"   /* zone name */
 132
 133 static unsigned int blue_size;          /* size of zone element */
 134 static struct zone *blue_zone;          /* zone for blue */
 135
 136 /* internal function prototypes */
 137 static struct mbuf *blue_getq_flow(struct blue *, class_queue_t *,
 138     u_int32_t, boolean_t);
 139 static int blue_drop_early(struct blue *);
 140
 141 void
 142 blue_init(void)
 143 {
 144         _CASSERT(BLUEF_ECN4 == CLASSQF_ECN4);
 145         _CASSERT(BLUEF_ECN6 == CLASSQF_ECN6);
 146
 147         blue_size = sizeof (struct blue);
 148         blue_zone = zinit(blue_size, BLUE_ZONE_MAX * blue_size,
 149             0, BLUE_ZONE_NAME);
 150         if (blue_zone == NULL) {
 151                 panic("%s: failed allocating %s", __func__, BLUE_ZONE_NAME);
 152                 /* NOTREACHED */
 153         }
 154         zone_change(blue_zone, Z_EXPAND, TRUE);
 155         zone_change(blue_zone, Z_CALLERACCT, TRUE);
 156 }
 157
 158 /*
 159  * blue support routines
 160  */
 161 struct blue *
 162 blue_alloc(struct ifnet *ifp, u_int32_t max_pmark, u_int32_t hold_time,
 163     u_int32_t flags)
 164 {
 165         struct blue *bp;
 166
 167         VERIFY(ifp != NULL);
 168
 169         bp = zalloc(blue_zone);
 170         if (bp == NULL)
 171                 return (NULL);
 172
 173         bzero(bp, blue_size);
 174         bp->blue_idle = 1;
 175         bp->blue_flags = (flags & BLUEF_USERFLAGS);
 176         bp->blue_ifp = ifp;
 177
 178         if (max_pmark == 0)
 179                 bp->blue_max_pmark = 1000;
 180         else
 181                 bp->blue_max_pmark = max_pmark;
 182
 183         if (hold_time == 0)
 184                 bp->blue_hold_time = 50000;
 185         else
 186                 bp->blue_hold_time = hold_time;
 187
 188         microuptime(&bp->blue_last);
 189
 190         return (bp);
 191 }
 192
 193 void
 194 blue_destroy(struct blue *bp)
 195 {
 196         zfree(blue_zone, bp);
 197 }
 198
 199 void
 200 blue_getstats(struct blue *bp, struct blue_stats *sp)
 201 {
 202         sp->q_pmark             = bp->blue_pmark;
 203         sp->drop_forced         = bp->blue_stats.drop_forced;
 204         sp->drop_unforced       = bp->blue_stats.drop_unforced;
 205         sp->marked_packets      = bp->blue_stats.marked_packets;
 206 }
 207
 208 #define DTYPE_NODROP    0       /* no drop */
 209 #define DTYPE_FORCED    1       /* a "forced" drop */
 210 #define DTYPE_EARLY     2       /* an "unforced" (early) drop */
 211
 212 int
 213 blue_addq(struct blue *bp, class_queue_t *q, struct mbuf *m,
 214     struct pf_mtag *tag)
 215 {
 216         int droptype;
 217
 218         /*
 219          * if we were idle, this is an enqueue onto an empty queue
 220          * and we should decrement marking probability
 221          */
 222         if (bp->blue_idle) {
 223                 struct timeval now;
 224                 u_int32_t t;
 225
 226                 bp->blue_idle = 0;
 227                 microuptime(&now);
 228                 t = (now.tv_sec - bp->blue_last.tv_sec);
 229                 if (t > 1) {
 230                         bp->blue_pmark = 1;
 231                         microuptime(&bp->blue_last);
 232                 } else {
 233                         t = t * 1000000 + (now.tv_usec - bp->blue_last.tv_usec);
 234                         if (t > bp->blue_hold_time) {
 235                                 bp->blue_pmark--;
 236                                 if (bp->blue_pmark < 0)
 237                                         bp->blue_pmark = 0;
 238                                 microuptime(&bp->blue_last);
 239                         }
 240                 }
 241         }
 242
 243         /* see if we drop early */
 244         droptype = DTYPE_NODROP;
 245         if (blue_drop_early(bp) && qlen(q) > 1) {
 246                 /* mark or drop by blue */
 247                 if ((bp->blue_flags & BLUEF_ECN) &&
 248                     (tag->pftag_flags & PF_TAG_TCP) &&  /* only for TCP */
 249                     mark_ecn(m, tag, bp->blue_flags)) {
 250                         /* successfully marked.  do not drop. */
 251                         bp->blue_stats.marked_packets++;
 252                 } else {
 253                         /* unforced drop by blue */
 254                         droptype = DTYPE_EARLY;
 255                 }
 256         }
 257
 258         /* if the queue length hits the hard limit, it's a forced drop */
 259         if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
 260                 droptype = DTYPE_FORCED;
 261
 262         /* if successful or forced drop, enqueue this packet. */
 263         if (droptype != DTYPE_EARLY)
 264                 _addq(q, m);
 265
 266         if (droptype != DTYPE_NODROP) {
 267                 if (droptype == DTYPE_EARLY) {
 268                         /* drop the incoming packet */
 269                         bp->blue_stats.drop_unforced++;
 270                 } else {
 271                         struct timeval now;
 272                         u_int32_t t;
 273                         /* forced drop, select a victim packet in the queue. */
 274                         m = _getq_random(q);
 275                         microuptime(&now);
 276                         t = (now.tv_sec - bp->blue_last.tv_sec);
 277                         t = t * 1000000 + (now.tv_usec - bp->blue_last.tv_usec);
 278                         if (t > bp->blue_hold_time) {
 279                                 bp->blue_pmark += bp->blue_max_pmark >> 3;
 280                                 if (bp->blue_pmark > bp->blue_max_pmark)
 281                                         bp->blue_pmark = bp->blue_max_pmark;
 282                                 microuptime(&bp->blue_last);
 283                         }
 284                         bp->blue_stats.drop_forced++;
 285                 }
 286                 IFCQ_CONVERT_LOCK(&bp->blue_ifp->if_snd);
 287                 m_freem(m);
 288                 return (CLASSQEQ_DROPPED);
 289         }
 290         /* successfully queued */
 291         return (CLASSQEQ_SUCCESS);
 292 }
 293
 294 static struct mbuf *
 295 blue_getq_flow(struct blue *bp, class_queue_t *q, u_int32_t flow,
 296     boolean_t purge)
 297 {
 298 #pragma unused(purge)
 299         struct mbuf *m;
 300
 301         /* flow of 0 means head of queue */
 302         if ((m = ((flow == 0) ? _getq(q) : _getq_flow(q, flow))) == NULL) {
 303                 if (bp->blue_idle == 0) {
 304                         bp->blue_idle = 1;
 305                         microuptime(&bp->blue_last);
 306                 }
 307                 return (NULL);
 308         }
 309
 310         bp->blue_idle = 0;
 311         return (m);
 312 }
 313
 314 struct mbuf *
 315 blue_getq(struct blue *bp, class_queue_t *q)
 316 {
 317         return (blue_getq_flow(bp, q, 0, FALSE));
 318 }
 319
 320 void
 321 blue_purgeq(struct blue *bp, class_queue_t *q, u_int32_t flow,
 322     u_int32_t *packets, u_int32_t *bytes)
 323 {
 324         u_int32_t cnt = 0, len = 0;
 325         struct mbuf *m;
 326
 327         IFCQ_CONVERT_LOCK(&bp->blue_ifp->if_snd);
 328
 329         while ((m = blue_getq_flow(bp, q, flow, TRUE)) != NULL) {
 330                 cnt++;
 331                 len += m_pktlen(m);
 332                 m_freem(m);
 333         }
 334
 335         if (packets != NULL)
 336                 *packets = cnt;
 337         if (bytes != NULL)
 338                 *bytes = len;
 339 }
 340
 341 /*
 342  * early-drop probability is kept in blue_pmark
 343  */
 344 static int
 345 blue_drop_early(struct blue *bp)
 346 {
 347         if ((random() % (unsigned)bp->blue_max_pmark) <
 348             (unsigned)bp->blue_pmark) {
 349                 /* drop or mark */
 350                 return (1);
 351         }
 352         /* no drop/mark */
 353         return (0);
 354 }
 355
 356 void
 357 blue_updateq(struct blue *bp, cqev_t ev)
 358 {
 359 #pragma unused(bp, ev)
 360         /* nothing for now */
 361 }
 362
 363 int
 364 blue_suspendq(struct blue *bp, class_queue_t *q, boolean_t on)
 365 {
 366 #pragma unused(bp, q, on)
 367         return (ENOTSUP);
 368 }
 369 #endif /* CLASSQ_BLUE */