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 76u_int32_t classq_verbose; /* more noise if greater than 1 */ 77 78SYSCTL_NODE(_net, OID_AUTO, classq, CTLFLAG_RW|CTLFLAG_LOCKED, 0, "classq"); 79 80SYSCTL_UINT(_net_classq, OID_AUTO, verbose, CTLFLAG_RW|CTLFLAG_LOCKED, 81 &classq_verbose, 0, "Class queue verbosity level"); 82 83void 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 */ 95void 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 */ 105void 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 */ 115struct 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 */ 140struct 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.pkt_flowid == 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 */ 172struct 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 */ 186struct 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 */ 226struct 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 */ 280void 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 317void 318_flushq(class_queue_t *q) 319{ 320 (void) _flushq_flow(q, 0, NULL, NULL); 321} 322 323void 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.pkt_flowid == 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} 367