[net-next-2.6.git] / net / sched / sch_gred.c

/*
 * net/sched/sch_gred.c	Generic 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:    J Hadi Salim (hadi@cyberus.ca) 1998-2002
 *
 *             991129: -  Bug fix with grio mode
 *		       - a better sing. AvgQ mode with Grio(WRED)
 *		       - A finer grained VQ dequeue based on sugestion
 *		         from Ren Liu
 *		       - More error checks
 *
 *
 *
 *  For all the glorious comments look at Alexey's sch_red.c
 */

#include <linux/config.h>
#include <linux/module.h>
#include <asm/uaccess.h>
#include <asm/system.h>
#include <linux/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/in.h>
#include <linux/errno.h>
#include <linux/interrupt.h>
#include <linux/if_ether.h>
#include <linux/inet.h>
#include <linux/netdevice.h>
#include <linux/etherdevice.h>
#include <linux/notifier.h>
#include <net/ip.h>
#include <net/route.h>
#include <linux/skbuff.h>
#include <net/sock.h>
#include <net/pkt_sched.h>

#if 1 /* control */
#define DPRINTK(format,args...) printk(KERN_DEBUG format,##args)
#else
#define DPRINTK(format,args...)
#endif

#if 0 /* data */
#define D2PRINTK(format,args...) printk(KERN_DEBUG format,##args)
#else
#define D2PRINTK(format,args...)
#endif

#define GRED_DEF_PRIO (MAX_DPs / 2)

struct gred_sched_data;
struct gred_sched;

struct gred_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      	DP;		/* the drop pramaters */
	char		Wlog;		/* log(W)		*/
	char		Plog;		/* random number bits	*/
	u32		Scell_max;
	u32		Rmask;
	u32		bytesin;	/* bytes seen on virtualQ so far*/
	u32		packetsin;	/* packets seen on virtualQ so far*/
	u32		backlog;	/* bytes on the virtualQ */
	u32		forced;	/* packets dropped for exceeding limits */
	u32		early;	/* packets dropped as a warning */
	u32		other;	/* packets dropped by invoking drop() */
	u32		pdrop;	/* packets dropped because we exceeded physical queue limits */
	char		Scell_log;
	u8		Stab[256];
	u8              prio;        /* the prio of this vq */

/* 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	*/
};

enum {
	GRED_WRED_MODE = 1,
	GRED_RIO_MODE,
};

struct gred_sched
{
	struct gred_sched_data *tab[MAX_DPs];
	unsigned long	flags;
	u32 		DPs;   
	u32 		def; 
	u8 		initd; 
};

static inline int gred_wred_mode(struct gred_sched *table)
{
	return test_bit(GRED_WRED_MODE, &table->flags);
}

static inline void gred_enable_wred_mode(struct gred_sched *table)
{
	__set_bit(GRED_WRED_MODE, &table->flags);
}

static inline void gred_disable_wred_mode(struct gred_sched *table)
{
	__clear_bit(GRED_WRED_MODE, &table->flags);
}

static inline int gred_rio_mode(struct gred_sched *table)
{
	return test_bit(GRED_RIO_MODE, &table->flags);
}

static inline void gred_enable_rio_mode(struct gred_sched *table)
{
	__set_bit(GRED_RIO_MODE, &table->flags);
}

static inline void gred_disable_rio_mode(struct gred_sched *table)
{
	__clear_bit(GRED_RIO_MODE, &table->flags);
}

static inline int gred_wred_mode_check(struct Qdisc *sch)
{
	struct gred_sched *table = qdisc_priv(sch);
	int i;

	/* Really ugly O(n^2) but shouldn't be necessary too frequent. */
	for (i = 0; i < table->DPs; i++) {
		struct gred_sched_data *q = table->tab[i];
		int n;

		if (q == NULL)
			continue;

		for (n = 0; n < table->DPs; n++)
			if (table->tab[n] && table->tab[n] != q &&
			    table->tab[n]->prio == q->prio)
				return 1;
	}

	return 0;
}

static int
gred_enqueue(struct sk_buff *skb, struct Qdisc* sch)
{
	psched_time_t now;
	struct gred_sched_data *q=NULL;
	struct gred_sched *t= qdisc_priv(sch);
	unsigned long	qave=0;	
	int i=0;

	if (!t->initd && skb_queue_len(&sch->q) < (sch->dev->tx_queue_len ? : 1)) {
		D2PRINTK("NO GRED Queues setup yet! Enqueued anyway\n");
		goto do_enqueue;
	}


	if ( ((skb->tc_index&0xf) > (t->DPs -1)) || !(q=t->tab[skb->tc_index&0xf])) {
		printk("GRED: setting to default (%d)\n ",t->def);
		if (!(q=t->tab[t->def])) {
			DPRINTK("GRED: setting to default FAILED! dropping!! "
			    "(%d)\n ", t->def);
			goto drop;
		}
		/* fix tc_index? --could be controvesial but needed for
		   requeueing */
		skb->tc_index=(skb->tc_index&0xfffffff0) | t->def;
	}

	D2PRINTK("gred_enqueue virtualQ 0x%x classid %x backlog %d "
	    "general backlog %d\n",skb->tc_index&0xf,sch->handle,q->backlog,
	    sch->qstats.backlog);
	/* sum up all the qaves of prios <= to ours to get the new qave*/
	if (!gred_wred_mode(t) && gred_rio_mode(t)) {
		for (i=0;i<t->DPs;i++) {
			if ((!t->tab[i]) || (i==q->DP))	
				continue; 
				
			if ((t->tab[i]->prio < q->prio) && (PSCHED_IS_PASTPERFECT(t->tab[i]->qidlestart)))
				qave +=t->tab[i]->qave;
		}
			
	}

	q->packetsin++;
	q->bytesin+=skb->len;

	if (gred_wred_mode(t)) {
		qave=0;
		q->qave=t->tab[t->def]->qave;
		q->qidlestart=t->tab[t->def]->qidlestart;
	}

	if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {
		long us_idle;
		PSCHED_GET_TIME(now);
		us_idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max);
		PSCHED_SET_PASTPERFECT(q->qidlestart);

		q->qave >>= q->Stab[(us_idle>>q->Scell_log)&0xFF];
	} else {
		if (gred_wred_mode(t)) {
			q->qave += sch->qstats.backlog - (q->qave >> q->Wlog);
		} else {
			q->qave += q->backlog - (q->qave >> q->Wlog);
		}

	}
	

	if (gred_wred_mode(t))
		t->tab[t->def]->qave=q->qave;

	if ((q->qave+qave) < q->qth_min) {
		q->qcount = -1;
enqueue:
		if (q->backlog + skb->len <= q->limit) {
			q->backlog += skb->len;
do_enqueue:
			__skb_queue_tail(&sch->q, skb);
			sch->qstats.backlog += skb->len;
			sch->bstats.bytes += skb->len;
			sch->bstats.packets++;
			return 0;
		} else {
			q->pdrop++;
		}

drop:
		kfree_skb(skb);
		sch->qstats.drops++;
		return NET_XMIT_DROP;
	}
	if ((q->qave+qave) >= q->qth_max) {
		q->qcount = -1;
		sch->qstats.overlimits++;
		q->forced++;
		goto drop;
	}
	if (++q->qcount) {
		if ((((qave+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++;
		q->early++;
		goto drop;
	}
	q->qR = net_random()&q->Rmask;
	goto enqueue;
}

static int
gred_requeue(struct sk_buff *skb, struct Qdisc* sch)
{
	struct gred_sched_data *q;
	struct gred_sched *t= qdisc_priv(sch);
	q= t->tab[(skb->tc_index&0xf)];
/* error checking here -- probably unnecessary */
	PSCHED_SET_PASTPERFECT(q->qidlestart);

	__skb_queue_head(&sch->q, skb);
	sch->qstats.backlog += skb->len;
	sch->qstats.requeues++;
	q->backlog += skb->len;
	return 0;
}

static struct sk_buff *
gred_dequeue(struct Qdisc* sch)
{
	struct sk_buff *skb;
	struct gred_sched_data *q;
	struct gred_sched *t= qdisc_priv(sch);

	skb = __skb_dequeue(&sch->q);
	if (skb) {
		sch->qstats.backlog -= skb->len;
		q= t->tab[(skb->tc_index&0xf)];
		if (q) {
			q->backlog -= skb->len;
			if (!q->backlog && !gred_wred_mode(t))
				PSCHED_GET_TIME(q->qidlestart);
		} else {
			D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf); 
		}
		return skb;
	}

	if (gred_wred_mode(t)) {
			q= t->tab[t->def];
			if (!q)	
				D2PRINTK("no default VQ set: Results will be "
				       "screwed up\n");
			else
				PSCHED_GET_TIME(q->qidlestart);
	}

	return NULL;
}

static unsigned int gred_drop(struct Qdisc* sch)
{
	struct sk_buff *skb;

	struct gred_sched_data *q;
	struct gred_sched *t= qdisc_priv(sch);

	skb = __skb_dequeue_tail(&sch->q);
	if (skb) {
		unsigned int len = skb->len;
		sch->qstats.backlog -= len;
		sch->qstats.drops++;
		q= t->tab[(skb->tc_index&0xf)];
		if (q) {
			q->backlog -= len;
			q->other++;
			if (!q->backlog && !gred_wred_mode(t))
				PSCHED_GET_TIME(q->qidlestart);
		} else {
			D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf); 
		}

		kfree_skb(skb);
		return len;
	}

	q=t->tab[t->def];
	if (!q) {
		D2PRINTK("no default VQ set: Results might be screwed up\n");
		return 0;
	}

	PSCHED_GET_TIME(q->qidlestart);
	return 0;

}

static void gred_reset(struct Qdisc* sch)
{
	int i;
	struct gred_sched_data *q;
	struct gred_sched *t= qdisc_priv(sch);

	__skb_queue_purge(&sch->q);

	sch->qstats.backlog = 0;

        for (i=0;i<t->DPs;i++) {
	        q= t->tab[i];
		if (!q)	
			continue; 
		PSCHED_SET_PASTPERFECT(q->qidlestart);
		q->qave = 0;
		q->qcount = -1;
		q->backlog = 0;
		q->other=0;
		q->forced=0;
		q->pdrop=0;
		q->early=0;
	}
}

static inline void gred_destroy_vq(struct gred_sched_data *q)
{
	kfree(q);
}

static inline int gred_change_table_def(struct Qdisc *sch, struct rtattr *dps)
{
	struct gred_sched *table = qdisc_priv(sch);
	struct tc_gred_sopt *sopt;
	int i;

	if (dps == NULL || RTA_PAYLOAD(dps) < sizeof(*sopt))
		return -EINVAL;

	sopt = RTA_DATA(dps);

	if (sopt->DPs > MAX_DPs || sopt->DPs == 0 || sopt->def_DP >= sopt->DPs)
		return -EINVAL;

	sch_tree_lock(sch);
	table->DPs = sopt->DPs;
	table->def = sopt->def_DP;

	/*
	 * Every entry point to GRED is synchronized with the above code
	 * and the DP is checked against DPs, i.e. shadowed VQs can no
	 * longer be found so we can unlock right here.
	 */
	sch_tree_unlock(sch);

	if (sopt->grio) {
		gred_enable_rio_mode(table);
		gred_disable_wred_mode(table);
		if (gred_wred_mode_check(sch))
			gred_enable_wred_mode(table);
	} else {
		gred_disable_rio_mode(table);
		gred_disable_wred_mode(table);
	}

	for (i = table->DPs; i < MAX_DPs; i++) {
		if (table->tab[i]) {
			printk(KERN_WARNING "GRED: Warning: Destroying "
			       "shadowed VQ 0x%x\n", i);
			gred_destroy_vq(table->tab[i]);
			table->tab[i] = NULL;
  		}
	}

	table->initd = 0;

	return 0;
}

static inline int gred_change_vq(struct Qdisc *sch, int dp,
				 struct tc_gred_qopt *ctl, int prio, u8 *stab)
{
	struct gred_sched *table = qdisc_priv(sch);
	struct gred_sched_data *q;

	if (table->tab[dp] == NULL) {
		table->tab[dp] = kmalloc(sizeof(*q), GFP_KERNEL);
		if (table->tab[dp] == NULL)
			return -ENOMEM;
		memset(table->tab[dp], 0, sizeof(*q));
	}

	q = table->tab[dp];
	q->DP = dp;
	q->prio = prio;

	q->Wlog = ctl->Wlog;
	q->Plog = ctl->Plog;
	q->limit = ctl->limit;
	q->Scell_log = ctl->Scell_log;
 	q->Rmask = ctl->Plog < 32 ? ((1<<ctl->Plog) - 1) : ~0UL;
 	q->Scell_max = (255<<q->Scell_log);
 	q->qth_min = ctl->qth_min<<ctl->Wlog;
 	q->qth_max = ctl->qth_max<<ctl->Wlog;
 	q->qave=0;
 	q->backlog=0;
 	q->qcount = -1;
 	q->other=0;
 	q->forced=0;
 	q->pdrop=0;
	q->early=0;

	PSCHED_SET_PASTPERFECT(q->qidlestart);
	memcpy(q->Stab, stab, 256);

	return 0;
}

static int gred_change(struct Qdisc *sch, struct rtattr *opt)
{
	struct gred_sched *table = qdisc_priv(sch);
	struct tc_gred_qopt *ctl;
	struct rtattr *tb[TCA_GRED_MAX];
	int err = -EINVAL, prio = GRED_DEF_PRIO;
	u8 *stab;

	if (opt == NULL || rtattr_parse_nested(tb, TCA_GRED_MAX, opt))
		return -EINVAL;

	if (tb[TCA_GRED_PARMS-1] == NULL && tb[TCA_GRED_STAB-1] == NULL)
		return gred_change_table_def(sch, opt);

	if (tb[TCA_GRED_PARMS-1] == NULL ||
	    RTA_PAYLOAD(tb[TCA_GRED_PARMS-1]) < sizeof(*ctl) ||
	    tb[TCA_GRED_STAB-1] == NULL ||
	    RTA_PAYLOAD(tb[TCA_GRED_STAB-1]) < 256)
		return -EINVAL;

	ctl = RTA_DATA(tb[TCA_GRED_PARMS-1]);
	stab = RTA_DATA(tb[TCA_GRED_STAB-1]);

	if (ctl->DP >= table->DPs)
		goto errout;

	if (gred_rio_mode(table)) {
		if (ctl->prio == 0) {
			int def_prio = GRED_DEF_PRIO;

			if (table->tab[table->def])
				def_prio = table->tab[table->def]->prio;

			printk(KERN_DEBUG "GRED: DP %u does not have a prio "
			       "setting default to %d\n", ctl->DP, def_prio);

			prio = def_prio;
		} else
			prio = ctl->prio;
	}

	sch_tree_lock(sch);

	err = gred_change_vq(sch, ctl->DP, ctl, prio, stab);
	if (err < 0)
		goto errout_locked;

	if (table->tab[table->def] == NULL) {
		if (gred_rio_mode(table))
			prio = table->tab[ctl->DP]->prio;

		err = gred_change_vq(sch, table->def, ctl, prio, stab);
		if (err < 0)
			goto errout_locked;
	}

	table->initd = 1;

	if (gred_rio_mode(table)) {
		gred_disable_wred_mode(table);
		if (gred_wred_mode_check(sch))
			gred_enable_wred_mode(table);
	}

	err = 0;

errout_locked:
	sch_tree_unlock(sch);
errout:
	return err;
}

static int gred_init(struct Qdisc *sch, struct rtattr *opt)
{
	struct rtattr *tb[TCA_GRED_MAX];

	if (opt == NULL || rtattr_parse_nested(tb, TCA_GRED_MAX, opt))
		return -EINVAL;

	if (tb[TCA_GRED_PARMS-1] || tb[TCA_GRED_STAB-1])
		return -EINVAL;

	return gred_change_table_def(sch, tb[TCA_GRED_DPS-1]);
}

static int gred_dump(struct Qdisc *sch, struct sk_buff *skb)
{
	struct gred_sched *table = qdisc_priv(sch);
	struct rtattr *parms, *opts = NULL;
	int i;
	struct tc_gred_sopt sopt = {
		.DPs	= table->DPs,
		.def_DP	= table->def,
		.grio	= gred_rio_mode(table),
	};

	opts = RTA_NEST(skb, TCA_OPTIONS);
	RTA_PUT(skb, TCA_GRED_DPS, sizeof(sopt), &sopt);
	parms = RTA_NEST(skb, TCA_GRED_PARMS);

	for (i = 0; i < MAX_DPs; i++) {
		struct gred_sched_data *q = table->tab[i];
		struct tc_gred_qopt opt;

		memset(&opt, 0, sizeof(opt));

		if (!q) {
			/* hack -- fix at some point with proper message
			   This is how we indicate to tc that there is no VQ
			   at this DP */

			opt.DP = MAX_DPs + i;
			goto append_opt;
		}

		opt.limit	= q->limit;
		opt.DP		= q->DP;
		opt.backlog	= q->backlog;
		opt.prio	= q->prio;
		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.other	= q->other;
		opt.early	= q->early;
		opt.forced	= q->forced;
		opt.pdrop	= q->pdrop;
		opt.packets	= q->packetsin;
		opt.bytesin	= q->bytesin;

		if (q->qave) {
			if (gred_wred_mode(table)) {
				q->qidlestart=table->tab[table->def]->qidlestart;
				q->qave=table->tab[table->def]->qave;
			}
			if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {
				long idle;
				unsigned long qave;
				psched_time_t now;
				PSCHED_GET_TIME(now);
				idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max);
				qave  = q->qave >> q->Stab[(idle>>q->Scell_log)&0xFF];
				opt.qave = qave >> q->Wlog;

			} else {
				opt.qave = q->qave >> q->Wlog;
			}
		}

append_opt:
		RTA_APPEND(skb, sizeof(opt), &opt);
	}

	RTA_NEST_END(skb, parms);

	return RTA_NEST_END(skb, opts);

rtattr_failure:
	return RTA_NEST_CANCEL(skb, opts);
}

static void gred_destroy(struct Qdisc *sch)
{
	struct gred_sched *table = qdisc_priv(sch);
	int i;

	for (i = 0;i < table->DPs; i++) {
		if (table->tab[i])
			gred_destroy_vq(table->tab[i]);
	}
}

static struct Qdisc_ops gred_qdisc_ops = {
	.next		=	NULL,
	.cl_ops		=	NULL,
	.id		=	"gred",
	.priv_size	=	sizeof(struct gred_sched),
	.enqueue	=	gred_enqueue,
	.dequeue	=	gred_dequeue,
	.requeue	=	gred_requeue,
	.drop		=	gred_drop,
	.init		=	gred_init,
	.reset		=	gred_reset,
	.destroy	=	gred_destroy,
	.change		=	gred_change,
	.dump		=	gred_dump,
	.owner		=	THIS_MODULE,
};

static int __init gred_module_init(void)
{
	return register_qdisc(&gred_qdisc_ops);
}
static void __exit gred_module_exit(void) 
{
	unregister_qdisc(&gred_qdisc_ops);
}
module_init(gred_module_init)
module_exit(gred_module_exit)
MODULE_LICENSE("GPL");
Commit	Line	Data
1da177e4 LT	1	/*
	2	* net/sched/sch_gred.c Generic Random Early Detection queue.
	3	*
	4	*
	5	* This program is free software; you can redistribute it and/or
	6	* modify it under the terms of the GNU General Public License
	7	* as published by the Free Software Foundation; either version
	8	* 2 of the License, or (at your option) any later version.
	9	*
	10	* Authors: J Hadi Salim (hadi@cyberus.ca) 1998-2002
	11	*
	12	* 991129: - Bug fix with grio mode
	13	* - a better sing. AvgQ mode with Grio(WRED)
	14	* - A finer grained VQ dequeue based on sugestion
	15	* from Ren Liu
	16	* - More error checks
	17	*
	18	*
	19	*
	20	* For all the glorious comments look at Alexey's sch_red.c
	21	*/
	22
	23	#include <linux/config.h>
	24	#include <linux/module.h>
	25	#include <asm/uaccess.h>
	26	#include <asm/system.h>
	27	#include <linux/bitops.h>
	28	#include <linux/types.h>
	29	#include <linux/kernel.h>
	30	#include <linux/sched.h>
	31	#include <linux/string.h>
	32	#include <linux/mm.h>
	33	#include <linux/socket.h>
	34	#include <linux/sockios.h>
	35	#include <linux/in.h>
	36	#include <linux/errno.h>
	37	#include <linux/interrupt.h>
	38	#include <linux/if_ether.h>
	39	#include <linux/inet.h>
	40	#include <linux/netdevice.h>
	41	#include <linux/etherdevice.h>
	42	#include <linux/notifier.h>
	43	#include <net/ip.h>
	44	#include <net/route.h>
	45	#include <linux/skbuff.h>
	46	#include <net/sock.h>
	47	#include <net/pkt_sched.h>
	48
	49	#if 1 /* control */
	50	#define DPRINTK(format,args...) printk(KERN_DEBUG format,##args)
	51	#else
	52	#define DPRINTK(format,args...)
	53	#endif
	54
	55	#if 0 /* data */
	56	#define D2PRINTK(format,args...) printk(KERN_DEBUG format,##args)
	57	#else
	58	#define D2PRINTK(format,args...)
	59	#endif
	60
f62d6b93 TG	61	#define GRED_DEF_PRIO (MAX_DPs / 2)
f62d6b93 TG	62
1da177e4 LT	63	struct gred_sched_data;
	64	struct gred_sched;
	65
	66	struct gred_sched_data
	67	{
	68	/* Parameters */
	69	u32 limit; /* HARD maximal queue length */
	70	u32 qth_min; /* Min average length threshold: A scaled */
	71	u32 qth_max; /* Max average length threshold: A scaled */
	72	u32 DP; /* the drop pramaters */
	73	char Wlog; /* log(W) */
	74	char Plog; /* random number bits */
	75	u32 Scell_max;
	76	u32 Rmask;
	77	u32 bytesin; /* bytes seen on virtualQ so far*/
	78	u32 packetsin; /* packets seen on virtualQ so far*/
	79	u32 backlog; /* bytes on the virtualQ */
	80	u32 forced; /* packets dropped for exceeding limits */
	81	u32 early; /* packets dropped as a warning */
	82	u32 other; /* packets dropped by invoking drop() */
	83	u32 pdrop; /* packets dropped because we exceeded physical queue limits */
	84	char Scell_log;
	85	u8 Stab[256];
	86	u8 prio; /* the prio of this vq */
	87
	88	/* Variables */
	89	unsigned long qave; /* Average queue length: A scaled */
	90	int qcount; /* Packets since last random number generation */
	91	u32 qR; /* Cached random number */
	92
	93	psched_time_t qidlestart; /* Start of idle period */
	94	};
	95
dea3f628 TG	96	enum {
dea3f628 TG	97	GRED_WRED_MODE = 1,
d6fd4e96	98	GRED_RIO_MODE,
dea3f628 TG	99	};
dea3f628 TG	100
1da177e4 LT	101	struct gred_sched
	102	{
	103	struct gred_sched_data *tab[MAX_DPs];
dea3f628	104	unsigned long flags;
1da177e4 LT	105	u32 DPs;
	106	u32 def;
	107	u8 initd;
1da177e4 LT	108	};
1da177e4 LT	109
dea3f628 TG	110	static inline int gred_wred_mode(struct gred_sched *table)
	111	{
	112	return test_bit(GRED_WRED_MODE, &table->flags);
	113	}
	114
	115	static inline void gred_enable_wred_mode(struct gred_sched *table)
	116	{
	117	__set_bit(GRED_WRED_MODE, &table->flags);
	118	}
	119
	120	static inline void gred_disable_wred_mode(struct gred_sched *table)
	121	{
	122	__clear_bit(GRED_WRED_MODE, &table->flags);
	123	}
	124
d6fd4e96 TG	125	static inline int gred_rio_mode(struct gred_sched *table)
	126	{
	127	return test_bit(GRED_RIO_MODE, &table->flags);
	128	}
	129
	130	static inline void gred_enable_rio_mode(struct gred_sched *table)
	131	{
	132	__set_bit(GRED_RIO_MODE, &table->flags);
	133	}
	134
	135	static inline void gred_disable_rio_mode(struct gred_sched *table)
	136	{
	137	__clear_bit(GRED_RIO_MODE, &table->flags);
	138	}
	139
dea3f628 TG	140	static inline int gred_wred_mode_check(struct Qdisc *sch)
	141	{
	142	struct gred_sched *table = qdisc_priv(sch);
	143	int i;
	144
	145	/* Really ugly O(n^2) but shouldn't be necessary too frequent. */
	146	for (i = 0; i < table->DPs; i++) {
	147	struct gred_sched_data *q = table->tab[i];
	148	int n;
	149
	150	if (q == NULL)
	151	continue;
	152
	153	for (n = 0; n < table->DPs; n++)
	154	if (table->tab[n] && table->tab[n] != q &&
	155	table->tab[n]->prio == q->prio)
	156	return 1;
	157	}
	158
	159	return 0;
	160	}
	161
1da177e4 LT	162	static int
	163	gred_enqueue(struct sk_buff skb, struct Qdisc sch)
	164	{
	165	psched_time_t now;
	166	struct gred_sched_data *q=NULL;
	167	struct gred_sched *t= qdisc_priv(sch);
	168	unsigned long qave=0;
	169	int i=0;
	170
	171	if (!t->initd && skb_queue_len(&sch->q) < (sch->dev->tx_queue_len ? : 1)) {
	172	D2PRINTK("NO GRED Queues setup yet! Enqueued anyway\n");
	173	goto do_enqueue;
	174	}
	175
	176
	177	if ( ((skb->tc_index&0xf) > (t->DPs -1)) \|\| !(q=t->tab[skb->tc_index&0xf])) {
	178	printk("GRED: setting to default (%d)\n ",t->def);
	179	if (!(q=t->tab[t->def])) {
	180	DPRINTK("GRED: setting to default FAILED! dropping!! "
	181	"(%d)\n ", t->def);
	182	goto drop;
	183	}
	184	/* fix tc_index? --could be controvesial but needed for
	185	requeueing */
	186	skb->tc_index=(skb->tc_index&0xfffffff0) \| t->def;
	187	}
	188
	189	D2PRINTK("gred_enqueue virtualQ 0x%x classid %x backlog %d "
	190	"general backlog %d\n",skb->tc_index&0xf,sch->handle,q->backlog,
	191	sch->qstats.backlog);
	192	/* sum up all the qaves of prios <= to ours to get the new qave*/
d6fd4e96	193	if (!gred_wred_mode(t) && gred_rio_mode(t)) {
1da177e4 LT	194	for (i=0;i<t->DPs;i++) {
	195	if ((!t->tab[i]) \|\| (i==q->DP))
	196	continue;
	197
	198	if ((t->tab[i]->prio < q->prio) && (PSCHED_IS_PASTPERFECT(t->tab[i]->qidlestart)))
	199	qave +=t->tab[i]->qave;
	200	}
	201
	202	}
	203
	204	q->packetsin++;
	205	q->bytesin+=skb->len;
	206
dea3f628	207	if (gred_wred_mode(t)) {
1da177e4 LT	208	qave=0;
	209	q->qave=t->tab[t->def]->qave;
	210	q->qidlestart=t->tab[t->def]->qidlestart;
	211	}
	212
	213	if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {
	214	long us_idle;
	215	PSCHED_GET_TIME(now);
	216	us_idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max);
	217	PSCHED_SET_PASTPERFECT(q->qidlestart);
	218
	219	q->qave >>= q->Stab[(us_idle>>q->Scell_log)&0xFF];
	220	} else {
dea3f628	221	if (gred_wred_mode(t)) {
1da177e4 LT	222	q->qave += sch->qstats.backlog - (q->qave >> q->Wlog);
	223	} else {
	224	q->qave += q->backlog - (q->qave >> q->Wlog);
	225	}
	226
	227	}
	228
	229
dea3f628	230	if (gred_wred_mode(t))
1da177e4 LT	231	t->tab[t->def]->qave=q->qave;
	232
	233	if ((q->qave+qave) < q->qth_min) {
	234	q->qcount = -1;
	235	enqueue:
	236	if (q->backlog + skb->len <= q->limit) {
	237	q->backlog += skb->len;
	238	do_enqueue:
	239	__skb_queue_tail(&sch->q, skb);
	240	sch->qstats.backlog += skb->len;
	241	sch->bstats.bytes += skb->len;
	242	sch->bstats.packets++;
	243	return 0;
	244	} else {
	245	q->pdrop++;
	246	}
	247
	248	drop:
	249	kfree_skb(skb);
	250	sch->qstats.drops++;
	251	return NET_XMIT_DROP;
	252	}
	253	if ((q->qave+qave) >= q->qth_max) {
	254	q->qcount = -1;
	255	sch->qstats.overlimits++;
	256	q->forced++;
	257	goto drop;
	258	}
	259	if (++q->qcount) {
	260	if ((((qave+q->qave) - q->qth_min)>>q->Wlog)*q->qcount < q->qR)
	261	goto enqueue;
	262	q->qcount = 0;
	263	q->qR = net_random()&q->Rmask;
	264	sch->qstats.overlimits++;
	265	q->early++;
	266	goto drop;
	267	}
	268	q->qR = net_random()&q->Rmask;
	269	goto enqueue;
	270	}
	271
	272	static int
	273	gred_requeue(struct sk_buff skb, struct Qdisc sch)
	274	{
	275	struct gred_sched_data *q;
	276	struct gred_sched *t= qdisc_priv(sch);
	277	q= t->tab[(skb->tc_index&0xf)];
	278	/* error checking here -- probably unnecessary */
	279	PSCHED_SET_PASTPERFECT(q->qidlestart);
	280
	281	__skb_queue_head(&sch->q, skb);
	282	sch->qstats.backlog += skb->len;
	283	sch->qstats.requeues++;
	284	q->backlog += skb->len;
	285	return 0;
	286	}
	287
	288	static struct sk_buff *
	289	gred_dequeue(struct Qdisc* sch)
	290	{
	291	struct sk_buff *skb;
	292	struct gred_sched_data *q;
	293	struct gred_sched *t= qdisc_priv(sch);
	294
295	skb = __skb_dequeue(&sch->q);
296	if (skb) {
297	sch->qstats.backlog -= skb->len;
298	q= t->tab[(skb->tc_index&0xf)];
299	if (q) {
300	q->backlog -= skb->len;
dea3f628	301	if (!q->backlog && !gred_wred_mode(t))
1da177e4 LT	302	PSCHED_GET_TIME(q->qidlestart);
	303	} else {
	304	D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
	305	}
	306	return skb;
	307	}
	308
dea3f628	309	if (gred_wred_mode(t)) {
1da177e4 LT	310	q= t->tab[t->def];
	311	if (!q)
	312	D2PRINTK("no default VQ set: Results will be "
	313	"screwed up\n");
	314	else
	315	PSCHED_GET_TIME(q->qidlestart);
	316	}
	317
	318	return NULL;
	319	}
	320
	321	static unsigned int gred_drop(struct Qdisc* sch)
	322	{
	323	struct sk_buff *skb;
	324
	325	struct gred_sched_data *q;
	326	struct gred_sched *t= qdisc_priv(sch);
	327
	328	skb = __skb_dequeue_tail(&sch->q);
	329	if (skb) {
	330	unsigned int len = skb->len;
	331	sch->qstats.backlog -= len;
	332	sch->qstats.drops++;
	333	q= t->tab[(skb->tc_index&0xf)];
	334	if (q) {
	335	q->backlog -= len;
	336	q->other++;
dea3f628	337	if (!q->backlog && !gred_wred_mode(t))
1da177e4 LT	338	PSCHED_GET_TIME(q->qidlestart);
	339	} else {
	340	D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
	341	}
	342
	343	kfree_skb(skb);
	344	return len;
	345	}
	346
	347	q=t->tab[t->def];
	348	if (!q) {
	349	D2PRINTK("no default VQ set: Results might be screwed up\n");
	350	return 0;
	351	}
	352
	353	PSCHED_GET_TIME(q->qidlestart);
	354	return 0;
	355
	356	}
	357
	358	static void gred_reset(struct Qdisc* sch)
	359	{
	360	int i;
	361	struct gred_sched_data *q;
	362	struct gred_sched *t= qdisc_priv(sch);
	363
	364	__skb_queue_purge(&sch->q);
	365
	366	sch->qstats.backlog = 0;
	367
	368	for (i=0;i<t->DPs;i++) {
	369	q= t->tab[i];
	370	if (!q)
	371	continue;
	372	PSCHED_SET_PASTPERFECT(q->qidlestart);
	373	q->qave = 0;
	374	q->qcount = -1;
	375	q->backlog = 0;
	376	q->other=0;
	377	q->forced=0;
	378	q->pdrop=0;
	379	q->early=0;
	380	}
	381	}
	382
6639607e TG	383	static inline void gred_destroy_vq(struct gred_sched_data *q)
	384	{
	385	kfree(q);
	386	}
	387
	388	static inline int gred_change_table_def(struct Qdisc sch, struct rtattr dps)
1da177e4 LT	389	{
1da177e4 LT	390	struct gred_sched *table = qdisc_priv(sch);
1da177e4	391	struct tc_gred_sopt *sopt;
6639607e	392	int i;
1da177e4	393
6639607e	394	if (dps == NULL \|\| RTA_PAYLOAD(dps) < sizeof(*sopt))
1da177e4 LT	395	return -EINVAL;
1da177e4 LT	396
6639607e	397	sopt = RTA_DATA(dps);
1da177e4	398
6639607e TG	399	if (sopt->DPs > MAX_DPs \|\| sopt->DPs == 0 \|\| sopt->def_DP >= sopt->DPs)
6639607e TG	400	return -EINVAL;
1da177e4	401
6639607e TG	402	sch_tree_lock(sch);
	403	table->DPs = sopt->DPs;
	404	table->def = sopt->def_DP;
dea3f628	405
6639607e TG	406	/*
	407	* Every entry point to GRED is synchronized with the above code
	408	* and the DP is checked against DPs, i.e. shadowed VQs can no
	409	* longer be found so we can unlock right here.
	410	*/
	411	sch_tree_unlock(sch);
dea3f628	412
6639607e TG	413	if (sopt->grio) {
	414	gred_enable_rio_mode(table);
	415	gred_disable_wred_mode(table);
	416	if (gred_wred_mode_check(sch))
	417	gred_enable_wred_mode(table);
	418	} else {
	419	gred_disable_rio_mode(table);
	420	gred_disable_wred_mode(table);
	421	}
	422
	423	for (i = table->DPs; i < MAX_DPs; i++) {
	424	if (table->tab[i]) {
	425	printk(KERN_WARNING "GRED: Warning: Destroying "
	426	"shadowed VQ 0x%x\n", i);
	427	gred_destroy_vq(table->tab[i]);
	428	table->tab[i] = NULL;
	429	}
	430	}
1da177e4	431
6639607e TG	432	table->initd = 0;
	433
	434	return 0;
	435	}
	436
f62d6b93 TG	437	static inline int gred_change_vq(struct Qdisc *sch, int dp,
f62d6b93 TG	438	struct tc_gred_qopt ctl, int prio, u8 stab)
6639607e TG	439	{
	440	struct gred_sched *table = qdisc_priv(sch);
	441	struct gred_sched_data *q;
f62d6b93 TG	442
	443	if (table->tab[dp] == NULL) {
	444	table->tab[dp] = kmalloc(sizeof(*q), GFP_KERNEL);
	445	if (table->tab[dp] == NULL)
	446	return -ENOMEM;
	447	memset(table->tab[dp], 0, sizeof(*q));
	448	}
	449
	450	q = table->tab[dp];
	451	q->DP = dp;
	452	q->prio = prio;
	453
	454	q->Wlog = ctl->Wlog;
	455	q->Plog = ctl->Plog;
	456	q->limit = ctl->limit;
	457	q->Scell_log = ctl->Scell_log;
	458	q->Rmask = ctl->Plog < 32 ? ((1<<ctl->Plog) - 1) : ~0UL;
	459	q->Scell_max = (255<<q->Scell_log);
	460	q->qth_min = ctl->qth_min<<ctl->Wlog;
	461	q->qth_max = ctl->qth_max<<ctl->Wlog;
	462	q->qave=0;
	463	q->backlog=0;
	464	q->qcount = -1;
	465	q->other=0;
	466	q->forced=0;
	467	q->pdrop=0;
	468	q->early=0;
	469
	470	PSCHED_SET_PASTPERFECT(q->qidlestart);
	471	memcpy(q->Stab, stab, 256);
	472
	473	return 0;
	474	}
	475
	476	static int gred_change(struct Qdisc sch, struct rtattr opt)
	477	{
	478	struct gred_sched *table = qdisc_priv(sch);
6639607e	479	struct tc_gred_qopt *ctl;
f62d6b93 TG	480	struct rtattr *tb[TCA_GRED_MAX];
	481	int err = -EINVAL, prio = GRED_DEF_PRIO;
	482	u8 *stab;
6639607e	483
f62d6b93	484	if (opt == NULL \|\| rtattr_parse_nested(tb, TCA_GRED_MAX, opt))
6639607e TG	485	return -EINVAL;
	486
	487	if (tb[TCA_GRED_PARMS-1] == NULL && tb[TCA_GRED_STAB-1] == NULL)
f62d6b93	488	return gred_change_table_def(sch, opt);
1da177e4	489
f62d6b93 TG	490	if (tb[TCA_GRED_PARMS-1] == NULL \|\|
	491	RTA_PAYLOAD(tb[TCA_GRED_PARMS-1]) < sizeof(*ctl) \|\|
	492	tb[TCA_GRED_STAB-1] == NULL \|\|
	493	RTA_PAYLOAD(tb[TCA_GRED_STAB-1]) < 256)
	494	return -EINVAL;
1da177e4 LT	495
1da177e4 LT	496	ctl = RTA_DATA(tb[TCA_GRED_PARMS-1]);
f62d6b93	497	stab = RTA_DATA(tb[TCA_GRED_STAB-1]);
a8aaa995 TG	498
a8aaa995 TG	499	if (ctl->DP >= table->DPs)
f62d6b93	500	goto errout;
1da177e4	501
d6fd4e96	502	if (gred_rio_mode(table)) {
f62d6b93 TG	503	if (ctl->prio == 0) {
	504	int def_prio = GRED_DEF_PRIO;
	505
	506	if (table->tab[table->def])
	507	def_prio = table->tab[table->def]->prio;
	508
	509	printk(KERN_DEBUG "GRED: DP %u does not have a prio "
	510	"setting default to %d\n", ctl->DP, def_prio);
	511
	512	prio = def_prio;
	513	} else
	514	prio = ctl->prio;
1da177e4 LT	515	}
1da177e4 LT	516
f62d6b93	517	sch_tree_lock(sch);
1da177e4	518
f62d6b93 TG	519	err = gred_change_vq(sch, ctl->DP, ctl, prio, stab);
	520	if (err < 0)
	521	goto errout_locked;
1da177e4	522
f62d6b93 TG	523	if (table->tab[table->def] == NULL) {
	524	if (gred_rio_mode(table))
	525	prio = table->tab[ctl->DP]->prio;
	526
	527	err = gred_change_vq(sch, table->def, ctl, prio, stab);
	528	if (err < 0)
	529	goto errout_locked;
	530	}
	531
	532	table->initd = 1;
1da177e4	533
d6fd4e96	534	if (gred_rio_mode(table)) {
dea3f628 TG	535	gred_disable_wred_mode(table);
	536	if (gred_wred_mode_check(sch))
	537	gred_enable_wred_mode(table);
1da177e4 LT	538	}
1da177e4 LT	539
f62d6b93	540	err = 0;
1da177e4	541
f62d6b93 TG	542	errout_locked:
	543	sch_tree_unlock(sch);
	544	errout:
	545	return err;
1da177e4 LT	546	}
	547
	548	static int gred_init(struct Qdisc sch, struct rtattr opt)
	549	{
6639607e	550	struct rtattr *tb[TCA_GRED_MAX];
1da177e4	551
6639607e	552	if (opt == NULL \|\| rtattr_parse_nested(tb, TCA_GRED_MAX, opt))
1da177e4 LT	553	return -EINVAL;
1da177e4 LT	554
6639607e TG	555	if (tb[TCA_GRED_PARMS-1] \|\| tb[TCA_GRED_STAB-1])
6639607e TG	556	return -EINVAL;
1da177e4	557
6639607e	558	return gred_change_table_def(sch, tb[TCA_GRED_DPS-1]);
1da177e4 LT	559	}
	560
	561	static int gred_dump(struct Qdisc sch, struct sk_buff skb)
	562	{
1da177e4	563	struct gred_sched *table = qdisc_priv(sch);
05f1cc01	564	struct rtattr parms, opts = NULL;
1da177e4	565	int i;
e0636822 TG	566	struct tc_gred_sopt sopt = {
	567	.DPs = table->DPs,
	568	.def_DP = table->def,
	569	.grio = gred_rio_mode(table),
	570	};
1da177e4	571
05f1cc01	572	opts = RTA_NEST(skb, TCA_OPTIONS);
e0636822	573	RTA_PUT(skb, TCA_GRED_DPS, sizeof(sopt), &sopt);
05f1cc01	574	parms = RTA_NEST(skb, TCA_GRED_PARMS);
1da177e4	575
05f1cc01 TG	576	for (i = 0; i < MAX_DPs; i++) {
	577	struct gred_sched_data *q = table->tab[i];
	578	struct tc_gred_qopt opt;
1da177e4	579
05f1cc01	580	memset(&opt, 0, sizeof(opt));
1da177e4 LT	581
	582	if (!q) {
	583	/* hack -- fix at some point with proper message
	584	This is how we indicate to tc that there is no VQ
	585	at this DP */
	586
05f1cc01 TG	587	opt.DP = MAX_DPs + i;
05f1cc01 TG	588	goto append_opt;
1da177e4 LT	589	}
1da177e4 LT	590
05f1cc01 TG	591	opt.limit = q->limit;
	592	opt.DP = q->DP;
	593	opt.backlog = q->backlog;
	594	opt.prio = q->prio;
	595	opt.qth_min = q->qth_min >> q->Wlog;
	596	opt.qth_max = q->qth_max >> q->Wlog;
	597	opt.Wlog = q->Wlog;
	598	opt.Plog = q->Plog;
	599	opt.Scell_log = q->Scell_log;
	600	opt.other = q->other;
	601	opt.early = q->early;
	602	opt.forced = q->forced;
	603	opt.pdrop = q->pdrop;
	604	opt.packets = q->packetsin;
	605	opt.bytesin = q->bytesin;
	606
1da177e4	607	if (q->qave) {
dea3f628	608	if (gred_wred_mode(table)) {
1da177e4 LT	609	q->qidlestart=table->tab[table->def]->qidlestart;
	610	q->qave=table->tab[table->def]->qave;
	611	}
	612	if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {
	613	long idle;
05f1cc01	614	unsigned long qave;
1da177e4 LT	615	psched_time_t now;
	616	PSCHED_GET_TIME(now);
	617	idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max);
	618	qave = q->qave >> q->Stab[(idle>>q->Scell_log)&0xFF];
05f1cc01	619	opt.qave = qave >> q->Wlog;
1da177e4 LT	620
1da177e4 LT	621	} else {
05f1cc01	622	opt.qave = q->qave >> q->Wlog;
1da177e4	623	}
1da177e4	624	}
05f1cc01 TG	625
	626	append_opt:
	627	RTA_APPEND(skb, sizeof(opt), &opt);
1da177e4 LT	628	}
1da177e4 LT	629
05f1cc01	630	RTA_NEST_END(skb, parms);
1da177e4	631
05f1cc01	632	return RTA_NEST_END(skb, opts);
1da177e4 LT	633
1da177e4 LT	634	rtattr_failure:
05f1cc01	635	return RTA_NEST_CANCEL(skb, opts);
1da177e4 LT	636	}
	637
	638	static void gred_destroy(struct Qdisc *sch)
	639	{
	640	struct gred_sched *table = qdisc_priv(sch);
	641	int i;
	642
	643	for (i = 0;i < table->DPs; i++) {
	644	if (table->tab[i])
6639607e	645	gred_destroy_vq(table->tab[i]);
1da177e4 LT	646	}
	647	}
	648
	649	static struct Qdisc_ops gred_qdisc_ops = {
	650	.next = NULL,
	651	.cl_ops = NULL,
	652	.id = "gred",
	653	.priv_size = sizeof(struct gred_sched),
	654	.enqueue = gred_enqueue,
	655	.dequeue = gred_dequeue,
	656	.requeue = gred_requeue,
	657	.drop = gred_drop,
	658	.init = gred_init,
	659	.reset = gred_reset,
	660	.destroy = gred_destroy,
	661	.change = gred_change,
	662	.dump = gred_dump,
	663	.owner = THIS_MODULE,
	664	};
	665
	666	static int __init gred_module_init(void)
	667	{
	668	return register_qdisc(&gred_qdisc_ops);
	669	}
	670	static void __exit gred_module_exit(void)
	671	{
	672	unregister_qdisc(&gred_qdisc_ops);
	673	}
	674	module_init(gred_module_init)
	675	module_exit(gred_module_exit)
	676	MODULE_LICENSE("GPL");