bsd/net/classq/classq.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 /*
  30  * Copyright (c) 1991-1997 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 Network Research
  44  *      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 <sys/cdefs.h>
  63 #include <sys/param.h>
  64 #include <sys/mbuf.h>
  65 #include <sys/errno.h>
  66 #include <sys/random.h>
  67 #include <sys/kernel_types.h>
  68 #include <sys/sysctl.h>
  69
  70 #include <net/if.h>
  71 #include <net/net_osdep.h>
  72 #include <net/classq/classq.h>
  73
  74 #include <libkern/libkern.h>
  75
  76 u_int32_t classq_verbose;       /* more noise if greater than 1 */
  77
  78 SYSCTL_NODE(_net, OID_AUTO, classq, CTLFLAG_RW|CTLFLAG_LOCKED, 0, "classq");
  79
  80 SYSCTL_UINT(_net_classq, OID_AUTO, verbose, CTLFLAG_RW|CTLFLAG_LOCKED,
  81         &classq_verbose, 0, "Class queue verbosity level");
  82
  83 void
  84 _qinit(class_queue_t *q, int type, int lim)
  85 {
  86         MBUFQ_INIT(&q->mbufq);
  87         qlimit(q) = lim;
  88         qlen(q) = 0;
  89         qsize(q) = 0;
  90         qtype(q) = type;
  91         qstate(q) = QS_RUNNING;
  92 }
  93
  94 /* add a packet at the tail of the queue */
  95 void
  96 _addq(class_queue_t *q, struct mbuf *m)
  97 {
  98         MBUFQ_ENQUEUE(&q->mbufq, m);
  99         qlen(q)++;
 100         VERIFY(qlen(q) != 0);
 101         qsize(q) += m_length(m);
 102 }
 103
 104 /* add one or more packets at the tail of the queue */
 105 void
 106 _addq_multi(class_queue_t *q, struct mbuf *m_head, struct mbuf *m_tail,
 107     u_int32_t cnt, u_int32_t size)
 108 {
 109         MBUFQ_ENQUEUE_MULTI(&q->mbufq, m_head, m_tail);
 110         qlen(q) += cnt;
 111         qsize(q) += size;
 112 }
 113
 114 /* get a packet at the head of the queue */
 115 struct mbuf *
 116 _getq(class_queue_t *q)
 117 {
 118         struct mbuf *m;
 119
 120         MBUFQ_DEQUEUE(&q->mbufq, m);
 121         if (m == NULL) {
 122                 VERIFY(qlen(q) == 0);
 123                 if (qsize(q) > 0)
 124                         qsize(q) = 0;
 125                 return (NULL);
 126         }
 127         VERIFY(qlen(q) > 0);
 128         qlen(q)--;
 129
 130         /* qsize is an approximation, so adjust if necessary */
 131         if (((int)qsize(q) - m_length(m)) > 0)
 132                 qsize(q) -= m_length(m);
 133         else if (qsize(q) != 0)
 134                 qsize(q) = 0;
 135
 136         return (m);
 137 }
 138
 139 /* get a packet of a specific flow beginning from the head of the queue */
 140 struct mbuf *
 141 _getq_flow(class_queue_t *q, u_int32_t flow)
 142 {
 143         struct mbuf *m, *m_tmp;
 144
 145         MBUFQ_FOREACH_SAFE(m, &q->mbufq, m_tmp) {
 146                 if (flow == 0 || ((m->m_flags & M_PKTHDR) &&
 147                     m->m_pkthdr.m_flowhash == flow)) {
 148                         /* remove it from the class queue */
 149                         MBUFQ_REMOVE(&q->mbufq, m);
 150                         MBUFQ_NEXT(m) = NULL;
 151                         break;
 152                 }
 153         }
 154
 155         if (m != NULL) {
 156                 u_int32_t l = m_length(m);
 157
 158                 VERIFY(qlen(q) > 0);
 159                 qlen(q)--;
 160
 161                 /* qsize is an approximation, so adjust if necessary */
 162                 if (((int)qsize(q) - l) > 0)
 163                         qsize(q) -= l;
 164                 else if (qsize(q) != 0)
 165                         qsize(q) = 0;
 166         }
 167
 168         return (m);
 169 }
 170
 171 /* get all packets starting from the head of the queue */
 172 struct mbuf *
 173 _getq_all(class_queue_t *q)
 174 {
 175         struct mbuf *m;
 176
 177         m = MBUFQ_FIRST(&q->mbufq);
 178         MBUFQ_INIT(&q->mbufq);
 179         qlen(q) = 0;
 180         qsize(q) = 0;
 181
 182         return (m);
 183 }
 184
 185 /* drop a packet at the tail of the queue */
 186 struct mbuf *
 187 _getq_tail(class_queue_t *q)
 188 {
 189         struct mq_head *head = &q->mbufq;
 190         struct mbuf *m = MBUFQ_LAST(head);
 191
 192         if (m != NULL) {
 193                 struct mbuf *n = MBUFQ_FIRST(head);
 194
 195                 while (n != NULL) {
 196                         struct mbuf *next = MBUFQ_NEXT(n);
 197                         if (next == m) {
 198                                 MBUFQ_NEXT(n) = NULL;
 199                                 break;
 200                         }
 201                         n = next;
 202                 }
 203                 VERIFY(n != NULL ||
 204                     (qlen(q) == 1 && m == MBUFQ_FIRST(head)));
 205                 VERIFY(qlen(q) > 0);
 206                 --qlen(q);
 207
 208                 /* qsize is an approximation, so adjust if necessary */
 209                 if (((int)qsize(q) - m_length(m)) > 0)
 210                         qsize(q) -= m_length(m);
 211                 else if (qsize(q) != 0)
 212                         qsize(q) = 0;
 213
 214                 if (qempty(q)) {
 215                         VERIFY(MBUFQ_EMPTY(head));
 216                         MBUFQ_INIT(head);
 217                 } else {
 218                         VERIFY(n != NULL);
 219                         head->mq_last = &MBUFQ_NEXT(n);
 220                 }
 221         }
 222         return (m);
 223 }
 224
 225 /* randomly select a packet in the queue */
 226 struct mbuf *
 227 _getq_random(class_queue_t *q)
 228 {
 229         struct mq_head *head = &q->mbufq;
 230         struct mbuf *m = NULL;
 231         unsigned int n;
 232         u_int32_t rnd;
 233
 234         n = qlen(q);
 235         if (n == 0) {
 236                 VERIFY(MBUFQ_EMPTY(head));
 237                 if (qsize(q) > 0)
 238                         qsize(q) = 0;
 239                 return (NULL);
 240         }
 241
 242         m = MBUFQ_FIRST(head);
 243         read_random(&rnd, sizeof (rnd));
 244         n = (rnd % n) + 1;
 245
 246         if (n == 1) {
 247                 if ((MBUFQ_FIRST(head) = MBUFQ_NEXT(m)) == NULL)
 248                         (head)->mq_last = &MBUFQ_FIRST(head);
 249         } else {
 250                 struct mbuf *p = NULL;
 251
 252                 VERIFY(n > 1);
 253                 while (n--) {
 254                         if (MBUFQ_NEXT(m) == NULL)
 255                                 break;
 256                         p = m;
 257                         m = MBUFQ_NEXT(m);
 258                 }
 259                 VERIFY(p != NULL && MBUFQ_NEXT(p) == m);
 260
 261                 if ((MBUFQ_NEXT(p) = MBUFQ_NEXT(m)) == NULL)
 262                         (head)->mq_last = &MBUFQ_NEXT(p);
 263         }
 264
 265         VERIFY(qlen(q) > 0);
 266         --qlen(q);
 267
 268         /* qsize is an approximation, so adjust if necessary */
 269         if (((int)qsize(q) - m_length(m)) > 0)
 270                 qsize(q) -= m_length(m);
 271         else if (qsize(q) != 0)
 272                 qsize(q) = 0;
 273
 274         MBUFQ_NEXT(m) = NULL;
 275
 276         return (m);
 277 }
 278
 279 /* remove a packet from the queue */
 280 void
 281 _removeq(class_queue_t *q, struct mbuf *m)
 282 {
 283         struct mq_head *head = &q->mbufq;
 284         struct mbuf *m0, **mtail;
 285
 286         m0 = MBUFQ_FIRST(head);
 287         if (m0 == NULL)
 288                 return;
 289
 290         if (m0 != m) {
 291                 while (MBUFQ_NEXT(m0) != m) {
 292                         if (m0 == NULL)
 293                                 return;
 294                         m0 = MBUFQ_NEXT(m0);
 295                 }
 296                 mtail = &MBUFQ_NEXT(m0);
 297         } else {
 298                 mtail = &MBUFQ_FIRST(head);
 299         }
 300
 301         *mtail = MBUFQ_NEXT(m);
 302         if (*mtail == NULL)
 303                 head->mq_last = mtail;
 304
 305         VERIFY(qlen(q) > 0);
 306         --qlen(q);
 307
 308         /* qsize is an approximation, so adjust if necessary */
 309         if (((int)qsize(q) - m_length(m)) > 0)
 310                 qsize(q) -= m_length(m);
 311         else if (qsize(q) != 0)
 312                 qsize(q) = 0;
 313
 314         MBUFQ_NEXT(m) = NULL;
 315 }
 316
 317 void
 318 _flushq(class_queue_t *q)
 319 {
 320         (void) _flushq_flow(q, 0, NULL, NULL);
 321 }
 322
 323 void
 324 _flushq_flow(class_queue_t *q, u_int32_t flow, u_int32_t *cnt, u_int32_t *len)
 325 {
 326         MBUFQ_HEAD(mq_freeq) freeq;
 327         struct mbuf *m, *m_tmp;
 328         u_int32_t c = 0, l = 0;
 329
 330         MBUFQ_INIT(&freeq);
 331
 332         MBUFQ_FOREACH_SAFE(m, &q->mbufq, m_tmp) {
 333                 if (flow == 0 || ((m->m_flags & M_PKTHDR) &&
 334                     m->m_pkthdr.m_flowhash == flow)) {
 335                         /* remove it from the class queue */
 336                         MBUFQ_REMOVE(&q->mbufq, m);
 337                         MBUFQ_NEXT(m) = NULL;
 338
 339                         /* and add it to the free queue */
 340                         MBUFQ_ENQUEUE(&freeq, m);
 341
 342                         l += m_length(m);
 343                         c++;
 344                 }
 345         }
 346         VERIFY(c == 0 || !MBUFQ_EMPTY(&freeq));
 347
 348         if (c > 0) {
 349                 VERIFY(qlen(q) >= c);
 350                 qlen(q) -= c;
 351
 352                 /* qsize is an approximation, so adjust if necessary */
 353                 if (((int)qsize(q) - l) > 0)
 354                         qsize(q) -= l;
 355                 else if (qsize(q) != 0)
 356                         qsize(q) = 0;
 357         }
 358
 359         if (!MBUFQ_EMPTY(&freeq))
 360                 m_freem_list(MBUFQ_FIRST(&freeq));
 361
 362         if (cnt != NULL)
 363                 *cnt = c;
 364         if (len != NULL)
 365                 *len = l;
 366 }