1 /*- 2 * Copyright (c) 1991-1997 Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the Network Research 16 * Group at Lawrence Berkeley Laboratory. 17 * 4. Neither the name of the University nor of the Laboratory may be used 18 * to endorse or promote products derived from this software without 19 * specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * 33 * $KAME: altq_classq.h,v 1.6 2003/01/07 07:33:38 kjc Exp $ 34 * $FreeBSD$ 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 /* 57 * Packet Queue structures and macros to manipulate them. 58 */ 59 struct _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 66 typedef 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 81 extern void _addq(class_queue_t *, struct mbuf *); 82 extern struct mbuf *_getq(class_queue_t *); 83 extern struct mbuf *_getq_tail(class_queue_t *); 84 extern struct mbuf *_getq_random(class_queue_t *); 85 extern void _removeq(class_queue_t *, struct mbuf *); 86 extern void _flushq(class_queue_t *); 87 88 #else /* __GNUC__ && !ALTQ_DEBUG */ 89 /* 90 * inlined versions 91 */ 92 static __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 106 static __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 */ 123 static __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 */ 145 static __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 172 static __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 190 static __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