xref: /dragonfly/sys/net/altq/altq_rmclass.h (revision ef3829f0)
1 /*	$KAME: altq_rmclass.h,v 1.10 2003/08/20 23:30:23 itojun Exp $	*/
2 /*	$DragonFly: src/sys/net/altq/altq_rmclass.h,v 1.2 2006/12/22 23:44:55 swildner Exp $ */
3 
4 /*
5  * Copyright (c) 1991-1997 Regents of the University of California.
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
15  *    documentation and/or other materials provided with the distribution.
16  * 3. All advertising materials mentioning features or use of this software
17  *    must display the following acknowledgement:
18  *	This product includes software developed by the Network Research
19  *	Group at Lawrence Berkeley Laboratory.
20  * 4. Neither the name of the University nor of the Laboratory may be used
21  *    to endorse or promote products derived from this software without
22  *    specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34  * SUCH DAMAGE.
35  */
36 
37 #ifndef _ALTQ_ALTQ_RMCLASS_H_
38 #define	_ALTQ_ALTQ_RMCLASS_H_
39 
40 #include <net/altq/altq_classq.h>
41 
42 /* #pragma ident "@(#)rm_class.h  1.20     97/10/23 SMI" */
43 
44 #define	RM_MAXPRIO	8	/* Max priority */
45 
46 #ifdef _KERNEL
47 
48 typedef struct rm_ifdat		rm_ifdat_t;
49 typedef struct rm_class		rm_class_t;
50 
51 struct red;
52 
53 /*
54  * Macros for dealing with time values.  We assume all times are
55  * 'timevals'.  `microtime' is used to get the best available clock
56  * resolution.  If `microtime' *doesn't* return a value that's about
57  * ten times smaller than the average packet time on the fastest
58  * link that will use these routines, a slightly different clock
59  * scheme than this one should be used.
60  * (Bias due to truncation error in this scheme will overestimate utilization
61  * and discriminate against high bandwidth classes.  To remove this bias an
62  * integrator needs to be added.  The simplest integrator uses a history of
63  * 10 * avg.packet.time / min.tick.time packet completion entries.  This is
64  * straight forward to add but we don't want to pay the extra memory
65  * traffic to maintain it if it's not necessary (occasionally a vendor
66  * accidentally builds a workstation with a decent clock - e.g., Sun & HP).)
67  */
68 
69 #define	RM_GETTIME(now) microtime(&now)
70 
71 #define	TV_LT(a, b) (((a)->tv_sec < (b)->tv_sec) ||  \
72 	(((a)->tv_usec < (b)->tv_usec) && ((a)->tv_sec <= (b)->tv_sec)))
73 
74 #define	TV_DELTA(a, b, delta) { \
75 	register int	xxs;	\
76 							\
77 	delta = (a)->tv_usec - (b)->tv_usec; \
78 	if ((xxs = (a)->tv_sec - (b)->tv_sec)) { \
79 		switch (xxs) { \
80 		default: \
81 			/* if (xxs < 0) \
82 				kprintf("rm_class: bogus time values\n"); */ \
83 			delta = 0; \
84 			/* fall through */ \
85 		case 2: \
86 			delta += 1000000; \
87 			/* fall through */ \
88 		case 1: \
89 			delta += 1000000; \
90 			break; \
91 		} \
92 	} \
93 }
94 
95 #define	TV_ADD_DELTA(a, delta, res) { \
96 	register int xxus = (a)->tv_usec + (delta); \
97 	\
98 	(res)->tv_sec = (a)->tv_sec; \
99 	while (xxus >= 1000000) { \
100 		++((res)->tv_sec); \
101 		xxus -= 1000000; \
102 	} \
103 	(res)->tv_usec = xxus; \
104 }
105 
106 #define	RM_TIMEOUT	2	/* 1 Clock tick. */
107 
108 #if 1
109 #define	RM_MAXQUEUED	1	/* this isn't used in ALTQ/CBQ */
110 #else
111 #define	RM_MAXQUEUED	16	/* Max number of packets downstream of CBQ */
112 #endif
113 #define	RM_MAXQUEUE	64	/* Max queue length */
114 #define	RM_FILTER_GAIN	5	/* log2 of gain, e.g., 5 => 31/32 */
115 #define	RM_POWER	(1 << RM_FILTER_GAIN)
116 #define	RM_MAXDEPTH	32
117 #define	RM_NS_PER_SEC	(1000000000)
118 
119 typedef struct _rm_class_stats_ {
120 	u_int		handle;
121 	u_int		depth;
122 
123 	struct pktcntr	xmit_cnt;	/* packets sent in this class */
124 	struct pktcntr	drop_cnt;	/* dropped packets */
125 	u_int		over;		/* # times went over limit */
126 	u_int		borrows;	/* # times tried to borrow */
127 	u_int		overactions;	/* # times invoked overlimit action */
128 	u_int		delays;		/* # times invoked delay actions */
129 } rm_class_stats_t;
130 
131 /*
132  * CBQ Class state structure
133  */
134 struct rm_class {
135 	class_queue_t	*q_;		/* Queue of packets */
136 	rm_ifdat_t	*ifdat_;
137 	int		pri_;		/* Class priority. */
138 	int		depth_;		/* Class depth */
139 	u_int		ns_per_byte_;	/* NanoSeconds per byte. */
140 	u_int		maxrate_;	/* Bytes per second for this class. */
141 	u_int		allotment_;	/* Fraction of link bandwidth. */
142 	u_int		w_allotment_;	/* Weighted allotment for WRR */
143 	int		bytes_alloc_;	/* Allocation for round of WRR */
144 
145 	int		avgidle_;
146 	int		maxidle_;
147 	int		minidle_;
148 	int		offtime_;
149 	int		sleeping_;	/* != 0 if delaying */
150 	int		qthresh_;	/* Queue threshold for formal link sharing */
151 	int		leaf_;		/* Note whether leaf class or not.*/
152 
153 	rm_class_t	*children_;	/* Children of this class */
154 	rm_class_t	*next_;		/* Next pointer, used if child */
155 
156 	rm_class_t	*peer_;		/* Peer class */
157 	rm_class_t	*borrow_;	/* Borrow class */
158 	rm_class_t	*parent_;	/* Parent class */
159 
160 	void	(*overlimit)(struct rm_class *, struct rm_class *);
161 	void	(*drop)(struct rm_class *);       /* Class drop action. */
162 
163 	struct red	*red_;		/* RED state pointer */
164 	struct altq_pktattr *pktattr_;	/* saved hdr used by RED/ECN */
165 	int		flags_;
166 
167 	int		last_pkttime_;	/* saved pkt_time */
168 	struct timeval	undertime_;	/* time can next send */
169 	struct timeval	last_;		/* time last packet sent */
170 	struct timeval	overtime_;
171 	struct callout	callout_; 	/* for timeout() calls */
172 	struct netmsg_base callout_nmsg_;
173 
174 	rm_class_stats_t stats_;	/* Class Statistics */
175 };
176 
177 /*
178  * CBQ Interface state
179  */
180 struct rm_ifdat {
181 	int		queued_;	/* # pkts queued downstream */
182 	int		efficient_;	/* Link Efficency bit */
183 	int		wrr_;		/* Enable Weighted Round-Robin */
184 	u_long		ns_per_byte_;	/* Link byte speed. */
185 	int		maxqueued_;	/* Max packets to queue */
186 	int		maxpkt_;	/* Max packet size. */
187 	int		qi_;		/* In/out pointers for downstream */
188 	int		qo_;		/* packets */
189 
190 	/*
191 	 * Active class state and WRR state.
192 	 */
193 	rm_class_t	*active_[RM_MAXPRIO];	/* Active cl's in each pri */
194 	int		na_[RM_MAXPRIO];	/* # of active cl's in a pri */
195 	int		num_[RM_MAXPRIO];	/* # of cl's per pri */
196 	int		alloc_[RM_MAXPRIO];	/* Byte Allocation */
197 	u_long		M_[RM_MAXPRIO];		/* WRR weights. */
198 
199 	/*
200 	 * Network Interface/Solaris Queue state pointer.
201 	 */
202 	struct ifaltq	*ifq_;
203 	rm_class_t	*default_;	/* Default Pkt class, BE */
204 	rm_class_t	*root_;		/* Root Link class. */
205 	rm_class_t	*ctl_;		/* Control Traffic class. */
206 	void		(*restart)(struct ifaltq *);	/* Restart routine. */
207 
208 	/*
209 	 * Current packet downstream packet state and dynamic state.
210 	 */
211 	rm_class_t	*borrowed_[RM_MAXQUEUED]; /* Class borrowed last */
212 	rm_class_t	*class_[RM_MAXQUEUED];	/* class sending */
213 	int		curlen_[RM_MAXQUEUED];	/* Current pktlen */
214 	struct timeval	now_[RM_MAXQUEUED];	/* Current packet time. */
215 	int		is_overlimit_[RM_MAXQUEUED];/* Current packet time. */
216 
217 	int		cutoff_;	/* Cut-off depth for borrowing */
218 
219 	struct timeval	ifnow_;		/* expected xmit completion time */
220 #if 1 /* ALTQ4PPP */
221 	int		maxiftime_;	/* max delay inside interface */
222 #endif
223         rm_class_t	*pollcache_;	/* cached rm_class by poll operation */
224 };
225 
226 /* flags for rmc_init and rmc_newclass */
227 /* class flags */
228 #define	RMCF_RED		0x0001
229 #define	RMCF_ECN		0x0002
230 #define	RMCF_RIO		0x0004
231 #define	RMCF_CLEARDSCP		0x0008  /* clear diffserv codepoint */
232 
233 /* flags for rmc_init */
234 #define	RMCF_WRR		0x0100
235 #define	RMCF_EFFICIENT		0x0200
236 
237 #define	is_a_parent_class(cl)	((cl)->children_ != NULL)
238 
239 rm_class_t *rmc_newclass(int, struct rm_ifdat *, u_int,
240 			 void (*)(struct rm_class *, struct rm_class *),
241 			 int, struct rm_class *, struct rm_class *,
242 			 u_int, int, u_int, int, int);
243 void	rmc_delete_class(struct rm_ifdat *, struct rm_class *);
244 int 	rmc_modclass(struct rm_class *, u_int, int, u_int, int, u_int, int);
245 void	rmc_init(struct ifaltq *, struct rm_ifdat *, u_int,
246 		 void (*)(struct ifaltq *), int, int, u_int, int, u_int, int);
247 int	rmc_queue_packet(struct rm_class *, struct mbuf *);
248 struct mbuf *rmc_dequeue_next(struct rm_ifdat *, int);
249 void	rmc_update_class_util(struct rm_ifdat *);
250 void	rmc_delay_action(struct rm_class *, struct rm_class *);
251 void	rmc_dropall(struct rm_class *);
252 int	rmc_get_weight(struct rm_ifdat *, int);
253 
254 #endif /* _KERNEL */
255 
256 #endif /* _ALTQ_ALTQ_RMCLASS_H_ */
257