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 52298133Sloos#define Q_CODEL 0x04 53130365Smlaier 54130365Smlaier#ifdef _KERNEL 55130365Smlaier 56130365Smlaier/* 57130365Smlaier * Packet Queue structures and macros to manipulate them. 58130365Smlaier */ 59130365Smlaierstruct _class_queue_ { 60130365Smlaier struct mbuf *tail_; /* Tail of packet queue */ 61130365Smlaier int qlen_; /* Queue length (in number of packets) */ 62130365Smlaier int qlim_; /* Queue limit (in number of packets*) */ 63298133Sloos int qsize_; /* Queue size (in number of bytes*) */ 64130365Smlaier int qtype_; /* Queue type */ 65130365Smlaier}; 66130365Smlaier 67130365Smlaiertypedef struct _class_queue_ class_queue_t; 68130365Smlaier 69130365Smlaier#define qtype(q) (q)->qtype_ /* Get queue type */ 70130365Smlaier#define qlimit(q) (q)->qlim_ /* Max packets to be queued */ 71130365Smlaier#define qlen(q) (q)->qlen_ /* Current queue length. */ 72298133Sloos#define qsize(q) (q)->qsize_ /* Current queue size. */ 73130365Smlaier#define qtail(q) (q)->tail_ /* Tail of the queue */ 74130365Smlaier#define qhead(q) ((q)->tail_ ? (q)->tail_->m_nextpkt : NULL) 75130365Smlaier 76130365Smlaier#define qempty(q) ((q)->qlen_ == 0) /* Is the queue empty?? */ 77298133Sloos#define q_is_codel(q) ((q)->qtype_ == Q_CODEL) /* Is the queue a codel queue */ 78130365Smlaier#define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a red queue */ 79130365Smlaier#define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a rio queue */ 80130365Smlaier#define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO) 81130365Smlaier 82130365Smlaier#if !defined(__GNUC__) || defined(ALTQ_DEBUG) 83130365Smlaier 84130365Smlaierextern void _addq(class_queue_t *, struct mbuf *); 85130365Smlaierextern struct mbuf *_getq(class_queue_t *); 86130365Smlaierextern struct mbuf *_getq_tail(class_queue_t *); 87130365Smlaierextern struct mbuf *_getq_random(class_queue_t *); 88130365Smlaierextern void _removeq(class_queue_t *, struct mbuf *); 89130365Smlaierextern void _flushq(class_queue_t *); 90130365Smlaier 91130365Smlaier#else /* __GNUC__ && !ALTQ_DEBUG */ 92130365Smlaier/* 93130365Smlaier * inlined versions 94130365Smlaier */ 95130365Smlaierstatic __inline void 96130365Smlaier_addq(class_queue_t *q, struct mbuf *m) 97130365Smlaier{ 98130365Smlaier struct mbuf *m0; 99130365Smlaier 100130365Smlaier if ((m0 = qtail(q)) != NULL) 101130365Smlaier m->m_nextpkt = m0->m_nextpkt; 102130365Smlaier else 103130365Smlaier m0 = m; 104130365Smlaier m0->m_nextpkt = m; 105130365Smlaier qtail(q) = m; 106130365Smlaier qlen(q)++; 107298133Sloos qsize(q) += m_pktlen(m); 108130365Smlaier} 109130365Smlaier 110130365Smlaierstatic __inline struct mbuf * 111130365Smlaier_getq(class_queue_t *q) 112130365Smlaier{ 113130365Smlaier struct mbuf *m, *m0; 114130365Smlaier 115130365Smlaier if ((m = qtail(q)) == NULL) 116130365Smlaier return (NULL); 117130365Smlaier if ((m0 = m->m_nextpkt) != m) 118130365Smlaier m->m_nextpkt = m0->m_nextpkt; 119130365Smlaier else 120130365Smlaier qtail(q) = NULL; 121130365Smlaier qlen(q)--; 122298133Sloos qsize(q) -= m_pktlen(m0); 123130365Smlaier m0->m_nextpkt = NULL; 124130365Smlaier return (m0); 125130365Smlaier} 126130365Smlaier 127130365Smlaier/* drop a packet at the tail of the queue */ 128130365Smlaierstatic __inline struct mbuf * 129130365Smlaier_getq_tail(class_queue_t *q) 130130365Smlaier{ 131130365Smlaier struct mbuf *m, *m0, *prev; 132130365Smlaier 133130365Smlaier if ((m = m0 = qtail(q)) == NULL) 134130365Smlaier return NULL; 135130365Smlaier do { 136130365Smlaier prev = m0; 137130365Smlaier m0 = m0->m_nextpkt; 138130365Smlaier } while (m0 != m); 139130365Smlaier prev->m_nextpkt = m->m_nextpkt; 140130365Smlaier if (prev == m) 141130365Smlaier qtail(q) = NULL; 142130365Smlaier else 143130365Smlaier qtail(q) = prev; 144130365Smlaier qlen(q)--; 145130365Smlaier m->m_nextpkt = NULL; 146130365Smlaier return (m); 147130365Smlaier} 148130365Smlaier 149130365Smlaier/* randomly select a packet in the queue */ 150130365Smlaierstatic __inline struct mbuf * 151130365Smlaier_getq_random(class_queue_t *q) 152130365Smlaier{ 153130365Smlaier struct mbuf *m; 154130365Smlaier int i, n; 155130365Smlaier 156130365Smlaier if ((m = qtail(q)) == NULL) 157130365Smlaier return NULL; 158130365Smlaier if (m->m_nextpkt == m) 159130365Smlaier qtail(q) = NULL; 160130365Smlaier else { 161130365Smlaier struct mbuf *prev = NULL; 162130365Smlaier 163130365Smlaier n = random() % qlen(q) + 1; 164130365Smlaier for (i = 0; i < n; i++) { 165130365Smlaier prev = m; 166130365Smlaier m = m->m_nextpkt; 167130365Smlaier } 168130365Smlaier prev->m_nextpkt = m->m_nextpkt; 169130365Smlaier if (m == qtail(q)) 170130365Smlaier qtail(q) = prev; 171130365Smlaier } 172130365Smlaier qlen(q)--; 173130365Smlaier m->m_nextpkt = NULL; 174130365Smlaier return (m); 175130365Smlaier} 176130365Smlaier 177130365Smlaierstatic __inline void 178130365Smlaier_removeq(class_queue_t *q, struct mbuf *m) 179130365Smlaier{ 180130365Smlaier struct mbuf *m0, *prev; 181130365Smlaier 182130365Smlaier m0 = qtail(q); 183130365Smlaier do { 184130365Smlaier prev = m0; 185130365Smlaier m0 = m0->m_nextpkt; 186130365Smlaier } while (m0 != m); 187130365Smlaier prev->m_nextpkt = m->m_nextpkt; 188130365Smlaier if (prev == m) 189130365Smlaier qtail(q) = NULL; 190130365Smlaier else if (qtail(q) == m) 191130365Smlaier qtail(q) = prev; 192130365Smlaier qlen(q)--; 193130365Smlaier} 194130365Smlaier 195130365Smlaierstatic __inline void 196130365Smlaier_flushq(class_queue_t *q) 197130365Smlaier{ 198130365Smlaier struct mbuf *m; 199130365Smlaier 200130365Smlaier while ((m = _getq(q)) != NULL) 201130365Smlaier m_freem(m); 202130365Smlaier} 203130365Smlaier 204130365Smlaier#endif /* __GNUC__ && !ALTQ_DEBUG */ 205130365Smlaier 206130365Smlaier#endif /* _KERNEL */ 207130365Smlaier 208130365Smlaier#ifdef __cplusplus 209130365Smlaier} 210130365Smlaier#endif 211130365Smlaier 212130365Smlaier#endif /* _ALTQ_ALTQ_CLASSQ_H_ */ 213