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