11da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds/* 21da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * net/sched/sch_red.c Random Early Detection queue. 31da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 41da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * This program is free software; you can redistribute it and/or 51da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * modify it under the terms of the GNU General Public License 61da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * as published by the Free Software Foundation; either version 71da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 2 of the License, or (at your option) any later version. 81da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 91da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> 101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * 111da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Changes: 12dba051f36a47989b20b248248ffef7984a2f6013Thomas Graf * J Hadi Salim 980914: computation fixes 131da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds * Alexey Makarenko <makar@phoenix.kharkov.ua> 990814: qave on idle link was calculated incorrectly. 14dba051f36a47989b20b248248ffef7984a2f6013Thomas Graf * J Hadi Salim 980816: ECN support 151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 161da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 171da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/module.h> 181da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/types.h> 191da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/kernel.h> 201da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <linux/skbuff.h> 211da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <net/pkt_sched.h> 221da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds#include <net/inet_ecn.h> 236b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf#include <net/red.h> 241da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 251da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 266b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf/* Parameters, settable by user: 271da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds ----------------------------- 281da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 291da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds limit - bytes (must be > qth_max + burst) 301da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 311da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds Hard limit on queue length, should be chosen >qth_max 321da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds to allow packet bursts. This parameter does not 331da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds affect the algorithms behaviour and can be chosen 341da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds arbitrarily high (well, less than ram size) 351da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds Really, this limit will never be reached 361da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds if RED works correctly. 371da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds */ 381da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 39cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstruct red_sched_data { 406b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf u32 limit; /* HARD maximal queue length */ 416b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf unsigned char flags; 428af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet struct timer_list adapt_timer; 436b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf struct red_parms parms; 44eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet struct red_vars vars; 456b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf struct red_stats stats; 46f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct Qdisc *qdisc; 471da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds}; 481da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 496b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Grafstatic inline int red_use_ecn(struct red_sched_data *q) 501da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 516b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf return q->flags & TC_RED_ECN; 521da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 531da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 54bdc450a0bb1d48144ced1f899cc8366ec8e85024Thomas Grafstatic inline int red_use_harddrop(struct red_sched_data *q) 55bdc450a0bb1d48144ced1f899cc8366ec8e85024Thomas Graf{ 56bdc450a0bb1d48144ced1f899cc8366ec8e85024Thomas Graf return q->flags & TC_RED_HARDDROP; 57bdc450a0bb1d48144ced1f899cc8366ec8e85024Thomas Graf} 58bdc450a0bb1d48144ced1f899cc8366ec8e85024Thomas Graf 59cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstatic int red_enqueue(struct sk_buff *skb, struct Qdisc *sch) 601da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 611da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct red_sched_data *q = qdisc_priv(sch); 62f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct Qdisc *child = q->qdisc; 63f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy int ret; 641da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 65eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet q->vars.qavg = red_calc_qavg(&q->parms, 66eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet &q->vars, 67eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet child->qstats.backlog); 681da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 69eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet if (red_is_idling(&q->vars)) 70eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet red_end_of_idle_period(&q->vars); 711da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 72eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet switch (red_action(&q->parms, &q->vars, q->vars.qavg)) { 73cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet case RED_DONT_MARK: 74cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet break; 75cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet 76cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet case RED_PROB_MARK: 7725331d6ce42bcf4b34b6705fce4da15c3fabe62fJohn Fastabend qdisc_qstats_overlimit(sch); 78cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet if (!red_use_ecn(q) || !INET_ECN_set_ce(skb)) { 79cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet q->stats.prob_drop++; 80cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet goto congestion_drop; 81cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet } 82cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet 83cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet q->stats.prob_mark++; 84cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet break; 85cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet 86cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet case RED_HARD_MARK: 8725331d6ce42bcf4b34b6705fce4da15c3fabe62fJohn Fastabend qdisc_qstats_overlimit(sch); 88cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet if (red_use_harddrop(q) || !red_use_ecn(q) || 89cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet !INET_ECN_set_ce(skb)) { 90cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet q->stats.forced_drop++; 91cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet goto congestion_drop; 92cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet } 93cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet 94cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet q->stats.forced_mark++; 95cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazet break; 961da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 971da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 985f86173bdf15981ca49d0434f638b68f70a35644Jussi Kivilinna ret = qdisc_enqueue(skb, child); 99f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy if (likely(ret == NET_XMIT_SUCCESS)) { 100f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy sch->q.qlen++; 101378a2f090f7a478704a372a4869b8a9ac206234eJarek Poplawski } else if (net_xmit_drop_count(ret)) { 102f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy q->stats.pdrop++; 10325331d6ce42bcf4b34b6705fce4da15c3fabe62fJohn Fastabend qdisc_qstats_drop(sch); 104f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy } 105f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy return ret; 1066b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf 1076b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Grafcongestion_drop: 1089e178ff27cd9187babe86dc80ef766b722c88da6Thomas Graf qdisc_drop(skb, sch); 1091da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return NET_XMIT_CN; 1101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1111da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 112cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstatic struct sk_buff *red_dequeue(struct Qdisc *sch) 1131da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1141da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct sk_buff *skb; 1151da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct red_sched_data *q = qdisc_priv(sch); 116f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct Qdisc *child = q->qdisc; 1171da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 118f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy skb = child->dequeue(child); 1199190b3b3208d052d98cb601fcc192f3f71a5658bEric Dumazet if (skb) { 1209190b3b3208d052d98cb601fcc192f3f71a5658bEric Dumazet qdisc_bstats_update(sch, skb); 121f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy sch->q.qlen--; 1229190b3b3208d052d98cb601fcc192f3f71a5658bEric Dumazet } else { 123eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet if (!red_is_idling(&q->vars)) 124eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet red_start_of_idle_period(&q->vars); 1259190b3b3208d052d98cb601fcc192f3f71a5658bEric Dumazet } 1269e178ff27cd9187babe86dc80ef766b722c88da6Thomas Graf return skb; 1271da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1281da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 129cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstatic struct sk_buff *red_peek(struct Qdisc *sch) 1308e3af97899db433111287e07d5105189f56fe191Jarek Poplawski{ 1318e3af97899db433111287e07d5105189f56fe191Jarek Poplawski struct red_sched_data *q = qdisc_priv(sch); 1328e3af97899db433111287e07d5105189f56fe191Jarek Poplawski struct Qdisc *child = q->qdisc; 1338e3af97899db433111287e07d5105189f56fe191Jarek Poplawski 1348e3af97899db433111287e07d5105189f56fe191Jarek Poplawski return child->ops->peek(child); 1358e3af97899db433111287e07d5105189f56fe191Jarek Poplawski} 1368e3af97899db433111287e07d5105189f56fe191Jarek Poplawski 137cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstatic unsigned int red_drop(struct Qdisc *sch) 1381da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1391da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct red_sched_data *q = qdisc_priv(sch); 140f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct Qdisc *child = q->qdisc; 141f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy unsigned int len; 1421da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 143f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy if (child->ops->drop && (len = child->ops->drop(child)) > 0) { 1446b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf q->stats.other++; 14525331d6ce42bcf4b34b6705fce4da15c3fabe62fJohn Fastabend qdisc_qstats_drop(sch); 146f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy sch->q.qlen--; 1471da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return len; 1481da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds } 1496b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf 150eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet if (!red_is_idling(&q->vars)) 151eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet red_start_of_idle_period(&q->vars); 1526a1b63d467281eb6bd64aafbbf6130a1b42c8c2eThomas Graf 1531da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return 0; 1541da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1551da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 156cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstatic void red_reset(struct Qdisc *sch) 1571da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1581da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct red_sched_data *q = qdisc_priv(sch); 1591da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 160f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy qdisc_reset(q->qdisc); 161f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy sch->q.qlen = 0; 162eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet red_restart(&q->vars); 1631da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 1641da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 165f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardystatic void red_destroy(struct Qdisc *sch) 166f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy{ 167f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct red_sched_data *q = qdisc_priv(sch); 1688af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet 1698af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet del_timer_sync(&q->adapt_timer); 170f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy qdisc_destroy(q->qdisc); 171f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy} 172f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 17327a3421e4821734bc19496faa77b380605dc3b23Patrick McHardystatic const struct nla_policy red_policy[TCA_RED_MAX + 1] = { 17427a3421e4821734bc19496faa77b380605dc3b23Patrick McHardy [TCA_RED_PARMS] = { .len = sizeof(struct tc_red_qopt) }, 17527a3421e4821734bc19496faa77b380605dc3b23Patrick McHardy [TCA_RED_STAB] = { .len = RED_STAB_SIZE }, 176a73ed26bbae7327370c5bd298f07de78df9e3466Eric Dumazet [TCA_RED_MAX_P] = { .type = NLA_U32 }, 17727a3421e4821734bc19496faa77b380605dc3b23Patrick McHardy}; 17827a3421e4821734bc19496faa77b380605dc3b23Patrick McHardy 1791e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardystatic int red_change(struct Qdisc *sch, struct nlattr *opt) 1801da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 1811da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct red_sched_data *q = qdisc_priv(sch); 1821e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy struct nlattr *tb[TCA_RED_MAX + 1]; 1831da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct tc_red_qopt *ctl; 184f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct Qdisc *child = NULL; 185cee63723b358e594225e812d6e14a2a0abfd5c88Patrick McHardy int err; 186a73ed26bbae7327370c5bd298f07de78df9e3466Eric Dumazet u32 max_P; 1871da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 188cee63723b358e594225e812d6e14a2a0abfd5c88Patrick McHardy if (opt == NULL) 189dba051f36a47989b20b248248ffef7984a2f6013Thomas Graf return -EINVAL; 190dba051f36a47989b20b248248ffef7984a2f6013Thomas Graf 19127a3421e4821734bc19496faa77b380605dc3b23Patrick McHardy err = nla_parse_nested(tb, TCA_RED_MAX, opt, red_policy); 192cee63723b358e594225e812d6e14a2a0abfd5c88Patrick McHardy if (err < 0) 193cee63723b358e594225e812d6e14a2a0abfd5c88Patrick McHardy return err; 194cee63723b358e594225e812d6e14a2a0abfd5c88Patrick McHardy 1951e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy if (tb[TCA_RED_PARMS] == NULL || 19627a3421e4821734bc19496faa77b380605dc3b23Patrick McHardy tb[TCA_RED_STAB] == NULL) 1971da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return -EINVAL; 1981da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 199a73ed26bbae7327370c5bd298f07de78df9e3466Eric Dumazet max_P = tb[TCA_RED_MAX_P] ? nla_get_u32(tb[TCA_RED_MAX_P]) : 0; 200a73ed26bbae7327370c5bd298f07de78df9e3466Eric Dumazet 2011e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy ctl = nla_data(tb[TCA_RED_PARMS]); 2021da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 203f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy if (ctl->limit > 0) { 204fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy child = fifo_create_dflt(sch, &bfifo_qdisc_ops, ctl->limit); 205fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy if (IS_ERR(child)) 206fb0305ce1b03f6ff17f84f2c63daccecb45f2805Patrick McHardy return PTR_ERR(child); 207f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy } 208f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 2091da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds sch_tree_lock(sch); 2101da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds q->flags = ctl->flags; 2111da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds q->limit = ctl->limit; 2125e50da01d0ce7ef0ba3ed6cfabd62f327da0aca6Patrick McHardy if (child) { 2135e50da01d0ce7ef0ba3ed6cfabd62f327da0aca6Patrick McHardy qdisc_tree_decrease_qlen(q->qdisc, q->qdisc->q.qlen); 214b94c8afcba3ae6584653b98e315446ea83be6ea5Patrick McHardy qdisc_destroy(q->qdisc); 215b94c8afcba3ae6584653b98e315446ea83be6ea5Patrick McHardy q->qdisc = child; 2165e50da01d0ce7ef0ba3ed6cfabd62f327da0aca6Patrick McHardy } 2171da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 218eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet red_set_parms(&q->parms, 219eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet ctl->qth_min, ctl->qth_max, ctl->Wlog, 220a73ed26bbae7327370c5bd298f07de78df9e3466Eric Dumazet ctl->Plog, ctl->Scell_log, 221a73ed26bbae7327370c5bd298f07de78df9e3466Eric Dumazet nla_data(tb[TCA_RED_STAB]), 222a73ed26bbae7327370c5bd298f07de78df9e3466Eric Dumazet max_P); 223eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet red_set_vars(&q->vars); 2246b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf 2258af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet del_timer(&q->adapt_timer); 2268af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet if (ctl->flags & TC_RED_ADAPTATIVE) 2278af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet mod_timer(&q->adapt_timer, jiffies + HZ/2); 2288af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet 2291ee5fa1e9970a16036e37c7b9d5ce81c778252fcEric Dumazet if (!q->qdisc->q.qlen) 230eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet red_start_of_idle_period(&q->vars); 231dba051f36a47989b20b248248ffef7984a2f6013Thomas Graf 2321da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds sch_tree_unlock(sch); 2331da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return 0; 2341da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2351da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2368af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazetstatic inline void red_adaptative_timer(unsigned long arg) 2378af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet{ 2388af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet struct Qdisc *sch = (struct Qdisc *)arg; 2398af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet struct red_sched_data *q = qdisc_priv(sch); 2408af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet spinlock_t *root_lock = qdisc_lock(qdisc_root_sleeping(sch)); 2418af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet 2428af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet spin_lock(root_lock); 243eeca6688d6599c28bc449a45facb67d7f203be74Eric Dumazet red_adaptative_algo(&q->parms, &q->vars); 2448af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet mod_timer(&q->adapt_timer, jiffies + HZ/2); 2458af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet spin_unlock(root_lock); 2468af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet} 2478af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet 248cc7ec456f82da7f89a5b376e613b3ac4311b3e9aEric Dumazetstatic int red_init(struct Qdisc *sch, struct nlattr *opt) 2491da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 250f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct red_sched_data *q = qdisc_priv(sch); 251f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 252f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy q->qdisc = &noop_qdisc; 2538af2a218de38f51ea4b4fa48cac1273319ae260cEric Dumazet setup_timer(&q->adapt_timer, red_adaptative_timer, (unsigned long)sch); 2541da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return red_change(sch, opt); 2551da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2561da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2571da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic int red_dump(struct Qdisc *sch, struct sk_buff *skb) 2581da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 2591da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct red_sched_data *q = qdisc_priv(sch); 2601e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy struct nlattr *opts = NULL; 2616b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf struct tc_red_qopt opt = { 2626b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .limit = q->limit, 2636b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .flags = q->flags, 2646b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .qth_min = q->parms.qth_min >> q->parms.Wlog, 2656b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .qth_max = q->parms.qth_max >> q->parms.Wlog, 2666b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .Wlog = q->parms.Wlog, 2676b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .Plog = q->parms.Plog, 2686b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .Scell_log = q->parms.Scell_log, 2696b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf }; 2701da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2710dfb33a0d7e2d9316eb4441a065ddd173f87223eEric Dumazet sch->qstats.backlog = q->qdisc->qstats.backlog; 2721e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy opts = nla_nest_start(skb, TCA_OPTIONS); 2731e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy if (opts == NULL) 2741e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy goto nla_put_failure; 2751b34ec43c9b3de44a5420841ab293d1b2035a94cDavid S. Miller if (nla_put(skb, TCA_RED_PARMS, sizeof(opt), &opt) || 2761b34ec43c9b3de44a5420841ab293d1b2035a94cDavid S. Miller nla_put_u32(skb, TCA_RED_MAX_P, q->parms.max_P)) 2771b34ec43c9b3de44a5420841ab293d1b2035a94cDavid S. Miller goto nla_put_failure; 2781e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardy return nla_nest_end(skb, opts); 2791da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2801e90474c377e92db7262a8968a45c1dd980ca9e5Patrick McHardynla_put_failure: 281bc3ed28caaef55e7e3a9316464256353c5f9b1dfThomas Graf nla_nest_cancel(skb, opts); 282bc3ed28caaef55e7e3a9316464256353c5f9b1dfThomas Graf return -EMSGSIZE; 2831da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2841da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 2851da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d) 2861da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 2871da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds struct red_sched_data *q = qdisc_priv(sch); 2886b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf struct tc_red_xstats st = { 2896b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .early = q->stats.prob_drop + q->stats.forced_drop, 2906b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .pdrop = q->stats.pdrop, 2916b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .other = q->stats.other, 2926b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf .marked = q->stats.prob_mark + q->stats.forced_mark, 2936b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf }; 2946b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf 2956b31b28a441c9ba33889f88ac1d9451ed9532adaThomas Graf return gnet_stats_copy_app(d, &st, sizeof(st)); 2961da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 2971da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 298f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardystatic int red_dump_class(struct Qdisc *sch, unsigned long cl, 299f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct sk_buff *skb, struct tcmsg *tcm) 300f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy{ 301f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct red_sched_data *q = qdisc_priv(sch); 302f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 303f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy tcm->tcm_handle |= TC_H_MIN(1); 304f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy tcm->tcm_info = q->qdisc->handle; 305f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy return 0; 306f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy} 307f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 308f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardystatic int red_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, 309f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct Qdisc **old) 310f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy{ 311f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct red_sched_data *q = qdisc_priv(sch); 312f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 313f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy if (new == NULL) 314f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy new = &noop_qdisc; 315f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 316f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy sch_tree_lock(sch); 317b94c8afcba3ae6584653b98e315446ea83be6ea5Patrick McHardy *old = q->qdisc; 318b94c8afcba3ae6584653b98e315446ea83be6ea5Patrick McHardy q->qdisc = new; 3195e50da01d0ce7ef0ba3ed6cfabd62f327da0aca6Patrick McHardy qdisc_tree_decrease_qlen(*old, (*old)->q.qlen); 320f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy qdisc_reset(*old); 321f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy sch_tree_unlock(sch); 322f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy return 0; 323f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy} 324f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 325f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardystatic struct Qdisc *red_leaf(struct Qdisc *sch, unsigned long arg) 326f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy{ 327f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy struct red_sched_data *q = qdisc_priv(sch); 328f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy return q->qdisc; 329f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy} 330f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 331f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardystatic unsigned long red_get(struct Qdisc *sch, u32 classid) 332f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy{ 333f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy return 1; 334f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy} 335f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 336f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardystatic void red_put(struct Qdisc *sch, unsigned long arg) 337f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy{ 338f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy} 339f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 340f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardystatic void red_walk(struct Qdisc *sch, struct qdisc_walker *walker) 341f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy{ 342f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy if (!walker->stop) { 343f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy if (walker->count >= walker->skip) 344f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy if (walker->fn(sch, 1, walker) < 0) { 345f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy walker->stop = 1; 346f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy return; 347f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy } 348f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy walker->count++; 349f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy } 350f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy} 351f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 35220fea08b5fb639c4c175b5c74a2bb346c5c5bc2eEric Dumazetstatic const struct Qdisc_class_ops red_class_ops = { 353f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy .graft = red_graft, 354f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy .leaf = red_leaf, 355f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy .get = red_get, 356f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy .put = red_put, 357f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy .walk = red_walk, 358f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy .dump = red_dump_class, 359f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy}; 360f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy 36120fea08b5fb639c4c175b5c74a2bb346c5c5bc2eEric Dumazetstatic struct Qdisc_ops red_qdisc_ops __read_mostly = { 3621da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .id = "red", 3631da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .priv_size = sizeof(struct red_sched_data), 364f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy .cl_ops = &red_class_ops, 3651da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .enqueue = red_enqueue, 3661da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .dequeue = red_dequeue, 3678e3af97899db433111287e07d5105189f56fe191Jarek Poplawski .peek = red_peek, 3681da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .drop = red_drop, 3691da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .init = red_init, 3701da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .reset = red_reset, 371f38c39d6ce8226519455a6dfe91c2ad84f363f6fPatrick McHardy .destroy = red_destroy, 3721da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .change = red_change, 3731da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .dump = red_dump, 3741da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .dump_stats = red_dump_stats, 3751da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds .owner = THIS_MODULE, 3761da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds}; 3771da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds 3781da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsstatic int __init red_module_init(void) 3791da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 3801da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds return register_qdisc(&red_qdisc_ops); 3811da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 382dba051f36a47989b20b248248ffef7984a2f6013Thomas Graf 383dba051f36a47989b20b248248ffef7984a2f6013Thomas Grafstatic void __exit red_module_exit(void) 3841da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds{ 3851da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds unregister_qdisc(&red_qdisc_ops); 3861da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvalds} 387dba051f36a47989b20b248248ffef7984a2f6013Thomas Graf 3881da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsmodule_init(red_module_init) 3891da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus Torvaldsmodule_exit(red_module_exit) 390dba051f36a47989b20b248248ffef7984a2f6013Thomas Graf 3911da177e4c3f41524e886b7f1b8a0c1fc7321cacLinus TorvaldsMODULE_LICENSE("GPL"); 392