bsd/net/classq/classq.c

   1 /*
   2  * Copyright (c) 2007-2017 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
  77 u_int32_t classq_verbose = 0;   /* more noise if greater than 1 */
  78
  79 SYSCTL_NODE(_net, OID_AUTO, classq, CTLFLAG_RW|CTLFLAG_LOCKED, 0, "classq");
  80
  81 SYSCTL_UINT(_net_classq, OID_AUTO, verbose, CTLFLAG_RW|CTLFLAG_LOCKED,
  82         &classq_verbose, 0, "Class queue verbosity level");
  83
  84 void
  85 _qinit(class_queue_t *q, int type, int lim, classq_pkt_type_t ptype)
  86 {
  87         switch (ptype) {
  88         case QP_MBUF:
  89                 MBUFQ_INIT(&qmbufq(q));
  90                 break;
  91
  92
  93         default:
  94                 VERIFY(0);
  95                 /* NOTREACHED */
  96         }
  97
  98         qlimit(q) = lim;
  99         qlen(q) = 0;
 100         qsize(q) = 0;
 101         qtype(q) = type;
 102         qptype(q) = ptype;
 103         qstate(q) = QS_RUNNING;
 104 }
 105
 106 /* add a packet at the tail of the queue */
 107 void
 108 _addq(class_queue_t *q, void *pkt)
 109 {
 110         uint32_t size = 0;
 111
 112         switch (qptype(q)) {
 113         case QP_MBUF: {
 114                 struct mbuf *m = pkt;
 115                 MBUFQ_ENQUEUE(&qmbufq(q), m);
 116                 size = m_length(m);
 117                 break;
 118         }
 119
 120
 121         default:
 122                 VERIFY(0);
 123                 /* NOTREACHED */
 124         }
 125
 126         qlen(q)++;
 127         VERIFY(qlen(q) != 0);
 128         qsize(q) += size;
 129 }
 130
 131 /* add one or more packets at the tail of the queue */
 132 void
 133 _addq_multi(class_queue_t *q, void *pkt_head, void *pkt_tail,
 134     u_int32_t cnt, u_int32_t size)
 135 {
 136         switch (qptype(q)) {
 137         case QP_MBUF: {
 138                 struct mbuf *m_head = pkt_head;
 139                 struct mbuf *m_tail = pkt_tail;
 140                 MBUFQ_ENQUEUE_MULTI(&qmbufq(q), m_head, m_tail);
 141                 break;
 142         }
 143
 144
 145         default:
 146                 VERIFY(0);
 147                 /* NOTREACHED */
 148         }
 149
 150         qlen(q) += cnt;
 151         qsize(q) += size;
 152 }
 153
 154 /* get a packet at the head of the queue */
 155 void *
 156 _getq(class_queue_t *q)
 157 {
 158         void *pkt = NULL;
 159         uint32_t pkt_len;
 160
 161         switch (qptype(q)) {
 162         case QP_MBUF: {
 163                 struct mbuf *m;
 164                 MBUFQ_DEQUEUE(&qmbufq(q), m);
 165                 if (m != NULL) {
 166                         pkt_len = m_length(m);
 167                         pkt = m;
 168                 }
 169                 break;
 170         }
 171
 172
 173         default:
 174                 VERIFY(0);
 175                 /* NOTREACHED */
 176         }
 177
 178         if (pkt == NULL) {
 179                 VERIFY(qlen(q) == 0);
 180                 if (qsize(q) > 0)
 181                         qsize(q) = 0;
 182                 return (NULL);
 183         }
 184         VERIFY(qlen(q) > 0);
 185         qlen(q)--;
 186
 187         /* qsize is an approximation, so adjust if necessary */
 188         if (((int)qsize(q) - pkt_len) > 0)
 189                 qsize(q) -= pkt_len;
 190         else if (qsize(q) != 0)
 191                 qsize(q) = 0;
 192
 193         return (pkt);
 194 }
 195
 196 static void *
 197 _getq_flow_or_scidx(class_queue_t *q, u_int32_t val, boolean_t isflowid)
 198 {
 199         void *pkt = NULL;
 200         uint32_t pkt_len;
 201
 202         switch (qptype(q)) {
 203         case QP_MBUF: {
 204                 struct mbuf *m, *m_tmp;
 205
 206                 MBUFQ_FOREACH_SAFE(m, &qmbufq(q), m_tmp) {
 207                         if ((isflowid && (val == 0 ||
 208                             ((m->m_flags & M_PKTHDR) &&
 209                             m->m_pkthdr.pkt_flowid == val))) ||
 210                             (!isflowid &&
 211                             MBUF_SCIDX(mbuf_get_service_class(m)) < val)) {
 212                                 /* remove it from the class queue */
 213                                 MBUFQ_REMOVE(&qmbufq(q), m);
 214                                 MBUFQ_NEXT(m) = NULL;
 215                                 break;
 216                         }
 217                 }
 218                 if (m != NULL) {
 219                         pkt = m;
 220                         pkt_len = m_length(m);
 221                 }
 222                 break;
 223         }
 224
 225
 226         default:
 227                 VERIFY(0);
 228                 /* NOTREACHED */
 229         }
 230
 231         if (pkt != NULL) {
 232                 VERIFY(qlen(q) > 0);
 233                 qlen(q)--;
 234
 235                 /* qsize is an approximation, so adjust if necessary */
 236                 if (((int)qsize(q) - pkt_len) > 0)
 237                         qsize(q) -= pkt_len;
 238                 else if (qsize(q) != 0)
 239                         qsize(q) = 0;
 240         }
 241
 242         return (pkt);
 243 }
 244
 245 /* get a packet of a specific flow beginning from the head of the queue */
 246 void *
 247 _getq_flow(class_queue_t *q, u_int32_t flow)
 248 {
 249         return (_getq_flow_or_scidx(q, flow, TRUE));
 250 }
 251
 252 /* Get a packet whose MBUF_SCIDX() < scidx from head of queue */
 253 void *
 254 _getq_scidx_lt(class_queue_t *q, u_int32_t scidx)
 255 {
 256         return (_getq_flow_or_scidx(q, scidx, FALSE));
 257 }
 258
 259 /* get all packets (chained) starting from the head of the queue */
 260 void *
 261 _getq_all(class_queue_t *q, void **last, u_int32_t *qlenp,
 262     u_int64_t *qsizep)
 263 {
 264         void *pkt = NULL;
 265
 266         switch (qptype(q)) {
 267         case QP_MBUF:
 268                 pkt = MBUFQ_FIRST(&qmbufq(q));
 269                 if (last != NULL)
 270                         *last = MBUFQ_LAST(&qmbufq(q));
 271                 MBUFQ_INIT(&qmbufq(q));
 272                 break;
 273
 274
 275         default:
 276                 VERIFY(0);
 277                 /* NOTREACHED */
 278         }
 279
 280         if (qlenp != NULL)
 281                 *qlenp = qlen(q);
 282         if (qsizep != NULL)
 283                 *qsizep = qsize(q);
 284
 285         qlen(q) = 0;
 286         qsize(q) = 0;
 287
 288         return (pkt);
 289 }
 290
 291 static inline struct mbuf *
 292 _getq_tail_mbuf(class_queue_t *q)
 293 {
 294         struct mq_head *head = &qmbufq(q);
 295         struct mbuf *m = MBUFQ_LAST(head);
 296
 297         if (m != NULL) {
 298                 struct mbuf *n = MBUFQ_FIRST(head);
 299
 300                 while (n != NULL) {
 301                         struct mbuf *next = MBUFQ_NEXT(n);
 302                         if (next == m) {
 303                                 MBUFQ_NEXT(n) = NULL;
 304                                 break;
 305                         }
 306                         n = next;
 307                 }
 308                 VERIFY(n != NULL ||
 309                     (qlen(q) == 1 && m == MBUFQ_FIRST(head)));
 310                 VERIFY(qlen(q) > 0);
 311                 --qlen(q);
 312
 313                 /* qsize is an approximation, so adjust if necessary */
 314                 if (((int)qsize(q) - m_length(m)) > 0)
 315                         qsize(q) -= m_length(m);
 316                 else if (qsize(q) != 0)
 317                         qsize(q) = 0;
 318
 319                 if (qempty(q)) {
 320                         VERIFY(m == MBUFQ_FIRST(head));
 321                         MBUFQ_INIT(head);
 322                 } else {
 323                         VERIFY(n != NULL);
 324                         head->mq_last = &MBUFQ_NEXT(n);
 325                 }
 326         }
 327         return (m);
 328 }
 329
 330 /* drop a packet at the tail of the queue */
 331 void *
 332 _getq_tail(class_queue_t *q)
 333 {
 334         void *t = NULL;
 335
 336         switch (qptype(q)) {
 337         case QP_MBUF:
 338                 t = _getq_tail_mbuf(q);
 339                 break;
 340
 341         default:
 342                 VERIFY(0);
 343                 /* NOTREACHED */
 344         }
 345
 346         return (t);
 347 }
 348
 349 static inline struct mbuf *
 350 _getq_random_mbuf(class_queue_t *q)
 351 {
 352         struct mq_head *head = &qmbufq(q);
 353         struct mbuf *m = NULL;
 354         unsigned int n;
 355         u_int32_t rnd;
 356
 357         /* XXX: Add support for Kernel packet when needed */
 358         VERIFY((qptype(q) == QP_MBUF));
 359
 360         n = qlen(q);
 361         if (n == 0) {
 362                 VERIFY(MBUFQ_EMPTY(head));
 363                 if (qsize(q) > 0)
 364                         qsize(q) = 0;
 365                 return (NULL);
 366         }
 367
 368         m = MBUFQ_FIRST(head);
 369         read_frandom(&rnd, sizeof (rnd));
 370         n = (rnd % n) + 1;
 371
 372         if (n == 1) {
 373                 if ((MBUFQ_FIRST(head) = MBUFQ_NEXT(m)) == NULL)
 374                         (head)->mq_last = &MBUFQ_FIRST(head);
 375         } else {
 376                 struct mbuf *p = NULL;
 377
 378                 VERIFY(n > 1);
 379                 while (n--) {
 380                         if (MBUFQ_NEXT(m) == NULL)
 381                                 break;
 382                         p = m;
 383                         m = MBUFQ_NEXT(m);
 384                 }
 385                 VERIFY(p != NULL && MBUFQ_NEXT(p) == m);
 386
 387                 if ((MBUFQ_NEXT(p) = MBUFQ_NEXT(m)) == NULL)
 388                         (head)->mq_last = &MBUFQ_NEXT(p);
 389         }
 390
 391         VERIFY(qlen(q) > 0);
 392         --qlen(q);
 393
 394         /* qsize is an approximation, so adjust if necessary */
 395         if (((int)qsize(q) - m_length(m)) > 0)
 396                 qsize(q) -= m_length(m);
 397         else if (qsize(q) != 0)
 398                 qsize(q) = 0;
 399
 400         MBUFQ_NEXT(m) = NULL;
 401
 402         return (m);
 403 }
 404
 405 /* randomly select a packet in the queue */
 406 void *
 407 _getq_random(class_queue_t *q)
 408 {
 409         void *r = NULL;
 410
 411         switch (qptype(q)) {
 412         case QP_MBUF:
 413                 r = _getq_random_mbuf(q);
 414                 break;
 415
 416         default:
 417                 VERIFY(0);
 418                 /* NOTREACHED */
 419         }
 420
 421         return (r);
 422 }
 423
 424 static inline void
 425 _removeq_mbuf(class_queue_t *q, struct mbuf *m)
 426 {
 427         struct mq_head *head = &qmbufq(q);
 428         struct mbuf *m0, **mtail;
 429
 430         m0 = MBUFQ_FIRST(head);
 431         if (m0 == NULL)
 432                 return;
 433
 434         if (m0 != m) {
 435                 while (MBUFQ_NEXT(m0) != m) {
 436                         if (m0 == NULL)
 437                                 return;
 438                         m0 = MBUFQ_NEXT(m0);
 439                 }
 440                 mtail = &MBUFQ_NEXT(m0);
 441         } else {
 442                 mtail = &MBUFQ_FIRST(head);
 443         }
 444
 445         *mtail = MBUFQ_NEXT(m);
 446         if (*mtail == NULL)
 447                 head->mq_last = mtail;
 448
 449         VERIFY(qlen(q) > 0);
 450         --qlen(q);
 451
 452         /* qsize is an approximation, so adjust if necessary */
 453         if (((int)qsize(q) - m_length(m)) > 0)
 454                 qsize(q) -= m_length(m);
 455         else if (qsize(q) != 0)
 456                 qsize(q) = 0;
 457
 458         MBUFQ_NEXT(m) = NULL;
 459 }
 460
 461 /* remove a packet from the queue */
 462 void
 463 _removeq(class_queue_t *q, void *pkt)
 464 {
 465         switch (qptype(q)) {
 466         case QP_MBUF:
 467                 _removeq_mbuf(q, pkt);
 468                 break;
 469
 470         default:
 471                 VERIFY(0);
 472                 /* NOTREACHED */
 473         }
 474 }
 475
 476 void
 477 _flushq(class_queue_t *q)
 478 {
 479         (void) _flushq_flow(q, 0, NULL, NULL);
 480 }
 481
 482 static inline void
 483 _flushq_flow_mbuf(class_queue_t *q, u_int32_t flow, u_int32_t *cnt,
 484     u_int32_t *len)
 485 {
 486         MBUFQ_HEAD(mq_freeq) freeq;
 487         struct mbuf *m, *m_tmp;
 488         u_int32_t c = 0, l = 0;
 489
 490         MBUFQ_INIT(&freeq);
 491
 492         MBUFQ_FOREACH_SAFE(m, &qmbufq(q), m_tmp) {
 493                 if (flow == 0 || ((m->m_flags & M_PKTHDR) &&
 494                     m->m_pkthdr.pkt_flowid == flow)) {
 495                         /* remove it from the class queue */
 496                         MBUFQ_REMOVE(&qmbufq(q), m);
 497                         MBUFQ_NEXT(m) = NULL;
 498
 499                         /* and add it to the free queue */
 500                         MBUFQ_ENQUEUE(&freeq, m);
 501
 502                         l += m_length(m);
 503                         c++;
 504                 }
 505         }
 506         VERIFY(c == 0 || !MBUFQ_EMPTY(&freeq));
 507
 508         if (c > 0) {
 509                 VERIFY(qlen(q) >= c);
 510                 qlen(q) -= c;
 511
 512                 /* qsize is an approximation, so adjust if necessary */
 513                 if (((int)qsize(q) - l) > 0)
 514                         qsize(q) -= l;
 515                 else if (qsize(q) != 0)
 516                         qsize(q) = 0;
 517         }
 518
 519         if (!MBUFQ_EMPTY(&freeq))
 520                 m_freem_list(MBUFQ_FIRST(&freeq));
 521
 522         if (cnt != NULL)
 523                 *cnt = c;
 524         if (len != NULL)
 525                 *len = l;
 526 }
 527
 528 void
 529 _flushq_flow(class_queue_t *q, u_int32_t flow, u_int32_t *cnt, u_int32_t *len)
 530 {
 531         switch (qptype(q)) {
 532         case QP_MBUF:
 533                 _flushq_flow_mbuf(q, flow, cnt, len);
 534                 break;
 535
 536         default:
 537                 VERIFY(0);
 538                 /* NOTREACHED */
 539         }
 540 }