1126385Smlaier/* $FreeBSD$ */ 2126385Smlaier/* $KAME: altq_classq.h,v 1.6 2003/01/07 07:33:38 kjc Exp $ */ 3126385Smlaier 4126385Smlaier/* 5126385Smlaier * Copyright (c) 1991-1997 Regents of the University of California. 6126385Smlaier * All rights reserved. 7126385Smlaier * 8126385Smlaier * Redistribution and use in source and binary forms, with or without 9126385Smlaier * modification, are permitted provided that the following conditions 10126385Smlaier * are met: 11126385Smlaier * 1. Redistributions of source code must retain the above copyright 12126385Smlaier * notice, this list of conditions and the following disclaimer. 13126385Smlaier * 2. Redistributions in binary form must reproduce the above copyright 14126385Smlaier * notice, this list of conditions and the following disclaimer in the 15126385Smlaier * documentation and/or other materials provided with the distribution. 16126385Smlaier * 4. Neither the name of the University nor of the Laboratory may be used 17126385Smlaier * to endorse or promote products derived from this software without 18126385Smlaier * specific prior written permission. 19126385Smlaier * 20126385Smlaier * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21126385Smlaier * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22126385Smlaier * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23126385Smlaier * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24126385Smlaier * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25126385Smlaier * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26126385Smlaier * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27126385Smlaier * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28126385Smlaier * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29126385Smlaier * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30126385Smlaier * SUCH DAMAGE. 31126385Smlaier */ 32126385Smlaier/* 33126385Smlaier * class queue definitions extracted from rm_class.h. 34126385Smlaier */ 35126385Smlaier#ifndef _ALTQ_ALTQ_CLASSQ_H_ 36126385Smlaier#define _ALTQ_ALTQ_CLASSQ_H_ 37126385Smlaier 38126385Smlaier#ifdef __cplusplus 39126385Smlaierextern "C" { 40126385Smlaier#endif 41126385Smlaier 42126385Smlaier/* 43126385Smlaier * Packet Queue types: RED or DROPHEAD. 44126385Smlaier */ 45126385Smlaier#define Q_DROPHEAD 0x00 46126385Smlaier#define Q_RED 0x01 47126385Smlaier#define Q_RIO 0x02 48126385Smlaier#define Q_DROPTAIL 0x03 49126385Smlaier 50126385Smlaier#ifdef _KERNEL 51126385Smlaier 52126385Smlaier/* 53126385Smlaier * Packet Queue structures and macros to manipulate them. 54126385Smlaier */ 55126385Smlaierstruct _class_queue_ { 56126385Smlaier struct mbuf *tail_; /* Tail of packet queue */ 57126385Smlaier int qlen_; /* Queue length (in number of packets) */ 58126385Smlaier int qlim_; /* Queue limit (in number of packets*) */ 59126385Smlaier int qtype_; /* Queue type */ 60126385Smlaier}; 61126385Smlaier 62126385Smlaiertypedef struct _class_queue_ class_queue_t; 63126385Smlaier 64126385Smlaier#define qtype(q) (q)->qtype_ /* Get queue type */ 65126385Smlaier#define qlimit(q) (q)->qlim_ /* Max packets to be queued */ 66126385Smlaier#define qlen(q) (q)->qlen_ /* Current queue length. */ 67126385Smlaier#define qtail(q) (q)->tail_ /* Tail of the queue */ 68126385Smlaier#define qhead(q) ((q)->tail_ ? (q)->tail_->m_nextpkt : NULL) 69126385Smlaier 70126385Smlaier#define qempty(q) ((q)->qlen_ == 0) /* Is the queue empty?? */ 71126385Smlaier#define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a red queue */ 72126385Smlaier#define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a rio queue */ 73126385Smlaier#define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO) 74126385Smlaier 75126385Smlaier#if !defined(__GNUC__) || defined(ALTQ_DEBUG) 76126385Smlaier 77126385Smlaierextern void _addq(class_queue_t *, struct mbuf *); 78126385Smlaierextern struct mbuf *_getq(class_queue_t *); 79126385Smlaierextern struct mbuf *_getq_tail(class_queue_t *); 80126385Smlaierextern struct mbuf *_getq_random(class_queue_t *); 81126385Smlaierextern void _removeq(class_queue_t *, struct mbuf *); 82126385Smlaierextern void _flushq(class_queue_t *); 83126385Smlaier 84126385Smlaier#else /* __GNUC__ && !ALTQ_DEBUG */ 85126385Smlaier/* 86126385Smlaier * inlined versions 87126385Smlaier */ 88126385Smlaierstatic __inline void 89126385Smlaier_addq(class_queue_t *q, struct mbuf *m) 90126385Smlaier{ 91126385Smlaier struct mbuf *m0; 92126385Smlaier 93126385Smlaier if ((m0 = qtail(q)) != NULL) 94126385Smlaier m->m_nextpkt = m0->m_nextpkt; 95126385Smlaier else 96126385Smlaier m0 = m; 97126385Smlaier m0->m_nextpkt = m; 98126385Smlaier qtail(q) = m; 99126385Smlaier qlen(q)++; 100126385Smlaier} 101126385Smlaier 102126385Smlaierstatic __inline struct mbuf * 103126385Smlaier_getq(class_queue_t *q) 104126385Smlaier{ 105126385Smlaier struct mbuf *m, *m0; 106126385Smlaier 107126385Smlaier if ((m = qtail(q)) == NULL) 108126385Smlaier return (NULL); 109126385Smlaier if ((m0 = m->m_nextpkt) != m) 110126385Smlaier m->m_nextpkt = m0->m_nextpkt; 111126385Smlaier else 112126385Smlaier qtail(q) = NULL; 113126385Smlaier qlen(q)--; 114126385Smlaier m0->m_nextpkt = NULL; 115126385Smlaier return (m0); 116126385Smlaier} 117126385Smlaier 118126385Smlaier/* drop a packet at the tail of the queue */ 119126385Smlaierstatic __inline struct mbuf * 120126385Smlaier_getq_tail(class_queue_t *q) 121126385Smlaier{ 122126385Smlaier struct mbuf *m, *m0, *prev; 123126385Smlaier 124126385Smlaier if ((m = m0 = qtail(q)) == NULL) 125126385Smlaier return NULL; 126126385Smlaier do { 127126385Smlaier prev = m0; 128126385Smlaier m0 = m0->m_nextpkt; 129126385Smlaier } while (m0 != m); 130126385Smlaier prev->m_nextpkt = m->m_nextpkt; 131126385Smlaier if (prev == m) 132126385Smlaier qtail(q) = NULL; 133126385Smlaier else 134126385Smlaier qtail(q) = prev; 135126385Smlaier qlen(q)--; 136126385Smlaier m->m_nextpkt = NULL; 137126385Smlaier return (m); 138126385Smlaier} 139126385Smlaier 140126385Smlaier/* randomly select a packet in the queue */ 141126385Smlaierstatic __inline struct mbuf * 142126385Smlaier_getq_random(class_queue_t *q) 143126385Smlaier{ 144126385Smlaier struct mbuf *m; 145126385Smlaier int i, n; 146126385Smlaier 147126385Smlaier if ((m = qtail(q)) == NULL) 148126385Smlaier return NULL; 149126385Smlaier if (m->m_nextpkt == m) 150126385Smlaier qtail(q) = NULL; 151126385Smlaier else { 152126385Smlaier struct mbuf *prev = NULL; 153126385Smlaier 154126385Smlaier n = random() % qlen(q) + 1; 155126385Smlaier for (i = 0; i < n; i++) { 156126385Smlaier prev = m; 157126385Smlaier m = m->m_nextpkt; 158126385Smlaier } 159126385Smlaier prev->m_nextpkt = m->m_nextpkt; 160126385Smlaier if (m == qtail(q)) 161126385Smlaier qtail(q) = prev; 162126385Smlaier } 163126385Smlaier qlen(q)--; 164126385Smlaier m->m_nextpkt = NULL; 165126385Smlaier return (m); 166126385Smlaier} 167126385Smlaier 168126385Smlaierstatic __inline void 169126385Smlaier_removeq(class_queue_t *q, struct mbuf *m) 170126385Smlaier{ 171126385Smlaier struct mbuf *m0, *prev; 172126385Smlaier 173126385Smlaier m0 = qtail(q); 174126385Smlaier do { 175126385Smlaier prev = m0; 176126385Smlaier m0 = m0->m_nextpkt; 177126385Smlaier } while (m0 != m); 178126385Smlaier prev->m_nextpkt = m->m_nextpkt; 179126385Smlaier if (prev == m) 180126385Smlaier qtail(q) = NULL; 181126385Smlaier else if (qtail(q) == m) 182126385Smlaier qtail(q) = prev; 183126385Smlaier qlen(q)--; 184126385Smlaier} 185126385Smlaier 186126385Smlaierstatic __inline void 187126385Smlaier_flushq(class_queue_t *q) 188126385Smlaier{ 189126385Smlaier struct mbuf *m; 190126385Smlaier 191126385Smlaier while ((m = _getq(q)) != NULL) 192126385Smlaier m_freem(m); 193126385Smlaier} 194126385Smlaier 195126385Smlaier#endif /* __GNUC__ && !ALTQ_DEBUG */ 196126385Smlaier 197126385Smlaier#endif /* _KERNEL */ 198126385Smlaier 199126385Smlaier#ifdef __cplusplus 200126385Smlaier} 201126385Smlaier#endif 202126385Smlaier 203126385Smlaier#endif /* _ALTQ_ALTQ_CLASSQ_H_ */ 204