1 /* $NetBSD: altq_classq.h,v 1.12 2025/01/22 22:41:38 joe Exp $ */
2 /* $KAME: altq_classq.h,v 1.6 2003/01/07 07:33:38 kjc Exp $ */
3
4 /*
5 * Copyright (c) 1991-1997 Regents of the University of California.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the Network Research
19 * Group at Lawrence Berkeley Laboratory.
20 * 4. Neither the name of the University nor of the Laboratory may be used
21 * to endorse or promote products derived from this software without
22 * specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36 /*
37 * class queue definitions extracted from rm_class.h.
38 */
39 #ifndef _ALTQ_ALTQ_CLASSQ_H_
40 #define _ALTQ_ALTQ_CLASSQ_H_
41
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45
46 /*
47 * Packet Queue types: RED or DROPHEAD.
48 */
49 #define Q_DROPHEAD 0x00
50 #define Q_RED 0x01
51 #define Q_RIO 0x02
52 #define Q_DROPTAIL 0x03
53
54 #ifdef _KERNEL
55
56 #include <sys/cprng.h>
57
58 /*
59 * Packet Queue structures and macros to manipulate them.
60 */
61 struct _class_queue_ {
62 struct mbuf *tail_; /* Tail of packet queue */
63 int qlen_; /* Queue length (in number of packets) */
64 int qlim_; /* Queue limit (in number of packets*) */
65 int qtype_; /* Queue type */
66 };
67
68 typedef struct _class_queue_ class_queue_t;
69
70 #define qtype(q) (q)->qtype_ /* Get queue type */
71 #define qlimit(q) (q)->qlim_ /* Max packets to be queued */
72 #define qlen(q) (q)->qlen_ /* Current queue length. */
73 #define qtail(q) (q)->tail_ /* Tail of the queue */
74 #define qhead(q) ((q)->tail_ ? (q)->tail_->m_nextpkt : NULL)
75
76 #define qempty(q) ((q)->qlen_ == 0) /* Is the queue empty?? */
77 #define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a red queue */
78 #define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a rio queue */
79 #define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO)
80
81 #if !defined(__GNUC__) || defined(ALTQ_DEBUG)
82
83 extern void _addq(class_queue_t *, struct mbuf *);
84 extern struct mbuf *_getq(class_queue_t *);
85 extern struct mbuf *_getq_tail(class_queue_t *);
86 extern struct mbuf *_getq_random(class_queue_t *);
87 extern void _removeq(class_queue_t *, struct mbuf *);
88 extern void _flushq(class_queue_t *);
89
90 #else /* __GNUC__ && !ALTQ_DEBUG */
91 /*
92 * inlined versions
93 */
94 static __inline void
_addq(class_queue_t * q,struct mbuf * m)95 _addq(class_queue_t *q, struct mbuf *m)
96 {
97 struct mbuf *m0;
98
99 if ((m0 = qtail(q)) != NULL)
100 m->m_nextpkt = m0->m_nextpkt;
101 else
102 m0 = m;
103 m0->m_nextpkt = m;
104 qtail(q) = m;
105 qlen(q)++;
106 }
107
108 static __inline struct mbuf *
_getq(class_queue_t * q)109 _getq(class_queue_t *q)
110 {
111 struct mbuf *m, *m0;
112
113 if ((m = qtail(q)) == NULL)
114 return NULL;
115 if ((m0 = m->m_nextpkt) != m)
116 m->m_nextpkt = m0->m_nextpkt;
117 else
118 qtail(q) = NULL;
119 qlen(q)--;
120 m0->m_nextpkt = NULL;
121 return m0;
122 }
123
124 /* drop a packet at the tail of the queue */
125 static __inline struct mbuf *
_getq_tail(class_queue_t * q)126 _getq_tail(class_queue_t *q)
127 {
128 struct mbuf *m, *m0, *prev;
129
130 if ((m = m0 = qtail(q)) == NULL)
131 return NULL;
132 do {
133 prev = m0;
134 m0 = m0->m_nextpkt;
135 } while (m0 != m);
136 prev->m_nextpkt = m->m_nextpkt;
137 if (prev == m)
138 qtail(q) = NULL;
139 else
140 qtail(q) = prev;
141 qlen(q)--;
142 m->m_nextpkt = NULL;
143 return m;
144 }
145
146 /* randomly select a packet in the queue */
147 static __inline struct mbuf *
_getq_random(class_queue_t * q)148 _getq_random(class_queue_t *q)
149 {
150 struct mbuf *m;
151 int i, n;
152
153 if ((m = qtail(q)) == NULL)
154 return NULL;
155 if (m->m_nextpkt == m)
156 qtail(q) = NULL;
157 else {
158 struct mbuf *prev = NULL;
159
160 n = cprng_fast32() % qlen(q) + 1;
161 for (i = 0; i < n; i++) {
162 prev = m;
163 m = m->m_nextpkt;
164 }
165 prev->m_nextpkt = m->m_nextpkt;
166 if (m == qtail(q))
167 qtail(q) = prev;
168 }
169 qlen(q)--;
170 m->m_nextpkt = NULL;
171 return m;
172 }
173
174 static __inline void
_removeq(class_queue_t * q,struct mbuf * m)175 _removeq(class_queue_t *q, struct mbuf *m)
176 {
177 struct mbuf *m0, *prev;
178
179 m0 = qtail(q);
180 do {
181 prev = m0;
182 m0 = m0->m_nextpkt;
183 } while (m0 != m);
184 prev->m_nextpkt = m->m_nextpkt;
185 if (prev == m)
186 qtail(q) = NULL;
187 else if (qtail(q) == m)
188 qtail(q) = prev;
189 qlen(q)--;
190 }
191
192 static __inline void
_flushq(class_queue_t * q)193 _flushq(class_queue_t *q)
194 {
195 struct mbuf *m;
196
197 while ((m = _getq(q)) != NULL)
198 m_freem(m);
199 }
200
201 #endif /* __GNUC__ && !ALTQ_DEBUG */
202
203 #endif /* _KERNEL */
204
205 #ifdef __cplusplus
206 }
207 #endif
208
209 #endif /* _ALTQ_ALTQ_CLASSQ_H_ */
210