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