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 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 * 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 * 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 * 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 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 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