1772e66a6SGleb Smirnoff /* $KAME: altq_classq.h,v 1.6 2003/01/07 07:33:38 kjc Exp $ */ 2772e66a6SGleb Smirnoff 3772e66a6SGleb Smirnoff /* 4772e66a6SGleb Smirnoff * Copyright (c) 1991-1997 Regents of the University of California. 5772e66a6SGleb Smirnoff * All rights reserved. 6772e66a6SGleb Smirnoff * 7772e66a6SGleb Smirnoff * Redistribution and use in source and binary forms, with or without 8772e66a6SGleb Smirnoff * modification, are permitted provided that the following conditions 9772e66a6SGleb Smirnoff * are met: 10772e66a6SGleb Smirnoff * 1. Redistributions of source code must retain the above copyright 11772e66a6SGleb Smirnoff * notice, this list of conditions and the following disclaimer. 12772e66a6SGleb Smirnoff * 2. Redistributions in binary form must reproduce the above copyright 13772e66a6SGleb Smirnoff * notice, this list of conditions and the following disclaimer in the 14772e66a6SGleb Smirnoff * documentation and/or other materials provided with the distribution. 15772e66a6SGleb Smirnoff * 3. All advertising materials mentioning features or use of this software 16772e66a6SGleb Smirnoff * must display the following acknowledgement: 17772e66a6SGleb Smirnoff * This product includes software developed by the Network Research 18772e66a6SGleb Smirnoff * Group at Lawrence Berkeley Laboratory. 19772e66a6SGleb Smirnoff * 4. Neither the name of the University nor of the Laboratory may be used 20772e66a6SGleb Smirnoff * to endorse or promote products derived from this software without 21772e66a6SGleb Smirnoff * specific prior written permission. 22772e66a6SGleb Smirnoff * 23772e66a6SGleb Smirnoff * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24772e66a6SGleb Smirnoff * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25772e66a6SGleb Smirnoff * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26772e66a6SGleb Smirnoff * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27772e66a6SGleb Smirnoff * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28772e66a6SGleb Smirnoff * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29772e66a6SGleb Smirnoff * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30772e66a6SGleb Smirnoff * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31772e66a6SGleb Smirnoff * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32772e66a6SGleb Smirnoff * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33772e66a6SGleb Smirnoff * SUCH DAMAGE. 34772e66a6SGleb Smirnoff */ 35772e66a6SGleb Smirnoff /* 36772e66a6SGleb Smirnoff * class queue definitions extracted from rm_class.h. 37772e66a6SGleb Smirnoff */ 38772e66a6SGleb Smirnoff #ifndef _ALTQ_ALTQ_CLASSQ_H_ 39772e66a6SGleb Smirnoff #define _ALTQ_ALTQ_CLASSQ_H_ 40772e66a6SGleb Smirnoff 41772e66a6SGleb Smirnoff #ifdef __cplusplus 42772e66a6SGleb Smirnoff extern "C" { 43772e66a6SGleb Smirnoff #endif 44772e66a6SGleb Smirnoff 45772e66a6SGleb Smirnoff /* 46772e66a6SGleb Smirnoff * Packet Queue types: RED or DROPHEAD. 47772e66a6SGleb Smirnoff */ 48772e66a6SGleb Smirnoff #define Q_DROPHEAD 0x00 49772e66a6SGleb Smirnoff #define Q_RED 0x01 50772e66a6SGleb Smirnoff #define Q_RIO 0x02 51772e66a6SGleb Smirnoff #define Q_DROPTAIL 0x03 52772e66a6SGleb Smirnoff 53772e66a6SGleb Smirnoff #ifdef _KERNEL 54772e66a6SGleb Smirnoff 55772e66a6SGleb Smirnoff /* 56772e66a6SGleb Smirnoff * Packet Queue structures and macros to manipulate them. 57772e66a6SGleb Smirnoff */ 58772e66a6SGleb Smirnoff struct _class_queue_ { 59772e66a6SGleb Smirnoff struct mbuf *tail_; /* Tail of packet queue */ 60772e66a6SGleb Smirnoff int qlen_; /* Queue length (in number of packets) */ 61772e66a6SGleb Smirnoff int qlim_; /* Queue limit (in number of packets*) */ 62772e66a6SGleb Smirnoff int qtype_; /* Queue type */ 63772e66a6SGleb Smirnoff }; 64772e66a6SGleb Smirnoff 65772e66a6SGleb Smirnoff typedef struct _class_queue_ class_queue_t; 66772e66a6SGleb Smirnoff 67772e66a6SGleb Smirnoff #define qtype(q) (q)->qtype_ /* Get queue type */ 68772e66a6SGleb Smirnoff #define qlimit(q) (q)->qlim_ /* Max packets to be queued */ 69772e66a6SGleb Smirnoff #define qlen(q) (q)->qlen_ /* Current queue length. */ 70772e66a6SGleb Smirnoff #define qtail(q) (q)->tail_ /* Tail of the queue */ 71772e66a6SGleb Smirnoff #define qhead(q) ((q)->tail_ ? (q)->tail_->m_nextpkt : NULL) 72772e66a6SGleb Smirnoff 73772e66a6SGleb Smirnoff #define qempty(q) ((q)->qlen_ == 0) /* Is the queue empty?? */ 74772e66a6SGleb Smirnoff #define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a red queue */ 75772e66a6SGleb Smirnoff #define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a rio queue */ 76772e66a6SGleb Smirnoff #define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO) 77772e66a6SGleb Smirnoff 78772e66a6SGleb Smirnoff #if !defined(__GNUC__) || defined(ALTQ_DEBUG) 79772e66a6SGleb Smirnoff 80772e66a6SGleb Smirnoff extern void _addq(class_queue_t *, struct mbuf *); 81772e66a6SGleb Smirnoff extern struct mbuf *_getq(class_queue_t *); 82772e66a6SGleb Smirnoff extern struct mbuf *_getq_tail(class_queue_t *); 83772e66a6SGleb Smirnoff extern struct mbuf *_getq_random(class_queue_t *); 84772e66a6SGleb Smirnoff extern void _removeq(class_queue_t *, struct mbuf *); 85772e66a6SGleb Smirnoff extern void _flushq(class_queue_t *); 86772e66a6SGleb Smirnoff 87772e66a6SGleb Smirnoff #else /* __GNUC__ && !ALTQ_DEBUG */ 88772e66a6SGleb Smirnoff /* 89772e66a6SGleb Smirnoff * inlined versions 90772e66a6SGleb Smirnoff */ 91772e66a6SGleb Smirnoff static __inline void 92772e66a6SGleb Smirnoff _addq(class_queue_t *q, struct mbuf *m) 93772e66a6SGleb Smirnoff { 94772e66a6SGleb Smirnoff struct mbuf *m0; 95772e66a6SGleb Smirnoff 96772e66a6SGleb Smirnoff if ((m0 = qtail(q)) != NULL) 97772e66a6SGleb Smirnoff m->m_nextpkt = m0->m_nextpkt; 98772e66a6SGleb Smirnoff else 99772e66a6SGleb Smirnoff m0 = m; 100772e66a6SGleb Smirnoff m0->m_nextpkt = m; 101772e66a6SGleb Smirnoff qtail(q) = m; 102772e66a6SGleb Smirnoff qlen(q)++; 103772e66a6SGleb Smirnoff } 104772e66a6SGleb Smirnoff 105772e66a6SGleb Smirnoff static __inline struct mbuf * 106772e66a6SGleb Smirnoff _getq(class_queue_t *q) 107772e66a6SGleb Smirnoff { 108772e66a6SGleb Smirnoff struct mbuf *m, *m0; 109772e66a6SGleb Smirnoff 110772e66a6SGleb Smirnoff if ((m = qtail(q)) == NULL) 111772e66a6SGleb Smirnoff return (NULL); 112772e66a6SGleb Smirnoff if ((m0 = m->m_nextpkt) != m) 113772e66a6SGleb Smirnoff m->m_nextpkt = m0->m_nextpkt; 114772e66a6SGleb Smirnoff else 115772e66a6SGleb Smirnoff qtail(q) = NULL; 116772e66a6SGleb Smirnoff qlen(q)--; 117772e66a6SGleb Smirnoff m0->m_nextpkt = NULL; 118772e66a6SGleb Smirnoff return (m0); 119772e66a6SGleb Smirnoff } 120772e66a6SGleb Smirnoff 121772e66a6SGleb Smirnoff /* drop a packet at the tail of the queue */ 122772e66a6SGleb Smirnoff static __inline struct mbuf * 123772e66a6SGleb Smirnoff _getq_tail(class_queue_t *q) 124772e66a6SGleb Smirnoff { 125772e66a6SGleb Smirnoff struct mbuf *m, *m0, *prev; 126772e66a6SGleb Smirnoff 127772e66a6SGleb Smirnoff if ((m = m0 = qtail(q)) == NULL) 128772e66a6SGleb Smirnoff return NULL; 129772e66a6SGleb Smirnoff do { 130772e66a6SGleb Smirnoff prev = m0; 131772e66a6SGleb Smirnoff m0 = m0->m_nextpkt; 132772e66a6SGleb Smirnoff } while (m0 != m); 133772e66a6SGleb Smirnoff prev->m_nextpkt = m->m_nextpkt; 134772e66a6SGleb Smirnoff if (prev == m) 135772e66a6SGleb Smirnoff qtail(q) = NULL; 136772e66a6SGleb Smirnoff else 137772e66a6SGleb Smirnoff qtail(q) = prev; 138772e66a6SGleb Smirnoff qlen(q)--; 139772e66a6SGleb Smirnoff m->m_nextpkt = NULL; 140772e66a6SGleb Smirnoff return (m); 141772e66a6SGleb Smirnoff } 142772e66a6SGleb Smirnoff 143772e66a6SGleb Smirnoff /* randomly select a packet in the queue */ 144772e66a6SGleb Smirnoff static __inline struct mbuf * 145772e66a6SGleb Smirnoff _getq_random(class_queue_t *q) 146772e66a6SGleb Smirnoff { 147772e66a6SGleb Smirnoff struct mbuf *m; 148772e66a6SGleb Smirnoff int i, n; 149772e66a6SGleb Smirnoff 150772e66a6SGleb Smirnoff if ((m = qtail(q)) == NULL) 151772e66a6SGleb Smirnoff return NULL; 152772e66a6SGleb Smirnoff if (m->m_nextpkt == m) 153772e66a6SGleb Smirnoff qtail(q) = NULL; 154772e66a6SGleb Smirnoff else { 155772e66a6SGleb Smirnoff struct mbuf *prev = NULL; 156772e66a6SGleb Smirnoff 157772e66a6SGleb Smirnoff n = random() % qlen(q) + 1; 158772e66a6SGleb Smirnoff for (i = 0; i < n; i++) { 159772e66a6SGleb Smirnoff prev = m; 160772e66a6SGleb Smirnoff m = m->m_nextpkt; 161772e66a6SGleb Smirnoff } 162772e66a6SGleb Smirnoff prev->m_nextpkt = m->m_nextpkt; 163772e66a6SGleb Smirnoff if (m == qtail(q)) 164772e66a6SGleb Smirnoff qtail(q) = prev; 165772e66a6SGleb Smirnoff } 166772e66a6SGleb Smirnoff qlen(q)--; 167772e66a6SGleb Smirnoff m->m_nextpkt = NULL; 168772e66a6SGleb Smirnoff return (m); 169772e66a6SGleb Smirnoff } 170772e66a6SGleb Smirnoff 171772e66a6SGleb Smirnoff static __inline void 172772e66a6SGleb Smirnoff _removeq(class_queue_t *q, struct mbuf *m) 173772e66a6SGleb Smirnoff { 174772e66a6SGleb Smirnoff struct mbuf *m0, *prev; 175772e66a6SGleb Smirnoff 176772e66a6SGleb Smirnoff m0 = qtail(q); 177772e66a6SGleb Smirnoff do { 178772e66a6SGleb Smirnoff prev = m0; 179772e66a6SGleb Smirnoff m0 = m0->m_nextpkt; 180772e66a6SGleb Smirnoff } while (m0 != m); 181772e66a6SGleb Smirnoff prev->m_nextpkt = m->m_nextpkt; 182772e66a6SGleb Smirnoff if (prev == m) 183772e66a6SGleb Smirnoff qtail(q) = NULL; 184772e66a6SGleb Smirnoff else if (qtail(q) == m) 185772e66a6SGleb Smirnoff qtail(q) = prev; 186772e66a6SGleb Smirnoff qlen(q)--; 187772e66a6SGleb Smirnoff } 188772e66a6SGleb Smirnoff 189772e66a6SGleb Smirnoff static __inline void 190772e66a6SGleb Smirnoff _flushq(class_queue_t *q) 191772e66a6SGleb Smirnoff { 192772e66a6SGleb Smirnoff struct mbuf *m; 193772e66a6SGleb Smirnoff 194772e66a6SGleb Smirnoff while ((m = _getq(q)) != NULL) 195772e66a6SGleb Smirnoff m_freem(m); 196772e66a6SGleb Smirnoff } 197772e66a6SGleb Smirnoff 198772e66a6SGleb Smirnoff #endif /* __GNUC__ && !ALTQ_DEBUG */ 199772e66a6SGleb Smirnoff 200772e66a6SGleb Smirnoff #endif /* _KERNEL */ 201772e66a6SGleb Smirnoff 202772e66a6SGleb Smirnoff #ifdef __cplusplus 203772e66a6SGleb Smirnoff } 204772e66a6SGleb Smirnoff #endif 205772e66a6SGleb Smirnoff 206772e66a6SGleb Smirnoff #endif /* _ALTQ_ALTQ_CLASSQ_H_ */ 207