1/*-
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.
32 *
33 * $KAME: altq_rmclass.h,v 1.10 2003/08/20 23:30:23 itojun Exp $
34 */
35
36#ifndef _ALTQ_ALTQ_RMCLASS_H_
37#define _ALTQ_ALTQ_RMCLASS_H_
38
39#include <net/altq/altq_classq.h>
40
41#ifdef __cplusplus
42extern "C" {
43#endif
44
45#define RM_MAXPRIO 8 /* Max priority */
46
47#ifdef _KERNEL
48
49typedef struct mbuf mbuf_t;
50typedef struct rm_ifdat rm_ifdat_t;
51typedef struct rm_class rm_class_t;
52
53struct red;
54
55/*
56 * Macros for dealing with time values. We assume all times are
57 * 'timevals'. `microtime' is used to get the best available clock
58 * resolution. If `microtime' *doesn't* return a value that's about
59 * ten times smaller than the average packet time on the fastest
60 * link that will use these routines, a slightly different clock
61 * scheme than this one should be used.
62 * (Bias due to truncation error in this scheme will overestimate utilization
63 * and discriminate against high bandwidth classes. To remove this bias an
64 * integrator needs to be added. The simplest integrator uses a history of
65 * 10 * avg.packet.time / min.tick.time packet completion entries. This is
66 * straight forward to add but we don't want to pay the extra memory
67 * traffic to maintain it if it's not necessary (occasionally a vendor
68 * accidentally builds a workstation with a decent clock - e.g., Sun & HP).)
69 */
70
71#define RM_GETTIME(now) microtime(&now)
72
73#define TV_LT(a, b) (((a)->tv_sec < (b)->tv_sec) || \
74 (((a)->tv_usec < (b)->tv_usec) && ((a)->tv_sec <= (b)->tv_sec)))
75
76#define TV_DELTA(a, b, delta) { \
77 int xxs; \
78 \
79 delta = (a)->tv_usec - (b)->tv_usec; \
80 if ((xxs = (a)->tv_sec - (b)->tv_sec)) { \
81 switch (xxs) { \
82 default: \
83 /* if (xxs < 0) \
84 printf("rm_class: bogus time values\n"); */ \
85 delta = 0; \
86 /* fall through */ \
87 case 2: \
88 delta += 1000000; \
89 /* fall through */ \
90 case 1: \
91 delta += 1000000; \
92 break; \
93 } \
94 } \
95}
96
97#define TV_ADD_DELTA(a, delta, res) { \
98 int xxus = (a)->tv_usec + (delta); \
99 \
100 (res)->tv_sec = (a)->tv_sec; \
101 while (xxus >= 1000000) { \
102 ++((res)->tv_sec); \
103 xxus -= 1000000; \
104 } \
105 (res)->tv_usec = xxus; \
106}
107
108#define RM_TIMEOUT 2 /* 1 Clock tick. */
109
110#if 1
111#define RM_MAXQUEUED 1 /* this isn't used in ALTQ/CBQ */
112#else
113#define RM_MAXQUEUED 16 /* Max number of packets downstream of CBQ */
114#endif
115#define RM_MAXQUEUE 64 /* Max queue length */
116#define RM_FILTER_GAIN 5 /* log2 of gain, e.g., 5 => 31/32 */
117#define RM_POWER (1 << RM_FILTER_GAIN)
118#define RM_MAXDEPTH 32
119#define RM_NS_PER_SEC (1000000000)
120
121typedef struct _rm_class_stats_ {
122 u_int handle;
123 u_int depth;
124
125 struct pktcntr xmit_cnt; /* packets sent in this class */
126 struct pktcntr drop_cnt; /* dropped packets */
127 u_int over; /* # times went over limit */
128 u_int borrows; /* # times tried to borrow */
129 u_int overactions; /* # times invoked overlimit action */
130 u_int delays; /* # times invoked delay actions */
131} rm_class_stats_t;
132
133/*
134 * CBQ Class state structure
135 */
136struct rm_class {
137 class_queue_t *q_; /* Queue of packets */
138 rm_ifdat_t *ifdat_;
139 int pri_; /* Class priority. */
140 int depth_; /* Class depth */
141 u_int ns_per_byte_; /* NanoSeconds per byte. */
142 u_int maxrate_; /* Bytes per second for this class. */
143 u_int allotment_; /* Fraction of link bandwidth. */
144 u_int w_allotment_; /* Weighted allotment for WRR */
145 int bytes_alloc_; /* Allocation for round of WRR */
146
147 int avgidle_;
148 int maxidle_;
149 int minidle_;
150 int offtime_;
151 int sleeping_; /* != 0 if delaying */
152 int qthresh_; /* Queue threshold for formal link sharing */
153 int leaf_; /* Note whether leaf class or not.*/
154
155 rm_class_t *children_; /* Children of this class */
156 rm_class_t *next_; /* Next pointer, used if child */
157
158 rm_class_t *peer_; /* Peer class */
159 rm_class_t *borrow_; /* Borrow class */
160 rm_class_t *parent_; /* Parent class */
161
162 void (*overlimit)(struct rm_class *, struct rm_class *);
163 void (*drop)(struct rm_class *); /* Class drop action. */
164
165 union {
166 struct red *red_; /* RED state pointer */
167 struct codel *codel_; /* codel state pointer */
168 } cl_aqm_;
169#define red_ cl_aqm_.red_
170#define codel_ cl_aqm_.codel_
171 struct altq_pktattr *pktattr_; /* saved hdr used by RED/ECN */
172 int flags_;
173
174 int last_pkttime_; /* saved pkt_time */
175 struct timeval undertime_; /* time can next send */
176 struct timeval last_; /* time last packet sent */
177 struct timeval overtime_;
178 struct callout callout_; /* for timeout() calls */
179
180 rm_class_stats_t stats_; /* Class Statistics */
181};
182
183/*
184 * CBQ Interface state
185 */
186struct rm_ifdat {
187 int queued_; /* # pkts queued downstream */
188 int efficient_; /* Link Efficiency bit */
189 int wrr_; /* Enable Weighted Round-Robin */
190 u_long ns_per_byte_; /* Link byte speed. */
191 int maxqueued_; /* Max packets to queue */
192 int maxpkt_; /* Max packet size. */
193 int qi_; /* In/out pointers for downstream */
194 int qo_; /* packets */
195
196 /*
197 * Active class state and WRR state.
198 */
199 rm_class_t *active_[RM_MAXPRIO]; /* Active cl's in each pri */
200 int na_[RM_MAXPRIO]; /* # of active cl's in a pri */
201 int num_[RM_MAXPRIO]; /* # of cl's per pri */
202 int alloc_[RM_MAXPRIO]; /* Byte Allocation */
203 u_long M_[RM_MAXPRIO]; /* WRR weights. */
204
205 /*
206 * Network Interface/Solaris Queue state pointer.
207 */
208 struct ifaltq *ifq_;
209 rm_class_t *default_; /* Default Pkt class, BE */
210 rm_class_t *root_; /* Root Link class. */
211 rm_class_t *ctl_; /* Control Traffic class. */
212 void (*restart)(struct ifaltq *); /* Restart routine. */
213
214 /*
215 * Current packet downstream packet state and dynamic state.
216 */
217 rm_class_t *borrowed_[RM_MAXQUEUED]; /* Class borrowed last */
218 rm_class_t *class_[RM_MAXQUEUED]; /* class sending */
219 int curlen_[RM_MAXQUEUED]; /* Current pktlen */
220 struct timeval now_[RM_MAXQUEUED]; /* Current packet time. */
221 int is_overlimit_[RM_MAXQUEUED];/* Current packet time. */
222
223 int cutoff_; /* Cut-off depth for borrowing */
224
225 struct timeval ifnow_; /* expected xmit completion time */
226#if 1 /* ALTQ4PPP */
227 int maxiftime_; /* max delay inside interface */
228#endif
229 rm_class_t *pollcache_; /* cached rm_class by poll operation */
230};
231
232/* flags for rmc_init and rmc_newclass */
233/* class flags; must be the same as class flags in altq_cbq.h */
234#define RMCF_RED 0x0001
235#define RMCF_ECN 0x0002
236#define RMCF_RIO 0x0004
237#define RMCF_FLOWVALVE 0x0008 /* use flowvalve (aka penalty-box) */
238#define RMCF_CLEARDSCP 0x0010 /* clear diffserv codepoint */
239#define RMCF_CODEL 0x0040
240
241/* flags for rmc_init */
242#define RMCF_WRR 0x0100
243#define RMCF_EFFICIENT 0x0200
244
245#define is_a_parent_class(cl) ((cl)->children_ != NULL)
246
247extern rm_class_t *rmc_newclass(int, struct rm_ifdat *, u_int,
248 void (*)(struct rm_class *, struct rm_class *),
249 int, struct rm_class *, struct rm_class *,
250 u_int, int, u_int, int, int);
251extern void rmc_delete_class(struct rm_ifdat *, struct rm_class *);
252extern int rmc_modclass(struct rm_class *, u_int, int,
253 u_int, int, u_int, int);
254extern void rmc_init(struct ifaltq *, struct rm_ifdat *, u_int,
255 void (*)(struct ifaltq *),
256 int, int, u_int, int, u_int, int);
257extern int rmc_queue_packet(struct rm_class *, mbuf_t *);
258extern mbuf_t *rmc_dequeue_next(struct rm_ifdat *, int);
259extern void rmc_update_class_util(struct rm_ifdat *);
260extern void rmc_delay_action(struct rm_class *, struct rm_class *);
261extern void rmc_dropall(struct rm_class *);
262extern int rmc_get_weight(struct rm_ifdat *, int);
263
264#endif /* _KERNEL */
265
266#ifdef __cplusplus
267}
268#endif
269
270#endif /* _ALTQ_ALTQ_RMCLASS_H_ */