14d723e5aSJoerg Sonnenberger /* $KAME: altq_classq.h,v 1.6 2003/01/07 07:33:38 kjc Exp $ */
2cddfb7bbSMatthew Dillon /* $DragonFly: src/sys/net/altq/altq_classq.h,v 1.2 2006/09/03 18:52:29 dillon Exp $ */
34d723e5aSJoerg Sonnenberger
44d723e5aSJoerg Sonnenberger /*
54d723e5aSJoerg Sonnenberger * Copyright (c) 1991-1997 Regents of the University of California.
64d723e5aSJoerg Sonnenberger * All rights reserved.
74d723e5aSJoerg Sonnenberger *
84d723e5aSJoerg Sonnenberger * Redistribution and use in source and binary forms, with or without
94d723e5aSJoerg Sonnenberger * modification, are permitted provided that the following conditions
104d723e5aSJoerg Sonnenberger * are met:
114d723e5aSJoerg Sonnenberger * 1. Redistributions of source code must retain the above copyright
124d723e5aSJoerg Sonnenberger * notice, this list of conditions and the following disclaimer.
134d723e5aSJoerg Sonnenberger * 2. Redistributions in binary form must reproduce the above copyright
144d723e5aSJoerg Sonnenberger * notice, this list of conditions and the following disclaimer in the
154d723e5aSJoerg Sonnenberger * documentation and/or other materials provided with the distribution.
164d723e5aSJoerg Sonnenberger * 3. All advertising materials mentioning features or use of this software
174d723e5aSJoerg Sonnenberger * must display the following acknowledgement:
184d723e5aSJoerg Sonnenberger * This product includes software developed by the Network Research
194d723e5aSJoerg Sonnenberger * Group at Lawrence Berkeley Laboratory.
204d723e5aSJoerg Sonnenberger * 4. Neither the name of the University nor of the Laboratory may be used
214d723e5aSJoerg Sonnenberger * to endorse or promote products derived from this software without
224d723e5aSJoerg Sonnenberger * specific prior written permission.
234d723e5aSJoerg Sonnenberger *
244d723e5aSJoerg Sonnenberger * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
254d723e5aSJoerg Sonnenberger * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
264d723e5aSJoerg Sonnenberger * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
274d723e5aSJoerg Sonnenberger * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
284d723e5aSJoerg Sonnenberger * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
294d723e5aSJoerg Sonnenberger * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
304d723e5aSJoerg Sonnenberger * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
314d723e5aSJoerg Sonnenberger * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
324d723e5aSJoerg Sonnenberger * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
334d723e5aSJoerg Sonnenberger * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
344d723e5aSJoerg Sonnenberger * SUCH DAMAGE.
354d723e5aSJoerg Sonnenberger */
364d723e5aSJoerg Sonnenberger /*
374d723e5aSJoerg Sonnenberger * class queue definitions extracted from rm_class.h.
384d723e5aSJoerg Sonnenberger */
394d723e5aSJoerg Sonnenberger #ifndef _ALTQ_ALTQ_CLASSQ_H_
404d723e5aSJoerg Sonnenberger #define _ALTQ_ALTQ_CLASSQ_H_
414d723e5aSJoerg Sonnenberger
42*e7d68516SSepherosa Ziehau #include <net/altq/if_classq.h>
43*e7d68516SSepherosa Ziehau
444d723e5aSJoerg Sonnenberger /*
454d723e5aSJoerg Sonnenberger * Packet Queue types: RED or DROPHEAD.
464d723e5aSJoerg Sonnenberger */
474d723e5aSJoerg Sonnenberger #define Q_DROPHEAD 0x00
484d723e5aSJoerg Sonnenberger #define Q_RED 0x01
494d723e5aSJoerg Sonnenberger #define Q_RIO 0x02
504d723e5aSJoerg Sonnenberger #define Q_DROPTAIL 0x03
514d723e5aSJoerg Sonnenberger
524d723e5aSJoerg Sonnenberger #ifdef _KERNEL
534d723e5aSJoerg Sonnenberger
544d723e5aSJoerg Sonnenberger /*
554d723e5aSJoerg Sonnenberger * Packet Queue structures and macros to manipulate them.
564d723e5aSJoerg Sonnenberger */
574d723e5aSJoerg Sonnenberger struct _class_queue_ {
58*e7d68516SSepherosa Ziehau struct if_classq que_;
594d723e5aSJoerg Sonnenberger int qlen_; /* Queue length (in number of packets) */
604d723e5aSJoerg Sonnenberger int qlim_; /* Queue limit (in number of packets*) */
614d723e5aSJoerg Sonnenberger int qtype_; /* Queue type */
624d723e5aSJoerg Sonnenberger };
634d723e5aSJoerg Sonnenberger
644d723e5aSJoerg Sonnenberger typedef struct _class_queue_ class_queue_t;
654d723e5aSJoerg Sonnenberger
664d723e5aSJoerg Sonnenberger #define qtype(q) (q)->qtype_ /* Get queue type */
674d723e5aSJoerg Sonnenberger #define qlimit(q) (q)->qlim_ /* Max packets to be queued */
684d723e5aSJoerg Sonnenberger #define qlen(q) (q)->qlen_ /* Current queue length. */
69*e7d68516SSepherosa Ziehau #define qtail(q) classq_tail(&(q)->que_) /* Tail of the queue */
70*e7d68516SSepherosa Ziehau #define qhead(q) classq_head(&(q)->que_)
714d723e5aSJoerg Sonnenberger
724d723e5aSJoerg Sonnenberger #define qempty(q) ((q)->qlen_ == 0) /* Is the queue empty?? */
734d723e5aSJoerg Sonnenberger #define q_is_red(q) ((q)->qtype_ == Q_RED) /* Is the queue a red queue */
744d723e5aSJoerg Sonnenberger #define q_is_rio(q) ((q)->qtype_ == Q_RIO) /* Is the queue a rio queue */
754d723e5aSJoerg Sonnenberger #define q_is_red_or_rio(q) ((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO)
764d723e5aSJoerg Sonnenberger
774d723e5aSJoerg Sonnenberger static __inline void
_addq(class_queue_t * q,struct mbuf * m)784d723e5aSJoerg Sonnenberger _addq(class_queue_t *q, struct mbuf *m)
794d723e5aSJoerg Sonnenberger {
80*e7d68516SSepherosa Ziehau classq_add(&q->que_, m);
814d723e5aSJoerg Sonnenberger qlen(q)++;
824d723e5aSJoerg Sonnenberger }
834d723e5aSJoerg Sonnenberger
844d723e5aSJoerg Sonnenberger static __inline struct mbuf *
_getq(class_queue_t * q)854d723e5aSJoerg Sonnenberger _getq(class_queue_t *q)
864d723e5aSJoerg Sonnenberger {
87*e7d68516SSepherosa Ziehau struct mbuf *m;
884d723e5aSJoerg Sonnenberger
89*e7d68516SSepherosa Ziehau m = classq_get(&q->que_);
90*e7d68516SSepherosa Ziehau if (m != NULL)
914d723e5aSJoerg Sonnenberger qlen(q)--;
92*e7d68516SSepherosa Ziehau return (m);
934d723e5aSJoerg Sonnenberger }
944d723e5aSJoerg Sonnenberger
954d723e5aSJoerg Sonnenberger /* drop a packet at the tail of the queue */
964d723e5aSJoerg Sonnenberger static __inline struct mbuf *
_getq_tail(class_queue_t * q)974d723e5aSJoerg Sonnenberger _getq_tail(class_queue_t *q)
984d723e5aSJoerg Sonnenberger {
994d723e5aSJoerg Sonnenberger struct mbuf *m, *m0, *prev;
1004d723e5aSJoerg Sonnenberger
1014d723e5aSJoerg Sonnenberger if ((m = m0 = qtail(q)) == NULL)
1024d723e5aSJoerg Sonnenberger return NULL;
1034d723e5aSJoerg Sonnenberger do {
1044d723e5aSJoerg Sonnenberger prev = m0;
1054d723e5aSJoerg Sonnenberger m0 = m0->m_nextpkt;
1064d723e5aSJoerg Sonnenberger } while (m0 != m);
1074d723e5aSJoerg Sonnenberger prev->m_nextpkt = m->m_nextpkt;
1084d723e5aSJoerg Sonnenberger if (prev == m)
1094d723e5aSJoerg Sonnenberger qtail(q) = NULL;
1104d723e5aSJoerg Sonnenberger else
1114d723e5aSJoerg Sonnenberger qtail(q) = prev;
1124d723e5aSJoerg Sonnenberger qlen(q)--;
1134d723e5aSJoerg Sonnenberger m->m_nextpkt = NULL;
1144d723e5aSJoerg Sonnenberger return (m);
1154d723e5aSJoerg Sonnenberger }
1164d723e5aSJoerg Sonnenberger
1174d723e5aSJoerg Sonnenberger /* randomly select a packet in the queue */
1184d723e5aSJoerg Sonnenberger static __inline struct mbuf *
_getq_random(class_queue_t * q)1194d723e5aSJoerg Sonnenberger _getq_random(class_queue_t *q)
1204d723e5aSJoerg Sonnenberger {
1214d723e5aSJoerg Sonnenberger struct mbuf *m;
1224d723e5aSJoerg Sonnenberger int i, n;
1234d723e5aSJoerg Sonnenberger
1244d723e5aSJoerg Sonnenberger if ((m = qtail(q)) == NULL)
1254d723e5aSJoerg Sonnenberger return NULL;
1264d723e5aSJoerg Sonnenberger if (m->m_nextpkt == m)
1274d723e5aSJoerg Sonnenberger qtail(q) = NULL;
1284d723e5aSJoerg Sonnenberger else {
1294d723e5aSJoerg Sonnenberger struct mbuf *prev = NULL;
1304d723e5aSJoerg Sonnenberger
131cddfb7bbSMatthew Dillon n = krandom() % qlen(q) + 1;
1324d723e5aSJoerg Sonnenberger for (i = 0; i < n; i++) {
1334d723e5aSJoerg Sonnenberger prev = m;
1344d723e5aSJoerg Sonnenberger m = m->m_nextpkt;
1354d723e5aSJoerg Sonnenberger }
1364d723e5aSJoerg Sonnenberger prev->m_nextpkt = m->m_nextpkt;
1374d723e5aSJoerg Sonnenberger if (m == qtail(q))
1384d723e5aSJoerg Sonnenberger qtail(q) = prev;
1394d723e5aSJoerg Sonnenberger }
1404d723e5aSJoerg Sonnenberger qlen(q)--;
1414d723e5aSJoerg Sonnenberger m->m_nextpkt = NULL;
1424d723e5aSJoerg Sonnenberger return (m);
1434d723e5aSJoerg Sonnenberger }
1444d723e5aSJoerg Sonnenberger
1454d723e5aSJoerg Sonnenberger static __inline void
_removeq(class_queue_t * q,struct mbuf * m)1464d723e5aSJoerg Sonnenberger _removeq(class_queue_t *q, struct mbuf *m)
1474d723e5aSJoerg Sonnenberger {
1484d723e5aSJoerg Sonnenberger struct mbuf *m0, *prev;
1494d723e5aSJoerg Sonnenberger
1504d723e5aSJoerg Sonnenberger m0 = qtail(q);
1514d723e5aSJoerg Sonnenberger do {
1524d723e5aSJoerg Sonnenberger prev = m0;
1534d723e5aSJoerg Sonnenberger m0 = m0->m_nextpkt;
1544d723e5aSJoerg Sonnenberger } while (m0 != m);
1554d723e5aSJoerg Sonnenberger prev->m_nextpkt = m->m_nextpkt;
1564d723e5aSJoerg Sonnenberger if (prev == m)
1574d723e5aSJoerg Sonnenberger qtail(q) = NULL;
1584d723e5aSJoerg Sonnenberger else if (qtail(q) == m)
1594d723e5aSJoerg Sonnenberger qtail(q) = prev;
1604d723e5aSJoerg Sonnenberger qlen(q)--;
1614d723e5aSJoerg Sonnenberger }
1624d723e5aSJoerg Sonnenberger
1634d723e5aSJoerg Sonnenberger static __inline void
_flushq(class_queue_t * q)1644d723e5aSJoerg Sonnenberger _flushq(class_queue_t *q)
1654d723e5aSJoerg Sonnenberger {
1664d723e5aSJoerg Sonnenberger struct mbuf *m;
1674d723e5aSJoerg Sonnenberger
1684d723e5aSJoerg Sonnenberger while ((m = _getq(q)) != NULL)
1694d723e5aSJoerg Sonnenberger m_freem(m);
1704d723e5aSJoerg Sonnenberger }
1714d723e5aSJoerg Sonnenberger
1724d723e5aSJoerg Sonnenberger #endif /* _KERNEL */
1734d723e5aSJoerg Sonnenberger
1744d723e5aSJoerg Sonnenberger #endif /* _ALTQ_ALTQ_CLASSQ_H_ */
175