Release 4.15 net/sched/sch_red.c
/*
* net/sched/sch_red.c Random Early Detection queue.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version
* 2 of the License, or (at your option) any later version.
*
* Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
*
* Changes:
* J Hadi Salim 980914: computation fixes
* Alexey Makarenko <makar@phoenix.kharkov.ua> 990814: qave on idle link was calculated incorrectly.
* J Hadi Salim 980816: ECN support
*/
#include <linux/module.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/skbuff.h>
#include <net/pkt_sched.h>
#include <net/pkt_cls.h>
#include <net/inet_ecn.h>
#include <net/red.h>
/* Parameters, settable by user:
-----------------------------
limit - bytes (must be > qth_max + burst)
Hard limit on queue length, should be chosen >qth_max
to allow packet bursts. This parameter does not
affect the algorithms behaviour and can be chosen
arbitrarily high (well, less than ram size)
Really, this limit will never be reached
if RED works correctly.
*/
struct red_sched_data {
u32 limit; /* HARD maximal queue length */
unsigned char flags;
struct timer_list adapt_timer;
struct Qdisc *sch;
struct red_parms parms;
struct red_vars vars;
struct red_stats stats;
struct Qdisc *qdisc;
};
static inline int red_use_ecn(struct red_sched_data *q)
{
return q->flags & TC_RED_ECN;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Linus Torvalds (pre-git) | 10 | 52.63% | 1 | 33.33% |
Thomas Graf | 8 | 42.11% | 1 | 33.33% |
Patrick McHardy | 1 | 5.26% | 1 | 33.33% |
Total | 19 | 100.00% | 3 | 100.00% |
static inline int red_use_harddrop(struct red_sched_data *q)
{
return q->flags & TC_RED_HARDDROP;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Thomas Graf | 19 | 100.00% | 1 | 100.00% |
Total | 19 | 100.00% | 1 | 100.00% |
static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch,
struct sk_buff **to_free)
{
struct red_sched_data *q = qdisc_priv(sch);
struct Qdisc *child = q->qdisc;
int ret;
q->vars.qavg = red_calc_qavg(&q->parms,
&q->vars,
child->qstats.backlog);
if (red_is_idling(&q->vars))
red_end_of_idle_period(&q->vars);
switch (red_action(&q->parms, &q->vars, q->vars.qavg)) {
case RED_DONT_MARK:
break;
case RED_PROB_MARK:
qdisc_qstats_overlimit(sch);
if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) {
q->stats.prob_drop++;
goto congestion_drop;
}
q->stats.prob_mark++;
break;
case RED_HARD_MARK:
qdisc_qstats_overlimit(sch);
if (red_use_harddrop(q) || !red_use_ecn(q) ||
!INET_ECN_set_ce(skb)) {
q->stats.forced_drop++;
goto congestion_drop;
}
q->stats.forced_mark++;
break;
}
ret = qdisc_enqueue(skb, child, to_free);
if (likely(ret == NET_XMIT_SUCCESS)) {
qdisc_qstats_backlog_inc(sch, skb);
sch->q.qlen++;
} else if (net_xmit_drop_count(ret)) {
q->stats.pdrop++;
qdisc_qstats_drop(sch);
}
return ret;
congestion_drop:
qdisc_drop(skb, sch, to_free);
return NET_XMIT_CN;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Thomas Graf | 101 | 36.33% | 3 | 18.75% |
Linus Torvalds (pre-git) | 84 | 30.22% | 5 | 31.25% |
Patrick McHardy | 41 | 14.75% | 1 | 6.25% |
Eric Dumazet | 24 | 8.63% | 2 | 12.50% |
John Fastabend | 9 | 3.24% | 1 | 6.25% |
Jarek Poplawski | 8 | 2.88% | 1 | 6.25% |
Américo Wang | 7 | 2.52% | 1 | 6.25% |
Stephen Hemminger | 3 | 1.08% | 1 | 6.25% |
Jussi Kivilinna | 1 | 0.36% | 1 | 6.25% |
Total | 278 | 100.00% | 16 | 100.00% |
static struct sk_buff *red_dequeue(struct Qdisc *sch)
{
struct sk_buff *skb;
struct red_sched_data *q = qdisc_priv(sch);
struct Qdisc *child = q->qdisc;
skb = child->dequeue(child);
if (skb) {
qdisc_bstats_update(sch, skb);
qdisc_qstats_backlog_dec(sch, skb);
sch->q.qlen--;
} else {
if (!red_is_idling(&q->vars))
red_start_of_idle_period(&q->vars);
}
return skb;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Linus Torvalds (pre-git) | 41 | 41.84% | 2 | 20.00% |
Patrick McHardy | 23 | 23.47% | 1 | 10.00% |
Eric Dumazet | 14 | 14.29% | 2 | 20.00% |
Thomas Graf | 10 | 10.20% | 3 | 30.00% |
Américo Wang | 7 | 7.14% | 1 | 10.00% |
Stephen Hemminger | 3 | 3.06% | 1 | 10.00% |
Total | 98 | 100.00% | 10 | 100.00% |
static struct sk_buff *red_peek(struct Qdisc *sch)
{
struct red_sched_data *q = qdisc_priv(sch);
struct Qdisc *child = q->qdisc;
return child->ops->peek(child);
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Jarek Poplawski | 42 | 100.00% | 1 | 100.00% |
Total | 42 | 100.00% | 1 | 100.00% |
static void red_reset(struct Qdisc *sch)
{
struct red_sched_data *q = qdisc_priv(sch);
qdisc_reset(q->qdisc);
sch->qstats.backlog = 0;
sch->q.qlen = 0;
red_restart(&q->vars);
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Linus Torvalds (pre-git) | 26 | 50.00% | 2 | 28.57% |
Patrick McHardy | 12 | 23.08% | 1 | 14.29% |
Américo Wang | 8 | 15.38% | 1 | 14.29% |
Stephen Hemminger | 3 | 5.77% | 1 | 14.29% |
Thomas Graf | 2 | 3.85% | 1 | 14.29% |
Eric Dumazet | 1 | 1.92% | 1 | 14.29% |
Total | 52 | 100.00% | 7 | 100.00% |
static int red_offload(struct Qdisc *sch, bool enable)
{
struct red_sched_data *q = qdisc_priv(sch);
struct net_device *dev = qdisc_dev(sch);
struct tc_red_qopt_offload opt = {
.handle = sch->handle,
.parent = sch->parent,
};
int err;
if (!tc_can_offload(dev) || !dev->netdev_ops->ndo_setup_tc)
return -EOPNOTSUPP;
if (enable) {
opt.command = TC_RED_REPLACE;
opt.set.min = q->parms.qth_min >> q->parms.Wlog;
opt.set.max = q->parms.qth_max >> q->parms.Wlog;
opt.set.probability = q->parms.max_P;
opt.set.is_ecn = red_use_ecn(q);
} else {
opt.command = TC_RED_DESTROY;
}
err = dev->netdev_ops->ndo_setup_tc(dev, TC_SETUP_QDISC_RED, &opt);
if (!err && enable)
sch->flags |= TCQ_F_OFFLOADED;
else
sch->flags &= ~TCQ_F_OFFLOADED;
return err;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Nogah Frankel | 167 | 85.20% | 1 | 50.00% |
Yuval Mintz | 29 | 14.80% | 1 | 50.00% |
Total | 196 | 100.00% | 2 | 100.00% |
static void red_destroy(struct Qdisc *sch)
{
struct red_sched_data *q = qdisc_priv(sch);
del_timer_sync(&q->adapt_timer);
red_offload(sch, false);
qdisc_destroy(q->qdisc);
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Linus Torvalds (pre-git) | 15 | 34.88% | 2 | 33.33% |
Patrick McHardy | 10 | 23.26% | 1 | 16.67% |
Eric Dumazet | 8 | 18.60% | 1 | 16.67% |
Nogah Frankel | 7 | 16.28% | 1 | 16.67% |
Stephen Hemminger | 3 | 6.98% | 1 | 16.67% |
Total | 43 | 100.00% | 6 | 100.00% |
static const struct nla_policy red_policy[TCA_RED_MAX + 1] = {
[TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) },
[TCA_RED_STAB] = { .len = RED_STAB_SIZE },
[TCA_RED_MAX_P] = { .type = NLA_U32 },
};
static int red_change(struct Qdisc *sch, struct nlattr *opt)
{
struct red_sched_data *q = qdisc_priv(sch);
struct nlattr *tb[TCA_RED_MAX + 1];
struct tc_red_qopt *ctl;
struct Qdisc *child = NULL;
int err;
u32 max_P;
if (opt == NULL)
return -EINVAL;
err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy, NULL);
if (err < 0)
return err;
if (tb[TCA_RED_PARMS] == NULL ||
tb[TCA_RED_STAB] == NULL)
return -EINVAL;
max_P = tb[TCA_RED_MAX_P] ? nla_get_u32(tb[TCA_RED_MAX_P]) : 0;
ctl = nla_data(tb[TCA_RED_PARMS]);
if (!red_check_params(ctl->qth_min, ctl->qth_max, ctl->Wlog))
return -EINVAL;
if (ctl->limit > 0) {
child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit);
if (IS_ERR(child))
return PTR_ERR(child);
}
if (child != &noop_qdisc)
qdisc_hash_add(child, true);
sch_tree_lock(sch);
q->flags = ctl->flags;
q->limit = ctl->limit;
if (child) {
qdisc_tree_reduce_backlog(q->qdisc, q->qdisc->q.qlen,
q->qdisc->qstats.backlog);
qdisc_destroy(q->qdisc);
q->qdisc = child;
}
red_set_parms(&q->parms,
ctl->qth_min, ctl->qth_max, ctl->Wlog,
ctl->Plog, ctl->Scell_log,
nla_data(tb[TCA_RED_STAB]),
max_P);
red_set_vars(&q->vars);
del_timer(&q->adapt_timer);
if (ctl->flags & TC_RED_ADAPTATIVE)
mod_timer(&q->adapt_timer, jiffies + HZ/2);
if (!q->qdisc->q.qlen)
red_start_of_idle_period(&q->vars);
sch_tree_unlock(sch);
red_offload(sch, true);
return 0;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Patrick McHardy | 150 | 39.37% | 7 | 31.82% |
Linus Torvalds (pre-git) | 81 | 21.26% | 4 | 18.18% |
Eric Dumazet | 68 | 17.85% | 4 | 18.18% |
Nogah Frankel | 29 | 7.61% | 2 | 9.09% |
Thomas Graf | 28 | 7.35% | 2 | 9.09% |
Jiri Kosina | 14 | 3.67% | 1 | 4.55% |
Américo Wang | 9 | 2.36% | 1 | 4.55% |
Johannes Berg | 2 | 0.52% | 1 | 4.55% |
Total | 381 | 100.00% | 22 | 100.00% |
static inline void red_adaptative_timer(struct timer_list *t)
{
struct red_sched_data *q = from_timer(q, t, adapt_timer);
struct Qdisc *sch = q->sch;
spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch));
spin_lock(root_lock);
red_adaptative_algo(&q->parms, &q->vars);
mod_timer(&q->adapt_timer, jiffies + HZ/2);
spin_unlock(root_lock);
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Eric Dumazet | 66 | 78.57% | 2 | 66.67% |
Kees Cook | 18 | 21.43% | 1 | 33.33% |
Total | 84 | 100.00% | 3 | 100.00% |
static int red_init(struct Qdisc *sch, struct nlattr *opt)
{
struct red_sched_data *q = qdisc_priv(sch);
q->qdisc = &noop_qdisc;
q->sch = sch;
timer_setup(&q->adapt_timer, red_adaptative_timer, 0);
return red_change(sch, opt);
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Linus Torvalds (pre-git) | 22 | 37.29% | 1 | 16.67% |
Patrick McHardy | 18 | 30.51% | 2 | 33.33% |
Eric Dumazet | 10 | 16.95% | 1 | 16.67% |
Kees Cook | 8 | 13.56% | 1 | 16.67% |
David S. Miller | 1 | 1.69% | 1 | 16.67% |
Total | 59 | 100.00% | 6 | 100.00% |
static int red_dump_offload_stats(struct Qdisc *sch, struct tc_red_qopt *opt)
{
struct net_device *dev = qdisc_dev(sch);
struct tc_red_qopt_offload hw_stats = {
.command = TC_RED_STATS,
.handle = sch->handle,
.parent = sch->parent,
{
.stats.bstats = &sch->bstats,
.stats.qstats = &sch->qstats,
},
};
if (!(sch->flags & TCQ_F_OFFLOADED))
return 0;
return dev->netdev_ops->ndo_setup_tc(dev, TC_SETUP_QDISC_RED,
&hw_stats);
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Nogah Frankel | 87 | 85.29% | 1 | 33.33% |
Yuval Mintz | 8 | 7.84% | 1 | 33.33% |
Andrew Morton | 7 | 6.86% | 1 | 33.33% |
Total | 102 | 100.00% | 3 | 100.00% |
static int red_dump(struct Qdisc *sch, struct sk_buff *skb)
{
struct red_sched_data *q = qdisc_priv(sch);
struct nlattr *opts = NULL;
struct tc_red_qopt opt = {
.limit = q->limit,
.flags = q->flags,
.qth_min = q->parms.qth_min >> q->parms.Wlog,
.qth_max = q->parms.qth_max >> q->parms.Wlog,
.Wlog = q->parms.Wlog,
.Plog = q->parms.Plog,
.Scell_log = q->parms.Scell_log,
};
int err;
sch->qstats.backlog = q->qdisc->qstats.backlog;
err = red_dump_offload_stats(sch, &opt);
if (err)
goto nla_put_failure;
opts = nla_nest_start(skb, TCA_OPTIONS);
if (opts == NULL)
goto nla_put_failure;
if (nla_put(skb, TCA_RED_PARMS, sizeof(opt), &opt) ||
nla_put_u32(skb, TCA_RED_MAX_P, q->parms.max_P))
goto nla_put_failure;
return nla_nest_end(skb, opts);
nla_put_failure:
nla_nest_cancel(skb, opts);
return -EMSGSIZE;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Linus Torvalds (pre-git) | 97 | 44.91% | 2 | 16.67% |
Thomas Graf | 48 | 22.22% | 3 | 25.00% |
Eric Dumazet | 25 | 11.57% | 2 | 16.67% |
Nogah Frankel | 19 | 8.80% | 1 | 8.33% |
Patrick McHardy | 14 | 6.48% | 1 | 8.33% |
David S. Miller | 9 | 4.17% | 1 | 8.33% |
Stephen Hemminger | 3 | 1.39% | 1 | 8.33% |
Yuval Mintz | 1 | 0.46% | 1 | 8.33% |
Total | 216 | 100.00% | 12 | 100.00% |
static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
{
struct red_sched_data *q = qdisc_priv(sch);
struct net_device *dev = qdisc_dev(sch);
struct tc_red_xstats st = {
.early = q->stats.prob_drop + q->stats.forced_drop,
.pdrop = q->stats.pdrop,
.other = q->stats.other,
.marked = q->stats.prob_mark + q->stats.forced_mark,
};
if (sch->flags & TCQ_F_OFFLOADED) {
struct red_stats hw_stats = {0};
struct tc_red_qopt_offload hw_stats_request = {
.command = TC_RED_XSTATS,
.handle = sch->handle,
.parent = sch->parent,
{
.xstats = &hw_stats,
},
};
if (!dev->netdev_ops->ndo_setup_tc(dev,
TC_SETUP_QDISC_RED,
&hw_stats_request)) {
st.early += hw_stats.prob_drop + hw_stats.forced_drop;
st.pdrop += hw_stats.pdrop;
st.other += hw_stats.other;
st.marked += hw_stats.prob_mark + hw_stats.forced_mark;
}
}
return gnet_stats_copy_app(d, &st, sizeof(st));
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Nogah Frankel | 109 | 50.93% | 1 | 20.00% |
Thomas Graf | 94 | 43.93% | 2 | 40.00% |
Andrew Morton | 7 | 3.27% | 1 | 20.00% |
Yuval Mintz | 4 | 1.87% | 1 | 20.00% |
Total | 214 | 100.00% | 5 | 100.00% |
static int red_dump_class(struct Qdisc *sch, unsigned long cl,
struct sk_buff *skb, struct tcmsg *tcm)
{
struct red_sched_data *q = qdisc_priv(sch);
tcm->tcm_handle |= TC_H_MIN(1);
tcm->tcm_info = q->qdisc->handle;
return 0;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Patrick McHardy | 51 | 89.47% | 1 | 25.00% |
Linus Torvalds (pre-git) | 4 | 7.02% | 1 | 25.00% |
Al Viro | 1 | 1.75% | 1 | 25.00% |
Dave Jones | 1 | 1.75% | 1 | 25.00% |
Total | 57 | 100.00% | 4 | 100.00% |
static int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
struct Qdisc **old)
{
struct red_sched_data *q = qdisc_priv(sch);
if (new == NULL)
new = &noop_qdisc;
*old = qdisc_replace(sch, new, &q->qdisc);
return 0;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Patrick McHardy | 58 | 89.23% | 2 | 66.67% |
Américo Wang | 7 | 10.77% | 1 | 33.33% |
Total | 65 | 100.00% | 3 | 100.00% |
static struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg)
{
struct red_sched_data *q = qdisc_priv(sch);
return q->qdisc;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Patrick McHardy | 32 | 100.00% | 1 | 100.00% |
Total | 32 | 100.00% | 1 | 100.00% |
static unsigned long red_find(struct Qdisc *sch, u32 classid)
{
return 1;
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Patrick McHardy | 17 | 94.44% | 1 | 50.00% |
Américo Wang | 1 | 5.56% | 1 | 50.00% |
Total | 18 | 100.00% | 2 | 100.00% |
static void red_walk(struct Qdisc *sch, struct qdisc_walker *walker)
{
if (!walker->stop) {
if (walker->count >= walker->skip)
if (walker->fn(sch, 1, walker) < 0) {
walker->stop = 1;
return;
}
walker->count++;
}
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Patrick McHardy | 64 | 100.00% | 1 | 100.00% |
Total | 64 | 100.00% | 1 | 100.00% |
static const struct Qdisc_class_ops red_class_ops = {
.graft = red_graft,
.leaf = red_leaf,
.find = red_find,
.walk = red_walk,
.dump = red_dump_class,
};
static struct Qdisc_ops red_qdisc_ops __read_mostly = {
.id = "red",
.priv_size = sizeof(struct red_sched_data),
.cl_ops = &red_class_ops,
.enqueue = red_enqueue,
.dequeue = red_dequeue,
.peek = red_peek,
.init = red_init,
.reset = red_reset,
.destroy = red_destroy,
.change = red_change,
.dump = red_dump,
.dump_stats = red_dump_stats,
.owner = THIS_MODULE,
};
static int __init red_module_init(void)
{
return register_qdisc(&red_qdisc_ops);
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Linus Torvalds (pre-git) | 13 | 81.25% | 2 | 66.67% |
Al Viro | 3 | 18.75% | 1 | 33.33% |
Total | 16 | 100.00% | 3 | 100.00% |
static void __exit red_module_exit(void)
{
unregister_qdisc(&red_qdisc_ops);
}
Contributors
Person | Tokens | Prop | Commits | CommitProp |
Linus Torvalds (pre-git) | 12 | 80.00% | 2 | 66.67% |
Al Viro | 3 | 20.00% | 1 | 33.33% |
Total | 15 | 100.00% | 3 | 100.00% |
module_init(red_module_init)
module_exit(red_module_exit)
MODULE_LICENSE("GPL");
Overall Contributors
Person | Tokens | Prop | Commits | CommitProp |
Patrick McHardy | 615 | 26.63% | 8 | 15.09% |
Linus Torvalds (pre-git) | 443 | 19.19% | 7 | 13.21% |
Nogah Frankel | 421 | 18.23% | 2 | 3.77% |
Thomas Graf | 324 | 14.03% | 7 | 13.21% |
Eric Dumazet | 237 | 10.26% | 8 | 15.09% |
Jarek Poplawski | 55 | 2.38% | 2 | 3.77% |
Yuval Mintz | 42 | 1.82% | 1 | 1.89% |
Américo Wang | 41 | 1.78% | 4 | 7.55% |
Kees Cook | 31 | 1.34% | 1 | 1.89% |
David S. Miller | 15 | 0.65% | 2 | 3.77% |
Stephen Hemminger | 15 | 0.65% | 1 | 1.89% |
Al Viro | 15 | 0.65% | 1 | 1.89% |
Andrew Morton | 14 | 0.61% | 1 | 1.89% |
Jiri Kosina | 14 | 0.61% | 1 | 1.89% |
John Fastabend | 9 | 0.39% | 1 | 1.89% |
Dave Jones | 7 | 0.30% | 1 | 1.89% |
Linus Torvalds | 6 | 0.26% | 2 | 3.77% |
Herbert Xu | 2 | 0.09% | 1 | 1.89% |
Johannes Berg | 2 | 0.09% | 1 | 1.89% |
Jussi Kivilinna | 1 | 0.04% | 1 | 1.89% |
Total | 2309 | 100.00% | 53 | 100.00% |
Information contained on this website is for historical information purposes only and does not indicate or represent copyright ownership.