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 $ 34da8ae05dSGleb Smirnoff * $FreeBSD$ 35772e66a6SGleb Smirnoff */ 36772e66a6SGleb Smirnoff /* 37772e66a6SGleb Smirnoff * class queue definitions extracted from rm_class.h. 38772e66a6SGleb Smirnoff */ 39772e66a6SGleb Smirnoff #ifndef _ALTQ_ALTQ_CLASSQ_H_ 40772e66a6SGleb Smirnoff #define _ALTQ_ALTQ_CLASSQ_H_ 41772e66a6SGleb Smirnoff 42772e66a6SGleb Smirnoff #ifdef __cplusplus 43772e66a6SGleb Smirnoff extern "C" { 44772e66a6SGleb Smirnoff #endif 45772e66a6SGleb Smirnoff 46772e66a6SGleb Smirnoff /* 47772e66a6SGleb Smirnoff * Packet Queue types: RED or DROPHEAD. 48772e66a6SGleb Smirnoff */ 49772e66a6SGleb Smirnoff #define Q_DROPHEAD 0x00 50772e66a6SGleb Smirnoff #define Q_RED 0x01 51772e66a6SGleb Smirnoff #define Q_RIO 0x02 52772e66a6SGleb Smirnoff #define Q_DROPTAIL 0x03 530a70aaf8SLuiz Otavio O Souza #define Q_CODEL 0x04 54772e66a6SGleb Smirnoff 55772e66a6SGleb Smirnoff #ifdef _KERNEL 56772e66a6SGleb Smirnoff 57772e66a6SGleb Smirnoff /* 58772e66a6SGleb Smirnoff * Packet Queue structures and macros to manipulate them. 59772e66a6SGleb Smirnoff */ 60772e66a6SGleb Smirnoff struct _class_queue_ { 61772e66a6SGleb Smirnoff struct mbuf *tail_; /* Tail of packet queue */ 62772e66a6SGleb Smirnoff int qlen_; /* Queue length (in number of packets) */ 63772e66a6SGleb Smirnoff int qlim_; /* Queue limit (in number of packets*) */ 640a70aaf8SLuiz Otavio O Souza int qsize_; /* Queue size (in number of bytes*) */ 65772e66a6SGleb Smirnoff int qtype_; /* Queue type */ 66772e66a6SGleb Smirnoff }; 67772e66a6SGleb Smirnoff 68772e66a6SGleb Smirnoff typedef struct _class_queue_ class_queue_t; 69772e66a6SGleb Smirnoff 70772e66a6SGleb Smirnoff #define qtype(q) (q)->qtype_ /* Get queue type */ 71772e66a6SGleb Smirnoff #define qlimit(q) (q)->qlim_ /* Max packets to be queued */ 72772e66a6SGleb Smirnoff #define qlen(q) (q)->qlen_ /* Current queue length. */ 730a70aaf8SLuiz Otavio O Souza #define qsize(q) (q)->qsize_ /* Current queue size. */ 74772e66a6SGleb Smirnoff #define qtail(q) (q)->tail_ /* Tail of the queue */ 75772e66a6SGleb Smirnoff #define qhead(q) ((q)->tail_ ? (q)->tail_->m_nextpkt : NULL) 76772e66a6SGleb Smirnoff 77772e66a6SGleb Smirnoff #define qempty(q) ((q)->qlen_ == 0) /* Is the queue empty?? */ 780a70aaf8SLuiz Otavio O Souza #define q_is_codel(q) ((q)->qtype_ == Q_CODEL) /* Is the queue a codel queue */ 79772e66a6SGleb Smirnoff #define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a red queue */ 80772e66a6SGleb Smirnoff #define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a rio queue */ 81772e66a6SGleb Smirnoff #define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO) 82772e66a6SGleb Smirnoff 83772e66a6SGleb Smirnoff #if !defined(__GNUC__) || defined(ALTQ_DEBUG) 84772e66a6SGleb Smirnoff 85772e66a6SGleb Smirnoff extern void _addq(class_queue_t *, struct mbuf *); 86772e66a6SGleb Smirnoff extern struct mbuf *_getq(class_queue_t *); 87772e66a6SGleb Smirnoff extern struct mbuf *_getq_tail(class_queue_t *); 88772e66a6SGleb Smirnoff extern struct mbuf *_getq_random(class_queue_t *); 89772e66a6SGleb Smirnoff extern void _removeq(class_queue_t *, struct mbuf *); 90772e66a6SGleb Smirnoff extern void _flushq(class_queue_t *); 91772e66a6SGleb Smirnoff 92772e66a6SGleb Smirnoff #else /* __GNUC__ && !ALTQ_DEBUG */ 93772e66a6SGleb Smirnoff /* 94772e66a6SGleb Smirnoff * inlined versions 95772e66a6SGleb Smirnoff */ 96772e66a6SGleb Smirnoff static __inline void 97772e66a6SGleb Smirnoff _addq(class_queue_t *q, struct mbuf *m) 98772e66a6SGleb Smirnoff { 99772e66a6SGleb Smirnoff struct mbuf *m0; 100772e66a6SGleb Smirnoff 101772e66a6SGleb Smirnoff if ((m0 = qtail(q)) != NULL) 102772e66a6SGleb Smirnoff m->m_nextpkt = m0->m_nextpkt; 103772e66a6SGleb Smirnoff else 104772e66a6SGleb Smirnoff m0 = m; 105772e66a6SGleb Smirnoff m0->m_nextpkt = m; 106772e66a6SGleb Smirnoff qtail(q) = m; 107772e66a6SGleb Smirnoff qlen(q)++; 1080a70aaf8SLuiz Otavio O Souza qsize(q) += m_pktlen(m); 109772e66a6SGleb Smirnoff } 110772e66a6SGleb Smirnoff 111772e66a6SGleb Smirnoff static __inline struct mbuf * 112772e66a6SGleb Smirnoff _getq(class_queue_t *q) 113772e66a6SGleb Smirnoff { 114772e66a6SGleb Smirnoff struct mbuf *m, *m0; 115772e66a6SGleb Smirnoff 116772e66a6SGleb Smirnoff if ((m = qtail(q)) == NULL) 117772e66a6SGleb Smirnoff return (NULL); 118772e66a6SGleb Smirnoff if ((m0 = m->m_nextpkt) != m) 119772e66a6SGleb Smirnoff m->m_nextpkt = m0->m_nextpkt; 120772e66a6SGleb Smirnoff else 121772e66a6SGleb Smirnoff qtail(q) = NULL; 122772e66a6SGleb Smirnoff qlen(q)--; 1230a70aaf8SLuiz Otavio O Souza qsize(q) -= m_pktlen(m0); 124772e66a6SGleb Smirnoff m0->m_nextpkt = NULL; 125772e66a6SGleb Smirnoff return (m0); 126772e66a6SGleb Smirnoff } 127772e66a6SGleb Smirnoff 128772e66a6SGleb Smirnoff /* drop a packet at the tail of the queue */ 129772e66a6SGleb Smirnoff static __inline struct mbuf * 130772e66a6SGleb Smirnoff _getq_tail(class_queue_t *q) 131772e66a6SGleb Smirnoff { 132772e66a6SGleb Smirnoff struct mbuf *m, *m0, *prev; 133772e66a6SGleb Smirnoff 134772e66a6SGleb Smirnoff if ((m = m0 = qtail(q)) == NULL) 135772e66a6SGleb Smirnoff return NULL; 136772e66a6SGleb Smirnoff do { 137772e66a6SGleb Smirnoff prev = m0; 138772e66a6SGleb Smirnoff m0 = m0->m_nextpkt; 139772e66a6SGleb Smirnoff } while (m0 != m); 140772e66a6SGleb Smirnoff prev->m_nextpkt = m->m_nextpkt; 141772e66a6SGleb Smirnoff if (prev == m) 142772e66a6SGleb Smirnoff qtail(q) = NULL; 143772e66a6SGleb Smirnoff else 144772e66a6SGleb Smirnoff qtail(q) = prev; 145772e66a6SGleb Smirnoff qlen(q)--; 146772e66a6SGleb Smirnoff m->m_nextpkt = NULL; 147772e66a6SGleb Smirnoff return (m); 148772e66a6SGleb Smirnoff } 149772e66a6SGleb Smirnoff 150772e66a6SGleb Smirnoff /* randomly select a packet in the queue */ 151772e66a6SGleb Smirnoff static __inline struct mbuf * 152772e66a6SGleb Smirnoff _getq_random(class_queue_t *q) 153772e66a6SGleb Smirnoff { 154772e66a6SGleb Smirnoff struct mbuf *m; 155772e66a6SGleb Smirnoff int i, n; 156772e66a6SGleb Smirnoff 157772e66a6SGleb Smirnoff if ((m = qtail(q)) == NULL) 158772e66a6SGleb Smirnoff return NULL; 159772e66a6SGleb Smirnoff if (m->m_nextpkt == m) 160772e66a6SGleb Smirnoff qtail(q) = NULL; 161772e66a6SGleb Smirnoff else { 162772e66a6SGleb Smirnoff struct mbuf *prev = NULL; 163772e66a6SGleb Smirnoff 164772e66a6SGleb Smirnoff n = random() % qlen(q) + 1; 165772e66a6SGleb Smirnoff for (i = 0; i < n; i++) { 166772e66a6SGleb Smirnoff prev = m; 167772e66a6SGleb Smirnoff m = m->m_nextpkt; 168772e66a6SGleb Smirnoff } 169772e66a6SGleb Smirnoff prev->m_nextpkt = m->m_nextpkt; 170772e66a6SGleb Smirnoff if (m == qtail(q)) 171772e66a6SGleb Smirnoff qtail(q) = prev; 172772e66a6SGleb Smirnoff } 173772e66a6SGleb Smirnoff qlen(q)--; 174772e66a6SGleb Smirnoff m->m_nextpkt = NULL; 175772e66a6SGleb Smirnoff return (m); 176772e66a6SGleb Smirnoff } 177772e66a6SGleb Smirnoff 178772e66a6SGleb Smirnoff static __inline void 179772e66a6SGleb Smirnoff _removeq(class_queue_t *q, struct mbuf *m) 180772e66a6SGleb Smirnoff { 181772e66a6SGleb Smirnoff struct mbuf *m0, *prev; 182772e66a6SGleb Smirnoff 183772e66a6SGleb Smirnoff m0 = qtail(q); 184772e66a6SGleb Smirnoff do { 185772e66a6SGleb Smirnoff prev = m0; 186772e66a6SGleb Smirnoff m0 = m0->m_nextpkt; 187772e66a6SGleb Smirnoff } while (m0 != m); 188772e66a6SGleb Smirnoff prev->m_nextpkt = m->m_nextpkt; 189772e66a6SGleb Smirnoff if (prev == m) 190772e66a6SGleb Smirnoff qtail(q) = NULL; 191772e66a6SGleb Smirnoff else if (qtail(q) == m) 192772e66a6SGleb Smirnoff qtail(q) = prev; 193772e66a6SGleb Smirnoff qlen(q)--; 194772e66a6SGleb Smirnoff } 195772e66a6SGleb Smirnoff 196772e66a6SGleb Smirnoff static __inline void 197772e66a6SGleb Smirnoff _flushq(class_queue_t *q) 198772e66a6SGleb Smirnoff { 199772e66a6SGleb Smirnoff struct mbuf *m; 200772e66a6SGleb Smirnoff 201772e66a6SGleb Smirnoff while ((m = _getq(q)) != NULL) 202772e66a6SGleb Smirnoff m_freem(m); 203772e66a6SGleb Smirnoff } 204772e66a6SGleb Smirnoff 205772e66a6SGleb Smirnoff #endif /* __GNUC__ && !ALTQ_DEBUG */ 206772e66a6SGleb Smirnoff 207772e66a6SGleb Smirnoff #endif /* _KERNEL */ 208772e66a6SGleb Smirnoff 209772e66a6SGleb Smirnoff #ifdef __cplusplus 210772e66a6SGleb Smirnoff } 211772e66a6SGleb Smirnoff #endif 212772e66a6SGleb Smirnoff 213772e66a6SGleb Smirnoff #endif /* _ALTQ_ALTQ_CLASSQ_H_ */ 214