From 1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sat, 16 Apr 2005 15:20:36 -0700 Subject: Linux-2.6.12-rc2 Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip! --- net/sched/sch_red.c | 459 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 459 insertions(+) create mode 100644 net/sched/sch_red.c (limited to 'net/sched/sch_red.c') diff --git a/net/sched/sch_red.c b/net/sched/sch_red.c new file mode 100644 index 00000000000..664d0e47374 --- /dev/null +++ b/net/sched/sch_red.c @@ -0,0 +1,459 @@ +/* + * 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, + * + * Changes: + * J Hadi Salim 980914: computation fixes + * Alexey Makarenko 990814: qave on idle link was calculated incorrectly. + * J Hadi Salim 980816: ECN support + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + + +/* Random Early Detection (RED) algorithm. + ======================================= + + Source: Sally Floyd and Van Jacobson, "Random Early Detection Gateways + for Congestion Avoidance", 1993, IEEE/ACM Transactions on Networking. + + This file codes a "divisionless" version of RED algorithm + as written down in Fig.17 of the paper. + +Short description. +------------------ + + When a new packet arrives we calculate the average queue length: + + avg = (1-W)*avg + W*current_queue_len, + + W is the filter time constant (chosen as 2^(-Wlog)), it controls + the inertia of the algorithm. To allow larger bursts, W should be + decreased. + + if (avg > th_max) -> packet marked (dropped). + if (avg < th_min) -> packet passes. + if (th_min < avg < th_max) we calculate probability: + + Pb = max_P * (avg - th_min)/(th_max-th_min) + + and mark (drop) packet with this probability. + Pb changes from 0 (at avg==th_min) to max_P (avg==th_max). + max_P should be small (not 1), usually 0.01..0.02 is good value. + + max_P is chosen as a number, so that max_P/(th_max-th_min) + is a negative power of two in order arithmetics to contain + only shifts. + + + 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. + + qth_min - bytes (should be < qth_max/2) + qth_max - bytes (should be at least 2*qth_min and less limit) + Wlog - bits (<32) log(1/W). + Plog - bits (<32) + + Plog is related to max_P by formula: + + max_P = (qth_max-qth_min)/2^Plog; + + F.e. if qth_max=128K and qth_min=32K, then Plog=22 + corresponds to max_P=0.02 + + Scell_log + Stab + + Lookup table for log((1-W)^(t/t_ave). + + +NOTES: + +Upper bound on W. +----------------- + + If you want to allow bursts of L packets of size S, + you should choose W: + + L + 1 - th_min/S < (1-(1-W)^L)/W + + th_min/S = 32 th_min/S = 4 + + log(W) L + -1 33 + -2 35 + -3 39 + -4 46 + -5 57 + -6 75 + -7 101 + -8 135 + -9 190 + etc. + */ + +struct red_sched_data +{ +/* Parameters */ + u32 limit; /* HARD maximal queue length */ + u32 qth_min; /* Min average length threshold: A scaled */ + u32 qth_max; /* Max average length threshold: A scaled */ + u32 Rmask; + u32 Scell_max; + unsigned char flags; + char Wlog; /* log(W) */ + char Plog; /* random number bits */ + char Scell_log; + u8 Stab[256]; + +/* Variables */ + unsigned long qave; /* Average queue length: A scaled */ + int qcount; /* Packets since last random number generation */ + u32 qR; /* Cached random number */ + + psched_time_t qidlestart; /* Start of idle period */ + struct tc_red_xstats st; +}; + +static int red_ecn_mark(struct sk_buff *skb) +{ + if (skb->nh.raw + 20 > skb->tail) + return 0; + + switch (skb->protocol) { + case __constant_htons(ETH_P_IP): + if (INET_ECN_is_not_ect(skb->nh.iph->tos)) + return 0; + IP_ECN_set_ce(skb->nh.iph); + return 1; + case __constant_htons(ETH_P_IPV6): + if (INET_ECN_is_not_ect(ipv6_get_dsfield(skb->nh.ipv6h))) + return 0; + IP6_ECN_set_ce(skb->nh.ipv6h); + return 1; + default: + return 0; + } +} + +static int +red_enqueue(struct sk_buff *skb, struct Qdisc* sch) +{ + struct red_sched_data *q = qdisc_priv(sch); + + psched_time_t now; + + if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) { + long us_idle; + int shift; + + PSCHED_GET_TIME(now); + us_idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max); + PSCHED_SET_PASTPERFECT(q->qidlestart); + +/* + The problem: ideally, average length queue recalcultion should + be done over constant clock intervals. This is too expensive, so that + the calculation is driven by outgoing packets. + When the queue is idle we have to model this clock by hand. + + SF+VJ proposed to "generate" m = idletime/(average_pkt_size/bandwidth) + dummy packets as a burst after idle time, i.e. + + q->qave *= (1-W)^m + + This is an apparently overcomplicated solution (f.e. we have to precompute + a table to make this calculation in reasonable time) + I believe that a simpler model may be used here, + but it is field for experiments. +*/ + shift = q->Stab[us_idle>>q->Scell_log]; + + if (shift) { + q->qave >>= shift; + } else { + /* Approximate initial part of exponent + with linear function: + (1-W)^m ~= 1-mW + ... + + Seems, it is the best solution to + problem of too coarce exponent tabulation. + */ + + us_idle = (q->qave * us_idle)>>q->Scell_log; + if (us_idle < q->qave/2) + q->qave -= us_idle; + else + q->qave >>= 1; + } + } else { + q->qave += sch->qstats.backlog - (q->qave >> q->Wlog); + /* NOTE: + q->qave is fixed point number with point at Wlog. + The formulae above is equvalent to floating point + version: + + qave = qave*(1-W) + sch->qstats.backlog*W; + --ANK (980924) + */ + } + + if (q->qave < q->qth_min) { + q->qcount = -1; +enqueue: + if (sch->qstats.backlog + skb->len <= q->limit) { + __skb_queue_tail(&sch->q, skb); + sch->qstats.backlog += skb->len; + sch->bstats.bytes += skb->len; + sch->bstats.packets++; + return NET_XMIT_SUCCESS; + } else { + q->st.pdrop++; + } + kfree_skb(skb); + sch->qstats.drops++; + return NET_XMIT_DROP; + } + if (q->qave >= q->qth_max) { + q->qcount = -1; + sch->qstats.overlimits++; +mark: + if (!(q->flags&TC_RED_ECN) || !red_ecn_mark(skb)) { + q->st.early++; + goto drop; + } + q->st.marked++; + goto enqueue; + } + + if (++q->qcount) { + /* The formula used below causes questions. + + OK. qR is random number in the interval 0..Rmask + i.e. 0..(2^Plog). If we used floating point + arithmetics, it would be: (2^Plog)*rnd_num, + where rnd_num is less 1. + + Taking into account, that qave have fixed + point at Wlog, and Plog is related to max_P by + max_P = (qth_max-qth_min)/2^Plog; two lines + below have the following floating point equivalent: + + max_P*(qave - qth_min)/(qth_max-qth_min) < rnd/qcount + + Any questions? --ANK (980924) + */ + if (((q->qave - q->qth_min)>>q->Wlog)*q->qcount < q->qR) + goto enqueue; + q->qcount = 0; + q->qR = net_random()&q->Rmask; + sch->qstats.overlimits++; + goto mark; + } + q->qR = net_random()&q->Rmask; + goto enqueue; + +drop: + kfree_skb(skb); + sch->qstats.drops++; + return NET_XMIT_CN; +} + +static int +red_requeue(struct sk_buff *skb, struct Qdisc* sch) +{ + struct red_sched_data *q = qdisc_priv(sch); + + PSCHED_SET_PASTPERFECT(q->qidlestart); + + __skb_queue_head(&sch->q, skb); + sch->qstats.backlog += skb->len; + sch->qstats.requeues++; + return 0; +} + +static struct sk_buff * +red_dequeue(struct Qdisc* sch) +{ + struct sk_buff *skb; + struct red_sched_data *q = qdisc_priv(sch); + + skb = __skb_dequeue(&sch->q); + if (skb) { + sch->qstats.backlog -= skb->len; + return skb; + } + PSCHED_GET_TIME(q->qidlestart); + return NULL; +} + +static unsigned int red_drop(struct Qdisc* sch) +{ + struct sk_buff *skb; + struct red_sched_data *q = qdisc_priv(sch); + + skb = __skb_dequeue_tail(&sch->q); + if (skb) { + unsigned int len = skb->len; + sch->qstats.backlog -= len; + sch->qstats.drops++; + q->st.other++; + kfree_skb(skb); + return len; + } + PSCHED_GET_TIME(q->qidlestart); + return 0; +} + +static void red_reset(struct Qdisc* sch) +{ + struct red_sched_data *q = qdisc_priv(sch); + + __skb_queue_purge(&sch->q); + sch->qstats.backlog = 0; + PSCHED_SET_PASTPERFECT(q->qidlestart); + q->qave = 0; + q->qcount = -1; +} + +static int red_change(struct Qdisc *sch, struct rtattr *opt) +{ + struct red_sched_data *q = qdisc_priv(sch); + struct rtattr *tb[TCA_RED_STAB]; + struct tc_red_qopt *ctl; + + if (opt == NULL || + rtattr_parse_nested(tb, TCA_RED_STAB, opt) || + tb[TCA_RED_PARMS-1] == 0 || tb[TCA_RED_STAB-1] == 0 || + RTA_PAYLOAD(tb[TCA_RED_PARMS-1]) < sizeof(*ctl) || + RTA_PAYLOAD(tb[TCA_RED_STAB-1]) < 256) + return -EINVAL; + + ctl = RTA_DATA(tb[TCA_RED_PARMS-1]); + + sch_tree_lock(sch); + q->flags = ctl->flags; + q->Wlog = ctl->Wlog; + q->Plog = ctl->Plog; + q->Rmask = ctl->Plog < 32 ? ((1<Plog) - 1) : ~0UL; + q->Scell_log = ctl->Scell_log; + q->Scell_max = (255<Scell_log); + q->qth_min = ctl->qth_min<Wlog; + q->qth_max = ctl->qth_max<Wlog; + q->limit = ctl->limit; + memcpy(q->Stab, RTA_DATA(tb[TCA_RED_STAB-1]), 256); + + q->qcount = -1; + if (skb_queue_len(&sch->q) == 0) + PSCHED_SET_PASTPERFECT(q->qidlestart); + sch_tree_unlock(sch); + return 0; +} + +static int red_init(struct Qdisc* sch, struct rtattr *opt) +{ + return red_change(sch, opt); +} + +static int red_dump(struct Qdisc *sch, struct sk_buff *skb) +{ + struct red_sched_data *q = qdisc_priv(sch); + unsigned char *b = skb->tail; + struct rtattr *rta; + struct tc_red_qopt opt; + + rta = (struct rtattr*)b; + RTA_PUT(skb, TCA_OPTIONS, 0, NULL); + opt.limit = q->limit; + opt.qth_min = q->qth_min>>q->Wlog; + opt.qth_max = q->qth_max>>q->Wlog; + opt.Wlog = q->Wlog; + opt.Plog = q->Plog; + opt.Scell_log = q->Scell_log; + opt.flags = q->flags; + RTA_PUT(skb, TCA_RED_PARMS, sizeof(opt), &opt); + rta->rta_len = skb->tail - b; + + return skb->len; + +rtattr_failure: + skb_trim(skb, b - skb->data); + return -1; +} + +static int red_dump_stats(struct Qdisc *sch, struct gnet_dump *d) +{ + struct red_sched_data *q = qdisc_priv(sch); + + return gnet_stats_copy_app(d, &q->st, sizeof(q->st)); +} + +static struct Qdisc_ops red_qdisc_ops = { + .next = NULL, + .cl_ops = NULL, + .id = "red", + .priv_size = sizeof(struct red_sched_data), + .enqueue = red_enqueue, + .dequeue = red_dequeue, + .requeue = red_requeue, + .drop = red_drop, + .init = red_init, + .reset = red_reset, + .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); +} +static void __exit red_module_exit(void) +{ + unregister_qdisc(&red_qdisc_ops); +} +module_init(red_module_init) +module_exit(red_module_exit) +MODULE_LICENSE("GPL"); -- cgit v1.2.3