[PKT_SCHED]: RED: Use generic queue management interface
[linux-2.6.git] / net / sched / sch_red.c
1 /*
2  * net/sched/sch_red.c  Random Early Detection queue.
3  *
4  *              This program is free software; you can redistribute it and/or
5  *              modify it under the terms of the GNU General Public License
6  *              as published by the Free Software Foundation; either version
7  *              2 of the License, or (at your option) any later version.
8  *
9  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
10  *
11  * Changes:
12  * J Hadi Salim <hadi@nortel.com> 980914:       computation fixes
13  * Alexey Makarenko <makar@phoenix.kharkov.ua> 990814: qave on idle link was calculated incorrectly.
14  * J Hadi Salim <hadi@nortelnetworks.com> 980816:  ECN support  
15  */
16
17 #include <linux/config.h>
18 #include <linux/module.h>
19 #include <asm/uaccess.h>
20 #include <asm/system.h>
21 #include <linux/bitops.h>
22 #include <linux/types.h>
23 #include <linux/kernel.h>
24 #include <linux/sched.h>
25 #include <linux/string.h>
26 #include <linux/mm.h>
27 #include <linux/socket.h>
28 #include <linux/sockios.h>
29 #include <linux/in.h>
30 #include <linux/errno.h>
31 #include <linux/interrupt.h>
32 #include <linux/if_ether.h>
33 #include <linux/inet.h>
34 #include <linux/netdevice.h>
35 #include <linux/etherdevice.h>
36 #include <linux/notifier.h>
37 #include <net/ip.h>
38 #include <net/route.h>
39 #include <linux/skbuff.h>
40 #include <net/sock.h>
41 #include <net/pkt_sched.h>
42 #include <net/inet_ecn.h>
43 #include <net/dsfield.h>
44 #include <net/red.h>
45
46
47 /*      Parameters, settable by user:
48         -----------------------------
49
50         limit           - bytes (must be > qth_max + burst)
51
52         Hard limit on queue length, should be chosen >qth_max
53         to allow packet bursts. This parameter does not
54         affect the algorithms behaviour and can be chosen
55         arbitrarily high (well, less than ram size)
56         Really, this limit will never be reached
57         if RED works correctly.
58  */
59
60 struct red_sched_data
61 {
62         u32                     limit;          /* HARD maximal queue length */
63         unsigned char           flags;
64         struct red_parms        parms;
65         struct red_stats        stats;
66 };
67
68 static inline int red_use_ecn(struct red_sched_data *q)
69 {
70         return q->flags & TC_RED_ECN;
71 }
72
73 static int
74 red_enqueue(struct sk_buff *skb, struct Qdisc* sch)
75 {
76         struct red_sched_data *q = qdisc_priv(sch);
77
78         q->parms.qavg = red_calc_qavg(&q->parms, sch->qstats.backlog);
79
80         if (red_is_idling(&q->parms))
81                 red_end_of_idle_period(&q->parms);
82
83         switch (red_action(&q->parms, q->parms.qavg)) {
84                 case RED_DONT_MARK:
85                         break;
86
87                 case RED_PROB_MARK:
88                         sch->qstats.overlimits++;
89                         if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
90                                 q->stats.prob_drop++;
91                                 goto congestion_drop;
92                         }
93
94                         q->stats.prob_mark++;
95                         break;
96
97                 case RED_HARD_MARK:
98                         sch->qstats.overlimits++;
99                         if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
100                                 q->stats.forced_drop++;
101                                 goto congestion_drop;
102                         }
103
104                         q->stats.forced_mark++;
105                         break;
106         }
107
108         if (sch->qstats.backlog + skb->len <= q->limit)
109                 return qdisc_enqueue_tail(skb, sch);
110
111         q->stats.pdrop++;
112         return qdisc_drop(skb, sch);
113
114 congestion_drop:
115         qdisc_drop(skb, sch);
116         return NET_XMIT_CN;
117 }
118
119 static int
120 red_requeue(struct sk_buff *skb, struct Qdisc* sch)
121 {
122         struct red_sched_data *q = qdisc_priv(sch);
123
124         if (red_is_idling(&q->parms))
125                 red_end_of_idle_period(&q->parms);
126
127         return qdisc_requeue(skb, sch);
128 }
129
130 static struct sk_buff *
131 red_dequeue(struct Qdisc* sch)
132 {
133         struct sk_buff *skb;
134         struct red_sched_data *q = qdisc_priv(sch);
135
136         skb = qdisc_dequeue_head(sch);
137
138         if (skb == NULL)
139                 red_start_of_idle_period(&q->parms);
140
141         return skb;
142 }
143
144 static unsigned int red_drop(struct Qdisc* sch)
145 {
146         struct sk_buff *skb;
147         struct red_sched_data *q = qdisc_priv(sch);
148
149         skb = qdisc_dequeue_tail(sch);
150         if (skb) {
151                 unsigned int len = skb->len;
152                 q->stats.other++;
153                 qdisc_drop(skb, sch);
154                 return len;
155         }
156
157         red_start_of_idle_period(&q->parms);
158         return 0;
159 }
160
161 static void red_reset(struct Qdisc* sch)
162 {
163         struct red_sched_data *q = qdisc_priv(sch);
164
165         qdisc_reset_queue(sch);
166         red_restart(&q->parms);
167 }
168
169 static int red_change(struct Qdisc *sch, struct rtattr *opt)
170 {
171         struct red_sched_data *q = qdisc_priv(sch);
172         struct rtattr *tb[TCA_RED_STAB];
173         struct tc_red_qopt *ctl;
174
175         if (opt == NULL ||
176             rtattr_parse_nested(tb, TCA_RED_STAB, opt) ||
177             tb[TCA_RED_PARMS-1] == 0 || tb[TCA_RED_STAB-1] == 0 ||
178             RTA_PAYLOAD(tb[TCA_RED_PARMS-1]) < sizeof(*ctl) ||
179             RTA_PAYLOAD(tb[TCA_RED_STAB-1]) < 256)
180                 return -EINVAL;
181
182         ctl = RTA_DATA(tb[TCA_RED_PARMS-1]);
183
184         sch_tree_lock(sch);
185         q->flags = ctl->flags;
186         q->limit = ctl->limit;
187
188         red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
189                                  ctl->Plog, ctl->Scell_log,
190                                  RTA_DATA(tb[TCA_RED_STAB-1]));
191
192         if (skb_queue_empty(&sch->q))
193                 red_end_of_idle_period(&q->parms);
194         sch_tree_unlock(sch);
195         return 0;
196 }
197
198 static int red_init(struct Qdisc* sch, struct rtattr *opt)
199 {
200         return red_change(sch, opt);
201 }
202
203 static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
204 {
205         struct red_sched_data *q = qdisc_priv(sch);
206         unsigned char    *b = skb->tail;
207         struct rtattr *rta;
208         struct tc_red_qopt opt = {
209                 .limit          = q->limit,
210                 .flags          = q->flags,
211                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
212                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
213                 .Wlog           = q->parms.Wlog,
214                 .Plog           = q->parms.Plog,
215                 .Scell_log      = q->parms.Scell_log,
216         };
217
218         rta = (struct rtattr*)b;
219         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
220         RTA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
221         rta->rta_len = skb->tail - b;
222
223         return skb->len;
224
225 rtattr_failure:
226         skb_trim(skb, b - skb->data);
227         return -1;
228 }
229
230 static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
231 {
232         struct red_sched_data *q = qdisc_priv(sch);
233         struct tc_red_xstats st = {
234                 .early  = q->stats.prob_drop + q->stats.forced_drop,
235                 .pdrop  = q->stats.pdrop,
236                 .other  = q->stats.other,
237                 .marked = q->stats.prob_mark + q->stats.forced_mark,
238         };
239
240         return gnet_stats_copy_app(d, &st, sizeof(st));
241 }
242
243 static struct Qdisc_ops red_qdisc_ops = {
244         .next           =       NULL,
245         .cl_ops         =       NULL,
246         .id             =       "red",
247         .priv_size      =       sizeof(struct red_sched_data),
248         .enqueue        =       red_enqueue,
249         .dequeue        =       red_dequeue,
250         .requeue        =       red_requeue,
251         .drop           =       red_drop,
252         .init           =       red_init,
253         .reset          =       red_reset,
254         .change         =       red_change,
255         .dump           =       red_dump,
256         .dump_stats     =       red_dump_stats,
257         .owner          =       THIS_MODULE,
258 };
259
260 static int __init red_module_init(void)
261 {
262         return register_qdisc(&red_qdisc_ops);
263 }
264 static void __exit red_module_exit(void) 
265 {
266         unregister_qdisc(&red_qdisc_ops);
267 }
268 module_init(red_module_init)
269 module_exit(red_module_exit)
270 MODULE_LICENSE("GPL");