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
77u_int32_t classq_verbose = 0; /* more noise if greater than 1 */
78
79SYSCTL_NODE(_net, OID_AUTO, classq, CTLFLAG_RW|CTLFLAG_LOCKED, 0, "classq");
80
81SYSCTL_UINT(_net_classq, OID_AUTO, verbose, CTLFLAG_RW|CTLFLAG_LOCKED,
82 &classq_verbose, 0, "Class queue verbosity level");
83
84void
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 */
107void
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 */
132void
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 */
155void *
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
196static 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 */
246void *
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 */
253void *
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 */
260void *
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
291static 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 */
331void *
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
349static 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 */
406void *
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
424static 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 */
462void
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
476void
477_flushq(class_queue_t *q)
478{
479 (void) _flushq_flow(q, 0, NULL, NULL);
480}
481
482static 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
528void
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}
541