1130365Smlaier/* $KAME: altq_classq.h,v 1.6 2003/01/07 07:33:38 kjc Exp $ */ 2130365Smlaier 3130365Smlaier/* 4130365Smlaier * Copyright (c) 1991-1997 Regents of the University of California. 5130365Smlaier * All rights reserved. 6130365Smlaier * 7130365Smlaier * Redistribution and use in source and binary forms, with or without 8130365Smlaier * modification, are permitted provided that the following conditions 9130365Smlaier * are met: 10130365Smlaier * 1. Redistributions of source code must retain the above copyright 11130365Smlaier * notice, this list of conditions and the following disclaimer. 12130365Smlaier * 2. Redistributions in binary form must reproduce the above copyright 13130365Smlaier * notice, this list of conditions and the following disclaimer in the 14130365Smlaier * documentation and/or other materials provided with the distribution. 15130365Smlaier * 3. All advertising materials mentioning features or use of this software 16130365Smlaier * must display the following acknowledgement: 17130365Smlaier * This product includes software developed by the Network Research 18130365Smlaier * Group at Lawrence Berkeley Laboratory. 19130365Smlaier * 4. Neither the name of the University nor of the Laboratory may be used 20130365Smlaier * to endorse or promote products derived from this software without 21130365Smlaier * specific prior written permission. 22130365Smlaier * 23130365Smlaier * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24130365Smlaier * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25130365Smlaier * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26130365Smlaier * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27130365Smlaier * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28130365Smlaier * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29130365Smlaier * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30130365Smlaier * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31130365Smlaier * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32130365Smlaier * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33130365Smlaier * SUCH DAMAGE. 34130365Smlaier */ 35130365Smlaier/* 36130365Smlaier * class queue definitions extracted from rm_class.h. 37130365Smlaier */ 38130365Smlaier#ifndef _ALTQ_ALTQ_CLASSQ_H_ 39130365Smlaier#define _ALTQ_ALTQ_CLASSQ_H_ 40130365Smlaier 41130365Smlaier#ifdef __cplusplus 42130365Smlaierextern "C" { 43130365Smlaier#endif 44130365Smlaier 45130365Smlaier/* 46130365Smlaier * Packet Queue types: RED or DROPHEAD. 47130365Smlaier */ 48130365Smlaier#define Q_DROPHEAD 0x00 49130365Smlaier#define Q_RED 0x01 50130365Smlaier#define Q_RIO 0x02 51130365Smlaier#define Q_DROPTAIL 0x03 52130365Smlaier 53130365Smlaier#ifdef _KERNEL 54130365Smlaier 55130365Smlaier/* 56130365Smlaier * Packet Queue structures and macros to manipulate them. 57130365Smlaier */ 58130365Smlaierstruct _class_queue_ { 59130365Smlaier struct mbuf *tail_; /* Tail of packet queue */ 60130365Smlaier int qlen_; /* Queue length (in number of packets) */ 61130365Smlaier int qlim_; /* Queue limit (in number of packets*) */ 62130365Smlaier int qtype_; /* Queue type */ 63130365Smlaier}; 64130365Smlaier 65130365Smlaiertypedef struct _class_queue_ class_queue_t; 66130365Smlaier 67130365Smlaier#define qtype(q) (q)->qtype_ /* Get queue type */ 68130365Smlaier#define qlimit(q) (q)->qlim_ /* Max packets to be queued */ 69130365Smlaier#define qlen(q) (q)->qlen_ /* Current queue length. */ 70130365Smlaier#define qtail(q) (q)->tail_ /* Tail of the queue */ 71130365Smlaier#define qhead(q) ((q)->tail_ ? (q)->tail_->m_nextpkt : NULL) 72130365Smlaier 73130365Smlaier#define qempty(q) ((q)->qlen_ == 0) /* Is the queue empty?? */ 74130365Smlaier#define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a red queue */ 75130365Smlaier#define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a rio queue */ 76130365Smlaier#define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO) 77130365Smlaier 78130365Smlaier#if !defined(__GNUC__) || defined(ALTQ_DEBUG) 79130365Smlaier 80130365Smlaierextern void _addq(class_queue_t *, struct mbuf *); 81130365Smlaierextern struct mbuf *_getq(class_queue_t *); 82130365Smlaierextern struct mbuf *_getq_tail(class_queue_t *); 83130365Smlaierextern struct mbuf *_getq_random(class_queue_t *); 84130365Smlaierextern void _removeq(class_queue_t *, struct mbuf *); 85130365Smlaierextern void _flushq(class_queue_t *); 86130365Smlaier 87130365Smlaier#else /* __GNUC__ && !ALTQ_DEBUG */ 88130365Smlaier/* 89130365Smlaier * inlined versions 90130365Smlaier */ 91130365Smlaierstatic __inline void 92130365Smlaier_addq(class_queue_t *q, struct mbuf *m) 93130365Smlaier{ 94130365Smlaier struct mbuf *m0; 95130365Smlaier 96130365Smlaier if ((m0 = qtail(q)) != NULL) 97130365Smlaier m->m_nextpkt = m0->m_nextpkt; 98130365Smlaier else 99130365Smlaier m0 = m; 100130365Smlaier m0->m_nextpkt = m; 101130365Smlaier qtail(q) = m; 102130365Smlaier qlen(q)++; 103130365Smlaier} 104130365Smlaier 105130365Smlaierstatic __inline struct mbuf * 106130365Smlaier_getq(class_queue_t *q) 107130365Smlaier{ 108130365Smlaier struct mbuf *m, *m0; 109130365Smlaier 110130365Smlaier if ((m = qtail(q)) == NULL) 111130365Smlaier return (NULL); 112130365Smlaier if ((m0 = m->m_nextpkt) != m) 113130365Smlaier m->m_nextpkt = m0->m_nextpkt; 114130365Smlaier else 115130365Smlaier qtail(q) = NULL; 116130365Smlaier qlen(q)--; 117130365Smlaier m0->m_nextpkt = NULL; 118130365Smlaier return (m0); 119130365Smlaier} 120130365Smlaier 121130365Smlaier/* drop a packet at the tail of the queue */ 122130365Smlaierstatic __inline struct mbuf * 123130365Smlaier_getq_tail(class_queue_t *q) 124130365Smlaier{ 125130365Smlaier struct mbuf *m, *m0, *prev; 126130365Smlaier 127130365Smlaier if ((m = m0 = qtail(q)) == NULL) 128130365Smlaier return NULL; 129130365Smlaier do { 130130365Smlaier prev = m0; 131130365Smlaier m0 = m0->m_nextpkt; 132130365Smlaier } while (m0 != m); 133130365Smlaier prev->m_nextpkt = m->m_nextpkt; 134130365Smlaier if (prev == m) 135130365Smlaier qtail(q) = NULL; 136130365Smlaier else 137130365Smlaier qtail(q) = prev; 138130365Smlaier qlen(q)--; 139130365Smlaier m->m_nextpkt = NULL; 140130365Smlaier return (m); 141130365Smlaier} 142130365Smlaier 143130365Smlaier/* randomly select a packet in the queue */ 144130365Smlaierstatic __inline struct mbuf * 145130365Smlaier_getq_random(class_queue_t *q) 146130365Smlaier{ 147130365Smlaier struct mbuf *m; 148130365Smlaier int i, n; 149130365Smlaier 150130365Smlaier if ((m = qtail(q)) == NULL) 151130365Smlaier return NULL; 152130365Smlaier if (m->m_nextpkt == m) 153130365Smlaier qtail(q) = NULL; 154130365Smlaier else { 155130365Smlaier struct mbuf *prev = NULL; 156130365Smlaier 157130365Smlaier n = random() % qlen(q) + 1; 158130365Smlaier for (i = 0; i < n; i++) { 159130365Smlaier prev = m; 160130365Smlaier m = m->m_nextpkt; 161130365Smlaier } 162130365Smlaier prev->m_nextpkt = m->m_nextpkt; 163130365Smlaier if (m == qtail(q)) 164130365Smlaier qtail(q) = prev; 165130365Smlaier } 166130365Smlaier qlen(q)--; 167130365Smlaier m->m_nextpkt = NULL; 168130365Smlaier return (m); 169130365Smlaier} 170130365Smlaier 171130365Smlaierstatic __inline void 172130365Smlaier_removeq(class_queue_t *q, struct mbuf *m) 173130365Smlaier{ 174130365Smlaier struct mbuf *m0, *prev; 175130365Smlaier 176130365Smlaier m0 = qtail(q); 177130365Smlaier do { 178130365Smlaier prev = m0; 179130365Smlaier m0 = m0->m_nextpkt; 180130365Smlaier } while (m0 != m); 181130365Smlaier prev->m_nextpkt = m->m_nextpkt; 182130365Smlaier if (prev == m) 183130365Smlaier qtail(q) = NULL; 184130365Smlaier else if (qtail(q) == m) 185130365Smlaier qtail(q) = prev; 186130365Smlaier qlen(q)--; 187130365Smlaier} 188130365Smlaier 189130365Smlaierstatic __inline void 190130365Smlaier_flushq(class_queue_t *q) 191130365Smlaier{ 192130365Smlaier struct mbuf *m; 193130365Smlaier 194130365Smlaier while ((m = _getq(q)) != NULL) 195130365Smlaier m_freem(m); 196130365Smlaier} 197130365Smlaier 198130365Smlaier#endif /* __GNUC__ && !ALTQ_DEBUG */ 199130365Smlaier 200130365Smlaier#endif /* _KERNEL */ 201130365Smlaier 202130365Smlaier#ifdef __cplusplus 203130365Smlaier} 204130365Smlaier#endif 205130365Smlaier 206130365Smlaier#endif /* _ALTQ_ALTQ_CLASSQ_H_ */ 207