Re: [RFC] sched: CHOKe packet scheduler (v0.4)

Eric Dumazet
2011-01-11T00:00:35Z

Le lundi 10 janvier 2011 à 15:44 -0800, Stephen Hemminger a écrit :
> This implements the CHOKe packet scheduler based on the existing
> Linux RED scheduler based on the algorithm described in the paper.
>
> The core idea is:
> For every packet arrival:
> Calculate Qave
> if (Qave < minth)
> Queue the new packet
> else
> Select randomly a packet from the queue
> if (both packets from same flow)
> then Drop both the packets
> else if (Qave > maxth)
> Drop packet
> else
> Admit packet with proability p (same as RED)
>
> See also:
> Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
> queue management scheme for approximating fair bandwidth allocation",
> Proceeding of INFOCOM'2000, March 2000.
>
> Signed-off-by: Stephen Hemminger <shemminger@vyatta.com>
>

You beat me, I found the bug I had in _change()

> +
> +static int choke_change(struct Qdisc *sch, struct nlattr *opt)
> +{
> + struct choke_sched_data *q = qdisc_priv(sch);
> + struct nlattr *tb[TCA_RED_MAX + 1];
> + struct tc_red_qopt *ctl;
> + int err;
> + struct sk_buff **old = NULL;
> + unsigned int mask;
> +
> + if (opt == NULL)
> + return -EINVAL;
> +
> + err = nla_parse_nested(tb, TCA_RED_MAX, opt, choke_policy);
> + if (err < 0)
> + return err;
> +
> + if (tb[TCA_RED_PARMS] == NULL ||
> + tb[TCA_RED_STAB] == NULL)
> + return -EINVAL;
> +
> + ctl = nla_data(tb[TCA_RED_PARMS]);
> +
> + mask = roundup_pow_of_two(ctl->limit + 1) - 1;
> + if (mask != q->tab_mask) {
> + struct sk_buff **ntab = kcalloc(mask + 1, sizeof(struct sk_buff *),
> + GFP_KERNEL);
> + if (!ntab)
> + ntab = vzalloc((mask + 1) * sizeof(struct sk_buff *));
> + if (!ntab)
> + return -ENOMEM;
> + sch_tree_lock(sch);
> + old = q->tab;
> + if (old) {
> + unsigned int tail = 0;
> +
> + while (q->head != q->tail) {
> + ntab[tail++] = q->tab[q->head];
> + q->head = (q->head + 1) & q->tab_mask;
> + }
> + q->head = 0;
> + q->tail = tail;
> + }
> + q->tab_mask = mask;

Here we missed :

q->tab = ntab;

> + q->holes = 0;
> + } else
> + sch_tree_lock(sch);
> + q->flags = ctl->flags;
> + q->limit = ctl->limit;
> +
> + red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
> + ctl->Plog, ctl->Scell_log,
> + nla_data(tb[TCA_RED_STAB]));
> +
> + if (q->head == q->tail)
> + red_end_of_idle_period(&q->parms);
> +
> + sch_tree_unlock(sch);
> + choke_free(old);
> + return 0;
> +}
> +