← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to net/sched/sch_red.c

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
Import upstream version 3.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 980914: computation fixes
 
13
 * Alexey Makarenko <makar@phoenix.kharkov.ua> 990814: qave on idle link was calculated incorrectly.
 
14
 * J Hadi Salim 980816:  ECN support
 
15
 */
 
16
 
 
17
#include <linux/module.h>
 
18
#include <linux/types.h>
 
19
#include <linux/kernel.h>
 
20
#include <linux/skbuff.h>
 
21
#include <net/pkt_sched.h>
 
22
#include <net/inet_ecn.h>
 
23
#include <net/red.h>
 
24
 
 
25
 
 
26
/*      Parameters, settable by user:
 
27
        -----------------------------
 
28
 
 
29
        limit           - bytes (must be > qth_max + burst)
 
30
 
 
31
        Hard limit on queue length, should be chosen >qth_max
 
32
        to allow packet bursts. This parameter does not
 
33
        affect the algorithms behaviour and can be chosen
 
34
        arbitrarily high (well, less than ram size)
 
35
        Really, this limit will never be reached
 
36
        if RED works correctly.
 
37
 */
 
38
 
 
39
struct red_sched_data {
 
40
        u32                     limit;          /* HARD maximal queue length */
 
41
        unsigned char           flags;
 
42
        struct red_parms        parms;
 
43
        struct red_stats        stats;
 
44
        struct Qdisc            *qdisc;
 
45
};
 
46
 
 
47
static inline int red_use_ecn(struct red_sched_data *q)
 
48
{
 
49
        return q->flags & TC_RED_ECN;
 
50
}
 
51
 
 
52
static inline int red_use_harddrop(struct red_sched_data *q)
 
53
{
 
54
        return q->flags & TC_RED_HARDDROP;
 
55
}
 
56
 
 
57
static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 
58
{
 
59
        struct red_sched_data *q = qdisc_priv(sch);
 
60
        struct Qdisc *child = q->qdisc;
 
61
        int ret;
 
62
 
 
63
        q->parms.qavg = red_calc_qavg(&q->parms, child->qstats.backlog);
 
64
 
 
65
        if (red_is_idling(&q->parms))
 
66
                red_end_of_idle_period(&q->parms);
 
67
 
 
68
        switch (red_action(&q->parms, q->parms.qavg)) {
 
69
        case RED_DONT_MARK:
 
70
                break;
 
71
 
 
72
        case RED_PROB_MARK:
 
73
                sch->qstats.overlimits++;
 
74
                if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
 
75
                        q->stats.prob_drop++;
 
76
                        goto congestion_drop;
 
77
                }
 
78
 
 
79
                q->stats.prob_mark++;
 
80
                break;
 
81
 
 
82
        case RED_HARD_MARK:
 
83
                sch->qstats.overlimits++;
 
84
                if (red_use_harddrop(q) || !red_use_ecn(q) ||
 
85
                    !INET_ECN_set_ce(skb)) {
 
86
                        q->stats.forced_drop++;
 
87
                        goto congestion_drop;
 
88
                }
 
89
 
 
90
                q->stats.forced_mark++;
 
91
                break;
 
92
        }
 
93
 
 
94
        ret = qdisc_enqueue(skb, child);
 
95
        if (likely(ret == NET_XMIT_SUCCESS)) {
 
96
                sch->q.qlen++;
 
97
        } else if (net_xmit_drop_count(ret)) {
 
98
                q->stats.pdrop++;
 
99
                sch->qstats.drops++;
 
100
        }
 
101
        return ret;
 
102
 
 
103
congestion_drop:
 
104
        qdisc_drop(skb, sch);
 
105
        return NET_XMIT_CN;
 
106
}
 
107
 
 
108
static struct sk_buff *red_dequeue(struct Qdisc *sch)
 
109
{
 
110
        struct sk_buff *skb;
 
111
        struct red_sched_data *q = qdisc_priv(sch);
 
112
        struct Qdisc *child = q->qdisc;
 
113
 
 
114
        skb = child->dequeue(child);
 
115
        if (skb) {
 
116
                qdisc_bstats_update(sch, skb);
 
117
                sch->q.qlen--;
 
118
        } else {
 
119
                if (!red_is_idling(&q->parms))
 
120
                        red_start_of_idle_period(&q->parms);
 
121
        }
 
122
        return skb;
 
123
}
 
124
 
 
125
static struct sk_buff *red_peek(struct Qdisc *sch)
 
126
{
 
127
        struct red_sched_data *q = qdisc_priv(sch);
 
128
        struct Qdisc *child = q->qdisc;
 
129
 
 
130
        return child->ops->peek(child);
 
131
}
 
132
 
 
133
static unsigned int red_drop(struct Qdisc *sch)
 
134
{
 
135
        struct red_sched_data *q = qdisc_priv(sch);
 
136
        struct Qdisc *child = q->qdisc;
 
137
        unsigned int len;
 
138
 
 
139
        if (child->ops->drop && (len = child->ops->drop(child)) > 0) {
 
140
                q->stats.other++;
 
141
                sch->qstats.drops++;
 
142
                sch->q.qlen--;
 
143
                return len;
 
144
        }
 
145
 
 
146
        if (!red_is_idling(&q->parms))
 
147
                red_start_of_idle_period(&q->parms);
 
148
 
 
149
        return 0;
 
150
}
 
151
 
 
152
static void red_reset(struct Qdisc *sch)
 
153
{
 
154
        struct red_sched_data *q = qdisc_priv(sch);
 
155
 
 
156
        qdisc_reset(q->qdisc);
 
157
        sch->q.qlen = 0;
 
158
        red_restart(&q->parms);
 
159
}
 
160
 
 
161
static void red_destroy(struct Qdisc *sch)
 
162
{
 
163
        struct red_sched_data *q = qdisc_priv(sch);
 
164
        qdisc_destroy(q->qdisc);
 
165
}
 
166
 
 
167
static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
 
168
        [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
 
169
        [TCA_RED_STAB]  = { .len = RED_STAB_SIZE },
 
170
};
 
171
 
 
172
static int red_change(struct Qdisc *sch, struct nlattr *opt)
 
173
{
 
174
        struct red_sched_data *q = qdisc_priv(sch);
 
175
        struct nlattr *tb[TCA_RED_MAX + 1];
 
176
        struct tc_red_qopt *ctl;
 
177
        struct Qdisc *child = NULL;
 
178
        int err;
 
179
 
 
180
        if (opt == NULL)
 
181
                return -EINVAL;
 
182
 
 
183
        err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy);
 
184
        if (err < 0)
 
185
                return err;
 
186
 
 
187
        if (tb[TCA_RED_PARMS] == NULL ||
 
188
            tb[TCA_RED_STAB] == NULL)
 
189
                return -EINVAL;
 
190
 
 
191
        ctl = nla_data(tb[TCA_RED_PARMS]);
 
192
 
 
193
        if (ctl->limit > 0) {
 
194
                child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
 
195
                if (IS_ERR(child))
 
196
                        return PTR_ERR(child);
 
197
        }
 
198
 
 
199
        sch_tree_lock(sch);
 
200
        q->flags = ctl->flags;
 
201
        q->limit = ctl->limit;
 
202
        if (child) {
 
203
                qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen);
 
204
                qdisc_destroy(q->qdisc);
 
205
                q->qdisc = child;
 
206
        }
 
207
 
 
208
        red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
 
209
                                 ctl->Plog, ctl->Scell_log,
 
210
                                 nla_data(tb[TCA_RED_STAB]));
 
211
 
 
212
        if (!q->qdisc->q.qlen)
 
213
                red_start_of_idle_period(&q->parms);
 
214
 
 
215
        sch_tree_unlock(sch);
 
216
        return 0;
 
217
}
 
218
 
 
219
static int red_init(struct Qdisc *sch, struct nlattr *opt)
 
220
{
 
221
        struct red_sched_data *q = qdisc_priv(sch);
 
222
 
 
223
        q->qdisc = &noop_qdisc;
 
224
        return red_change(sch, opt);
 
225
}
 
226
 
 
227
static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
 
228
{
 
229
        struct red_sched_data *q = qdisc_priv(sch);
 
230
        struct nlattr *opts = NULL;
 
231
        struct tc_red_qopt opt = {
 
232
                .limit          = q->limit,
 
233
                .flags          = q->flags,
 
234
                .qth_min        = q->parms.qth_min >> q->parms.Wlog,
 
235
                .qth_max        = q->parms.qth_max >> q->parms.Wlog,
 
236
                .Wlog           = q->parms.Wlog,
 
237
                .Plog           = q->parms.Plog,
 
238
                .Scell_log      = q->parms.Scell_log,
 
239
        };
 
240
 
 
241
        sch->qstats.backlog = q->qdisc->qstats.backlog;
 
242
        opts = nla_nest_start(skb, TCA_OPTIONS);
 
243
        if (opts == NULL)
 
244
                goto nla_put_failure;
 
245
        NLA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt);
 
246
        return nla_nest_end(skb, opts);
 
247
 
 
248
nla_put_failure:
 
249
        nla_nest_cancel(skb, opts);
 
250
        return -EMSGSIZE;
 
251
}
 
252
 
 
253
static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 
254
{
 
255
        struct red_sched_data *q = qdisc_priv(sch);
 
256
        struct tc_red_xstats st = {
 
257
                .early  = q->stats.prob_drop + q->stats.forced_drop,
 
258
                .pdrop  = q->stats.pdrop,
 
259
                .other  = q->stats.other,
 
260
                .marked = q->stats.prob_mark + q->stats.forced_mark,
 
261
        };
 
262
 
 
263
        return gnet_stats_copy_app(d, &st, sizeof(st));
 
264
}
 
265
 
 
266
static int red_dump_class(struct Qdisc *sch, unsigned long cl,
 
267
                          struct sk_buff *skb, struct tcmsg *tcm)
 
268
{
 
269
        struct red_sched_data *q = qdisc_priv(sch);
 
270
 
 
271
        tcm->tcm_handle |= TC_H_MIN(1);
 
272
        tcm->tcm_info = q->qdisc->handle;
 
273
        return 0;
 
274
}
 
275
 
 
276
static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
 
277
                     struct Qdisc **old)
 
278
{
 
279
        struct red_sched_data *q = qdisc_priv(sch);
 
280
 
 
281
        if (new == NULL)
 
282
                new = &noop_qdisc;
 
283
 
 
284
        sch_tree_lock(sch);
 
285
        *old = q->qdisc;
 
286
        q->qdisc = new;
 
287
        qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
 
288
        qdisc_reset(*old);
 
289
        sch_tree_unlock(sch);
 
290
        return 0;
 
291
}
 
292
 
 
293
static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
 
294
{
 
295
        struct red_sched_data *q = qdisc_priv(sch);
 
296
        return q->qdisc;
 
297
}
 
298
 
 
299
static unsigned long red_get(struct Qdisc *sch, u32 classid)
 
300
{
 
301
        return 1;
 
302
}
 
303
 
 
304
static void red_put(struct Qdisc *sch, unsigned long arg)
 
305
{
 
306
}
 
307
 
 
308
static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
 
309
{
 
310
        if (!walker->stop) {
 
311
                if (walker->count >= walker->skip)
 
312
                        if (walker->fn(sch, 1, walker) < 0) {
 
313
                                walker->stop = 1;
 
314
                                return;
 
315
                        }
 
316
                walker->count++;
 
317
        }
 
318
}
 
319
 
 
320
static const struct Qdisc_class_ops red_class_ops = {
 
321
        .graft          =       red_graft,
 
322
        .leaf           =       red_leaf,
 
323
        .get            =       red_get,
 
324
        .put            =       red_put,
 
325
        .walk           =       red_walk,
 
326
        .dump           =       red_dump_class,
 
327
};
 
328
 
 
329
static struct Qdisc_ops red_qdisc_ops __read_mostly = {
 
330
        .id             =       "red",
 
331
        .priv_size      =       sizeof(struct red_sched_data),
 
332
        .cl_ops         =       &red_class_ops,
 
333
        .enqueue        =       red_enqueue,
 
334
        .dequeue        =       red_dequeue,
 
335
        .peek           =       red_peek,
 
336
        .drop           =       red_drop,
 
337
        .init           =       red_init,
 
338
        .reset          =       red_reset,
 
339
        .destroy        =       red_destroy,
 
340
        .change         =       red_change,
 
341
        .dump           =       red_dump,
 
342
        .dump_stats     =       red_dump_stats,
 
343
        .owner          =       THIS_MODULE,
 
344
};
 
345
 
 
346
static int __init red_module_init(void)
 
347
{
 
348
        return register_qdisc(&red_qdisc_ops);
 
349
}
 
350
 
 
351
static void __exit red_module_exit(void)
 
352
{
 
353
        unregister_qdisc(&red_qdisc_ops);
 
354
}
 
355
 
 
356
module_init(red_module_init)
 
357
module_exit(red_module_exit)
 
358
 
 
359
MODULE_LICENSE("GPL");