1/* $NetBSD: altq_classq.h,v 1.8 2018/04/19 21:50:06 christos 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
43extern "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/*
57 * Packet Queue structures and macros to manipulate them.
58 */
59struct _class_queue_ {
60 struct mbuf *tail_; /* Tail of packet queue */
61 int qlen_; /* Queue length (in number of packets) */
62 int qlim_; /* Queue limit (in number of packets*) */
63 int qtype_; /* Queue type */
64};
65
66typedef struct _class_queue_ class_queue_t;
67
68#define qtype(q) (q)->qtype_ /* Get queue type */
69#define qlimit(q) (q)->qlim_ /* Max packets to be queued */
70#define qlen(q) (q)->qlen_ /* Current queue length. */
71#define qtail(q) (q)->tail_ /* Tail of the queue */
72#define qhead(q) ((q)->tail_ ? (q)->tail_->m_nextpkt : NULL)
73
74#define qempty(q) ((q)->qlen_ == 0) /* Is the queue empty?? */
75#define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a red queue */
76#define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a rio queue */
77#define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO)
78
79#if !defined(__GNUC__) || defined(ALTQ_DEBUG)
80
81extern void _addq(class_queue_t *, struct mbuf *);
82extern struct mbuf *_getq(class_queue_t *);
83extern struct mbuf *_getq_tail(class_queue_t *);
84extern struct mbuf *_getq_random(class_queue_t *);
85extern void _removeq(class_queue_t *, struct mbuf *);
86extern void _flushq(class_queue_t *);
87
88#else /* __GNUC__ && !ALTQ_DEBUG */
89/*
90 * inlined versions
91 */
92static __inline void
93_addq(class_queue_t *q, struct mbuf *m)
94{
95 struct mbuf *m0;
96
97 if ((m0 = qtail(q)) != NULL)
98 m->m_nextpkt = m0->m_nextpkt;
99 else
100 m0 = m;
101 m0->m_nextpkt = m;
102 qtail(q) = m;
103 qlen(q)++;
104}
105
106static __inline struct mbuf *
107_getq(class_queue_t *q)
108{
109 struct mbuf *m, *m0;
110
111 if ((m = qtail(q)) == NULL)
112 return (NULL);
113 if ((m0 = m->m_nextpkt) != m)
114 m->m_nextpkt = m0->m_nextpkt;
115 else
116 qtail(q) = NULL;
117 qlen(q)--;
118 m0->m_nextpkt = NULL;
119 return (m0);
120}
121
122/* drop a packet at the tail of the queue */
123static __inline struct mbuf *
124_getq_tail(class_queue_t *q)
125{
126 struct mbuf *m, *m0, *prev;
127
128 if ((m = m0 = qtail(q)) == NULL)
129 return NULL;
130 do {
131 prev = m0;
132 m0 = m0->m_nextpkt;
133 } while (m0 != m);
134 prev->m_nextpkt = m->m_nextpkt;
135 if (prev == m)
136 qtail(q) = NULL;
137 else
138 qtail(q) = prev;
139 qlen(q)--;
140 m->m_nextpkt = NULL;
141 return (m);
142}
143
144/* randomly select a packet in the queue */
145static __inline struct mbuf *
146_getq_random(class_queue_t *q)
147{
148 struct mbuf *m;
149 int i, n;
150
151 if ((m = qtail(q)) == NULL)
152 return NULL;
153 if (m->m_nextpkt == m)
154 qtail(q) = NULL;
155 else {
156 struct mbuf *prev = NULL;
157
158 n = random() % qlen(q) + 1;
159 for (i = 0; i < n; i++) {
160 prev = m;
161 m = m->m_nextpkt;
162 }
163 prev->m_nextpkt = m->m_nextpkt;
164 if (m == qtail(q))
165 qtail(q) = prev;
166 }
167 qlen(q)--;
168 m->m_nextpkt = NULL;
169 return (m);
170}
171
172static __inline void
173_removeq(class_queue_t *q, struct mbuf *m)
174{
175 struct mbuf *m0, *prev;
176
177 m0 = qtail(q);
178 do {
179 prev = m0;
180 m0 = m0->m_nextpkt;
181 } while (m0 != m);
182 prev->m_nextpkt = m->m_nextpkt;
183 if (prev == m)
184 qtail(q) = NULL;
185 else if (qtail(q) == m)
186 qtail(q) = prev;
187 qlen(q)--;
188}
189
190static __inline void
191_flushq(class_queue_t *q)
192{
193 struct mbuf *m;
194
195 while ((m = _getq(q)) != NULL)
196 m_freem(m);
197}
198
199#endif /* __GNUC__ && !ALTQ_DEBUG */
200
201#endif /* _KERNEL */
202
203#ifdef __cplusplus
204}
205#endif
206
207#endif /* _ALTQ_ALTQ_CLASSQ_H_ */
208