1da8ae05dSGleb Smirnoff /*-
2772e66a6SGleb Smirnoff * Copyright (c) 1991-1997 Regents of the University of California.
3772e66a6SGleb Smirnoff * All rights reserved.
4772e66a6SGleb Smirnoff *
5772e66a6SGleb Smirnoff * Redistribution and use in source and binary forms, with or without
6772e66a6SGleb Smirnoff * modification, are permitted provided that the following conditions
7772e66a6SGleb Smirnoff * are met:
8772e66a6SGleb Smirnoff * 1. Redistributions of source code must retain the above copyright
9772e66a6SGleb Smirnoff * notice, this list of conditions and the following disclaimer.
10772e66a6SGleb Smirnoff * 2. Redistributions in binary form must reproduce the above copyright
11772e66a6SGleb Smirnoff * notice, this list of conditions and the following disclaimer in the
12772e66a6SGleb Smirnoff * documentation and/or other materials provided with the distribution.
13772e66a6SGleb Smirnoff * 3. All advertising materials mentioning features or use of this software
14772e66a6SGleb Smirnoff * must display the following acknowledgement:
15772e66a6SGleb Smirnoff * This product includes software developed by the Network Research
16772e66a6SGleb Smirnoff * Group at Lawrence Berkeley Laboratory.
17772e66a6SGleb Smirnoff * 4. Neither the name of the University nor of the Laboratory may be used
18772e66a6SGleb Smirnoff * to endorse or promote products derived from this software without
19772e66a6SGleb Smirnoff * specific prior written permission.
20772e66a6SGleb Smirnoff *
21772e66a6SGleb Smirnoff * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22772e66a6SGleb Smirnoff * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23772e66a6SGleb Smirnoff * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24772e66a6SGleb Smirnoff * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25772e66a6SGleb Smirnoff * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26772e66a6SGleb Smirnoff * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27772e66a6SGleb Smirnoff * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28772e66a6SGleb Smirnoff * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29772e66a6SGleb Smirnoff * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30772e66a6SGleb Smirnoff * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31772e66a6SGleb Smirnoff * SUCH DAMAGE.
32da8ae05dSGleb Smirnoff *
33da8ae05dSGleb Smirnoff * $KAME: altq_classq.h,v 1.6 2003/01/07 07:33:38 kjc Exp $
34772e66a6SGleb Smirnoff */
35772e66a6SGleb Smirnoff /*
36772e66a6SGleb Smirnoff * class queue definitions extracted from rm_class.h.
37772e66a6SGleb Smirnoff */
38772e66a6SGleb Smirnoff #ifndef _ALTQ_ALTQ_CLASSQ_H_
39772e66a6SGleb Smirnoff #define _ALTQ_ALTQ_CLASSQ_H_
40772e66a6SGleb Smirnoff
41772e66a6SGleb Smirnoff #ifdef __cplusplus
42772e66a6SGleb Smirnoff extern "C" {
43772e66a6SGleb Smirnoff #endif
44772e66a6SGleb Smirnoff
45772e66a6SGleb Smirnoff /*
46772e66a6SGleb Smirnoff * Packet Queue types: RED or DROPHEAD.
47772e66a6SGleb Smirnoff */
48772e66a6SGleb Smirnoff #define Q_DROPHEAD 0x00
49772e66a6SGleb Smirnoff #define Q_RED 0x01
50772e66a6SGleb Smirnoff #define Q_RIO 0x02
51772e66a6SGleb Smirnoff #define Q_DROPTAIL 0x03
520a70aaf8SLuiz Otavio O Souza #define Q_CODEL 0x04
53772e66a6SGleb Smirnoff
54772e66a6SGleb Smirnoff #ifdef _KERNEL
55772e66a6SGleb Smirnoff
56772e66a6SGleb Smirnoff /*
57772e66a6SGleb Smirnoff * Packet Queue structures and macros to manipulate them.
58772e66a6SGleb Smirnoff */
59772e66a6SGleb Smirnoff struct _class_queue_ {
60772e66a6SGleb Smirnoff struct mbuf *tail_; /* Tail of packet queue */
61772e66a6SGleb Smirnoff int qlen_; /* Queue length (in number of packets) */
62772e66a6SGleb Smirnoff int qlim_; /* Queue limit (in number of packets*) */
630a70aaf8SLuiz Otavio O Souza int qsize_; /* Queue size (in number of bytes*) */
64772e66a6SGleb Smirnoff int qtype_; /* Queue type */
65772e66a6SGleb Smirnoff };
66772e66a6SGleb Smirnoff
67772e66a6SGleb Smirnoff typedef struct _class_queue_ class_queue_t;
68772e66a6SGleb Smirnoff
69772e66a6SGleb Smirnoff #define qtype(q) (q)->qtype_ /* Get queue type */
70772e66a6SGleb Smirnoff #define qlimit(q) (q)->qlim_ /* Max packets to be queued */
71772e66a6SGleb Smirnoff #define qlen(q) (q)->qlen_ /* Current queue length. */
720a70aaf8SLuiz Otavio O Souza #define qsize(q) (q)->qsize_ /* Current queue size. */
73772e66a6SGleb Smirnoff #define qtail(q) (q)->tail_ /* Tail of the queue */
74772e66a6SGleb Smirnoff #define qhead(q) ((q)->tail_ ? (q)->tail_->m_nextpkt : NULL)
75772e66a6SGleb Smirnoff
76772e66a6SGleb Smirnoff #define qempty(q) ((q)->qlen_ == 0) /* Is the queue empty?? */
770a70aaf8SLuiz Otavio O Souza #define q_is_codel(q) ((q)->qtype_ == Q_CODEL) /* Is the queue a codel queue */
78772e66a6SGleb Smirnoff #define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a red queue */
79772e66a6SGleb Smirnoff #define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a rio queue */
80772e66a6SGleb Smirnoff #define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO)
81772e66a6SGleb Smirnoff
82772e66a6SGleb Smirnoff #if !defined(__GNUC__) || defined(ALTQ_DEBUG)
83772e66a6SGleb Smirnoff
84772e66a6SGleb Smirnoff extern void _addq(class_queue_t *, struct mbuf *);
85772e66a6SGleb Smirnoff extern struct mbuf *_getq(class_queue_t *);
86772e66a6SGleb Smirnoff extern struct mbuf *_getq_tail(class_queue_t *);
87772e66a6SGleb Smirnoff extern struct mbuf *_getq_random(class_queue_t *);
88772e66a6SGleb Smirnoff extern void _removeq(class_queue_t *, struct mbuf *);
89772e66a6SGleb Smirnoff extern void _flushq(class_queue_t *);
90772e66a6SGleb Smirnoff
91772e66a6SGleb Smirnoff #else /* __GNUC__ && !ALTQ_DEBUG */
92772e66a6SGleb Smirnoff /*
93772e66a6SGleb Smirnoff * inlined versions
94772e66a6SGleb Smirnoff */
95772e66a6SGleb Smirnoff static __inline void
_addq(class_queue_t * q,struct mbuf * m)96772e66a6SGleb Smirnoff _addq(class_queue_t *q, struct mbuf *m)
97772e66a6SGleb Smirnoff {
98772e66a6SGleb Smirnoff struct mbuf *m0;
99772e66a6SGleb Smirnoff
100772e66a6SGleb Smirnoff if ((m0 = qtail(q)) != NULL)
101772e66a6SGleb Smirnoff m->m_nextpkt = m0->m_nextpkt;
102772e66a6SGleb Smirnoff else
103772e66a6SGleb Smirnoff m0 = m;
104772e66a6SGleb Smirnoff m0->m_nextpkt = m;
105772e66a6SGleb Smirnoff qtail(q) = m;
106772e66a6SGleb Smirnoff qlen(q)++;
1070a70aaf8SLuiz Otavio O Souza qsize(q) += m_pktlen(m);
108772e66a6SGleb Smirnoff }
109772e66a6SGleb Smirnoff
110772e66a6SGleb Smirnoff static __inline struct mbuf *
_getq(class_queue_t * q)111772e66a6SGleb Smirnoff _getq(class_queue_t *q)
112772e66a6SGleb Smirnoff {
113772e66a6SGleb Smirnoff struct mbuf *m, *m0;
114772e66a6SGleb Smirnoff
115772e66a6SGleb Smirnoff if ((m = qtail(q)) == NULL)
116772e66a6SGleb Smirnoff return (NULL);
117772e66a6SGleb Smirnoff if ((m0 = m->m_nextpkt) != m)
118772e66a6SGleb Smirnoff m->m_nextpkt = m0->m_nextpkt;
119772e66a6SGleb Smirnoff else
120772e66a6SGleb Smirnoff qtail(q) = NULL;
121772e66a6SGleb Smirnoff qlen(q)--;
1220a70aaf8SLuiz Otavio O Souza qsize(q) -= m_pktlen(m0);
123772e66a6SGleb Smirnoff m0->m_nextpkt = NULL;
124772e66a6SGleb Smirnoff return (m0);
125772e66a6SGleb Smirnoff }
126772e66a6SGleb Smirnoff
127772e66a6SGleb Smirnoff /* drop a packet at the tail of the queue */
128772e66a6SGleb Smirnoff static __inline struct mbuf *
_getq_tail(class_queue_t * q)129772e66a6SGleb Smirnoff _getq_tail(class_queue_t *q)
130772e66a6SGleb Smirnoff {
131772e66a6SGleb Smirnoff struct mbuf *m, *m0, *prev;
132772e66a6SGleb Smirnoff
133772e66a6SGleb Smirnoff if ((m = m0 = qtail(q)) == NULL)
134772e66a6SGleb Smirnoff return NULL;
135772e66a6SGleb Smirnoff do {
136772e66a6SGleb Smirnoff prev = m0;
137772e66a6SGleb Smirnoff m0 = m0->m_nextpkt;
138772e66a6SGleb Smirnoff } while (m0 != m);
139772e66a6SGleb Smirnoff prev->m_nextpkt = m->m_nextpkt;
140772e66a6SGleb Smirnoff if (prev == m)
141772e66a6SGleb Smirnoff qtail(q) = NULL;
142772e66a6SGleb Smirnoff else
143772e66a6SGleb Smirnoff qtail(q) = prev;
144772e66a6SGleb Smirnoff qlen(q)--;
145772e66a6SGleb Smirnoff m->m_nextpkt = NULL;
146772e66a6SGleb Smirnoff return (m);
147772e66a6SGleb Smirnoff }
148772e66a6SGleb Smirnoff
149772e66a6SGleb Smirnoff /* randomly select a packet in the queue */
150772e66a6SGleb Smirnoff static __inline struct mbuf *
_getq_random(class_queue_t * q)151772e66a6SGleb Smirnoff _getq_random(class_queue_t *q)
152772e66a6SGleb Smirnoff {
153772e66a6SGleb Smirnoff struct mbuf *m;
154772e66a6SGleb Smirnoff int i, n;
155772e66a6SGleb Smirnoff
156772e66a6SGleb Smirnoff if ((m = qtail(q)) == NULL)
157772e66a6SGleb Smirnoff return NULL;
158772e66a6SGleb Smirnoff if (m->m_nextpkt == m)
159772e66a6SGleb Smirnoff qtail(q) = NULL;
160772e66a6SGleb Smirnoff else {
161772e66a6SGleb Smirnoff struct mbuf *prev = NULL;
162772e66a6SGleb Smirnoff
163772e66a6SGleb Smirnoff n = random() % qlen(q) + 1;
164772e66a6SGleb Smirnoff for (i = 0; i < n; i++) {
165772e66a6SGleb Smirnoff prev = m;
166772e66a6SGleb Smirnoff m = m->m_nextpkt;
167772e66a6SGleb Smirnoff }
168772e66a6SGleb Smirnoff prev->m_nextpkt = m->m_nextpkt;
169772e66a6SGleb Smirnoff if (m == qtail(q))
170772e66a6SGleb Smirnoff qtail(q) = prev;
171772e66a6SGleb Smirnoff }
172772e66a6SGleb Smirnoff qlen(q)--;
173772e66a6SGleb Smirnoff m->m_nextpkt = NULL;
174772e66a6SGleb Smirnoff return (m);
175772e66a6SGleb Smirnoff }
176772e66a6SGleb Smirnoff
177772e66a6SGleb Smirnoff static __inline void
_removeq(class_queue_t * q,struct mbuf * m)178772e66a6SGleb Smirnoff _removeq(class_queue_t *q, struct mbuf *m)
179772e66a6SGleb Smirnoff {
180772e66a6SGleb Smirnoff struct mbuf *m0, *prev;
181772e66a6SGleb Smirnoff
182772e66a6SGleb Smirnoff m0 = qtail(q);
183772e66a6SGleb Smirnoff do {
184772e66a6SGleb Smirnoff prev = m0;
185772e66a6SGleb Smirnoff m0 = m0->m_nextpkt;
186772e66a6SGleb Smirnoff } while (m0 != m);
187772e66a6SGleb Smirnoff prev->m_nextpkt = m->m_nextpkt;
188772e66a6SGleb Smirnoff if (prev == m)
189772e66a6SGleb Smirnoff qtail(q) = NULL;
190772e66a6SGleb Smirnoff else if (qtail(q) == m)
191772e66a6SGleb Smirnoff qtail(q) = prev;
192772e66a6SGleb Smirnoff qlen(q)--;
193772e66a6SGleb Smirnoff }
194772e66a6SGleb Smirnoff
195772e66a6SGleb Smirnoff static __inline void
_flushq(class_queue_t * q)196772e66a6SGleb Smirnoff _flushq(class_queue_t *q)
197772e66a6SGleb Smirnoff {
198772e66a6SGleb Smirnoff struct mbuf *m;
199772e66a6SGleb Smirnoff
200772e66a6SGleb Smirnoff while ((m = _getq(q)) != NULL)
201772e66a6SGleb Smirnoff m_freem(m);
202772e66a6SGleb Smirnoff }
203772e66a6SGleb Smirnoff
204772e66a6SGleb Smirnoff #endif /* __GNUC__ && !ALTQ_DEBUG */
205772e66a6SGleb Smirnoff
206772e66a6SGleb Smirnoff #endif /* _KERNEL */
207772e66a6SGleb Smirnoff
208772e66a6SGleb Smirnoff #ifdef __cplusplus
209772e66a6SGleb Smirnoff }
210772e66a6SGleb Smirnoff #endif
211772e66a6SGleb Smirnoff
212772e66a6SGleb Smirnoff #endif /* _ALTQ_ALTQ_CLASSQ_H_ */
213