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

[Eric Dumazet <eric.dumazet@gmail.com>]

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;
> +}
> +