[mirror_ubuntu-artful-kernel.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>
#include <net/red.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
{
	u32		limit;		/* HARD maximal queue length	*/
	u32      	DP;		/* the drop pramaters */
	u32		bytesin;	/* bytes seen on virtualQ so far*/
	u32		packetsin;	/* packets seen on virtualQ so far*/
	u32		backlog;	/* bytes on the virtualQ */
	u8              prio;        /* the prio of this vq */

	struct red_parms parms;
	struct red_stats stats;
};

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 inline unsigned int gred_backlog(struct gred_sched *table,
					struct gred_sched_data *q,
					struct Qdisc *sch)
{
	if (gred_wred_mode(table))
		return sch->qstats.backlog;
	else
		return q->backlog;
}

static int
gred_enqueue(struct sk_buff *skb, struct Qdisc* sch)
{
	struct gred_sched_data *q=NULL;
	struct gred_sched *t= qdisc_priv(sch);
	unsigned long qavg = 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 &&
			    !red_is_idling(&t->tab[i]->parms))
				qavg +=t->tab[i]->parms.qavg;
		}
			
	}

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

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

	q->parms.qavg = red_calc_qavg(&q->parms, gred_backlog(t, q, sch));

	if (red_is_idling(&q->parms))
		red_end_of_idle_period(&q->parms);

	if (gred_wred_mode(t))
		t->tab[t->def]->parms.qavg = q->parms.qavg;

	switch (red_action(&q->parms, q->parms.qavg + qavg)) {
		case RED_DONT_MARK:
			break;

		case RED_PROB_MARK:
			sch->qstats.overlimits++;
			q->stats.prob_drop++;
			goto drop;

		case RED_HARD_MARK:
			sch->qstats.overlimits++;
			q->stats.forced_drop++;
			goto drop;
	}

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

	q->stats.pdrop++;
drop:
	kfree_skb(skb);
	sch->qstats.drops++;
	return NET_XMIT_DROP;
}

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

	if (red_is_idling(&q->parms))
		red_end_of_idle_period(&q->parms);

	__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))
				red_start_of_idle_period(&q->parms);
		} 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
				red_start_of_idle_period(&q->parms);
	}

	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->stats.other++;
			if (!q->backlog && !gred_wred_mode(t))
				red_start_of_idle_period(&q->parms);
		} 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;
	}

	red_start_of_idle_period(&q->parms);
	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; 
		red_restart(&q->parms);
		q->backlog = 0;
		q->stats.other = 0;
		q->stats.forced_drop = 0;
		q->stats.prob_drop = 0;
		q->stats.pdrop = 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->limit = ctl->limit;

	if (q->backlog == 0)
		red_end_of_idle_period(&q->parms);

	red_set_parms(&q->parms,
		      ctl->qth_min, ctl->qth_max, ctl->Wlog, ctl->Plog,
		      ctl->Scell_log, stab);

	q->stats.other = 0;
	q->stats.forced_drop = 0;
	q->stats.prob_drop = 0;
	q->stats.pdrop = 0;

	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->parms.qth_min >> q->parms.Wlog;
		opt.qth_max	= q->parms.qth_max >> q->parms.Wlog;
		opt.Wlog	= q->parms.Wlog;
		opt.Plog	= q->parms.Plog;
		opt.Scell_log	= q->parms.Scell_log;
		opt.other	= q->stats.other;
		opt.early	= q->stats.prob_drop;
		opt.forced	= q->stats.forced_drop;
		opt.pdrop	= q->stats.pdrop;
		opt.packets	= q->packetsin;
		opt.bytesin	= q->bytesin;

		if (gred_wred_mode(table)) {
			q->parms.qidlestart =
				table->tab[table->def]->parms.qidlestart;
			q->parms.qavg = table->tab[table->def]->parms.qavg;
		}

		opt.qave = red_calc_qavg(&q->parms, q->parms.qavg);

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>
22b33429	48	#include <net/red.h>
1da177e4 LT	49
	50	#if 1 /* control */
	51	#define DPRINTK(format,args...) printk(KERN_DEBUG format,##args)
	52	#else
	53	#define DPRINTK(format,args...)
	54	#endif
	55
	56	#if 0 /* data */
	57	#define D2PRINTK(format,args...) printk(KERN_DEBUG format,##args)
	58	#else
	59	#define D2PRINTK(format,args...)
	60	#endif
	61
f62d6b93 TG	62	#define GRED_DEF_PRIO (MAX_DPs / 2)
f62d6b93 TG	63
1da177e4 LT	64	struct gred_sched_data;
	65	struct gred_sched;
	66
	67	struct gred_sched_data
	68	{
1da177e4	69	u32 limit; /* HARD maximal queue length */
1da177e4	70	u32 DP; /* the drop pramaters */
1da177e4 LT	71	u32 bytesin; /* bytes seen on virtualQ so far*/
	72	u32 packetsin; /* packets seen on virtualQ so far*/
	73	u32 backlog; /* bytes on the virtualQ */
1da177e4 LT	74	u8 prio; /* the prio of this vq */
1da177e4 LT	75
22b33429 TG	76	struct red_parms parms;
22b33429 TG	77	struct red_stats stats;
1da177e4 LT	78	};
1da177e4 LT	79
dea3f628 TG	80	enum {
dea3f628 TG	81	GRED_WRED_MODE = 1,
d6fd4e96	82	GRED_RIO_MODE,
dea3f628 TG	83	};
dea3f628 TG	84
1da177e4 LT	85	struct gred_sched
	86	{
	87	struct gred_sched_data *tab[MAX_DPs];
dea3f628	88	unsigned long flags;
1da177e4 LT	89	u32 DPs;
	90	u32 def;
	91	u8 initd;
1da177e4 LT	92	};
1da177e4 LT	93
dea3f628 TG	94	static inline int gred_wred_mode(struct gred_sched *table)
	95	{
	96	return test_bit(GRED_WRED_MODE, &table->flags);
	97	}
	98
	99	static inline void gred_enable_wred_mode(struct gred_sched *table)
	100	{
	101	__set_bit(GRED_WRED_MODE, &table->flags);
	102	}
	103
	104	static inline void gred_disable_wred_mode(struct gred_sched *table)
	105	{
	106	__clear_bit(GRED_WRED_MODE, &table->flags);
	107	}
	108
d6fd4e96 TG	109	static inline int gred_rio_mode(struct gred_sched *table)
	110	{
	111	return test_bit(GRED_RIO_MODE, &table->flags);
	112	}
	113
	114	static inline void gred_enable_rio_mode(struct gred_sched *table)
	115	{
	116	__set_bit(GRED_RIO_MODE, &table->flags);
	117	}
	118
	119	static inline void gred_disable_rio_mode(struct gred_sched *table)
	120	{
	121	__clear_bit(GRED_RIO_MODE, &table->flags);
	122	}
	123
dea3f628 TG	124	static inline int gred_wred_mode_check(struct Qdisc *sch)
	125	{
	126	struct gred_sched *table = qdisc_priv(sch);
	127	int i;
	128
	129	/* Really ugly O(n^2) but shouldn't be necessary too frequent. */
	130	for (i = 0; i < table->DPs; i++) {
	131	struct gred_sched_data *q = table->tab[i];
	132	int n;
	133
	134	if (q == NULL)
	135	continue;
	136
	137	for (n = 0; n < table->DPs; n++)
	138	if (table->tab[n] && table->tab[n] != q &&
	139	table->tab[n]->prio == q->prio)
	140	return 1;
	141	}
	142
	143	return 0;
	144	}
	145
22b33429 TG	146	static inline unsigned int gred_backlog(struct gred_sched *table,
	147	struct gred_sched_data *q,
	148	struct Qdisc *sch)
	149	{
	150	if (gred_wred_mode(table))
	151	return sch->qstats.backlog;
	152	else
	153	return q->backlog;
	154	}
	155
1da177e4 LT	156	static int
	157	gred_enqueue(struct sk_buff skb, struct Qdisc sch)
	158	{
1da177e4 LT	159	struct gred_sched_data *q=NULL;
1da177e4 LT	160	struct gred_sched *t= qdisc_priv(sch);
22b33429	161	unsigned long qavg = 0;
1da177e4 LT	162	int i=0;
	163
	164	if (!t->initd && skb_queue_len(&sch->q) < (sch->dev->tx_queue_len ? : 1)) {
	165	D2PRINTK("NO GRED Queues setup yet! Enqueued anyway\n");
	166	goto do_enqueue;
	167	}
	168
	169
	170	if ( ((skb->tc_index&0xf) > (t->DPs -1)) \|\| !(q=t->tab[skb->tc_index&0xf])) {
	171	printk("GRED: setting to default (%d)\n ",t->def);
	172	if (!(q=t->tab[t->def])) {
	173	DPRINTK("GRED: setting to default FAILED! dropping!! "
	174	"(%d)\n ", t->def);
	175	goto drop;
	176	}
	177	/* fix tc_index? --could be controvesial but needed for
	178	requeueing */
	179	skb->tc_index=(skb->tc_index&0xfffffff0) \| t->def;
	180	}
	181
	182	D2PRINTK("gred_enqueue virtualQ 0x%x classid %x backlog %d "
	183	"general backlog %d\n",skb->tc_index&0xf,sch->handle,q->backlog,
	184	sch->qstats.backlog);
	185	/* sum up all the qaves of prios <= to ours to get the new qave*/
d6fd4e96	186	if (!gred_wred_mode(t) && gred_rio_mode(t)) {
1da177e4 LT	187	for (i=0;i<t->DPs;i++) {
	188	if ((!t->tab[i]) \|\| (i==q->DP))
	189	continue;
	190
22b33429 TG	191	if (t->tab[i]->prio < q->prio &&
	192	!red_is_idling(&t->tab[i]->parms))
	193	qavg +=t->tab[i]->parms.qavg;
1da177e4 LT	194	}
	195
	196	}
	197
	198	q->packetsin++;
	199	q->bytesin+=skb->len;
	200
dea3f628	201	if (gred_wred_mode(t)) {
22b33429 TG	202	qavg = 0;
	203	q->parms.qavg = t->tab[t->def]->parms.qavg;
	204	q->parms.qidlestart = t->tab[t->def]->parms.qidlestart;
1da177e4 LT	205	}
1da177e4 LT	206
22b33429	207	q->parms.qavg = red_calc_qavg(&q->parms, gred_backlog(t, q, sch));
1da177e4	208
22b33429 TG	209	if (red_is_idling(&q->parms))
22b33429 TG	210	red_end_of_idle_period(&q->parms);
1da177e4	211
dea3f628	212	if (gred_wred_mode(t))
22b33429	213	t->tab[t->def]->parms.qavg = q->parms.qavg;
1da177e4	214
22b33429 TG	215	switch (red_action(&q->parms, q->parms.qavg + qavg)) {
	216	case RED_DONT_MARK:
	217	break;
1da177e4	218
22b33429 TG	219	case RED_PROB_MARK:
	220	sch->qstats.overlimits++;
	221	q->stats.prob_drop++;
	222	goto drop;
	223
	224	case RED_HARD_MARK:
	225	sch->qstats.overlimits++;
	226	q->stats.forced_drop++;
	227	goto drop;
1da177e4	228	}
22b33429 TG	229
	230	if (q->backlog + skb->len <= q->limit) {
	231	q->backlog += skb->len;
	232	do_enqueue:
	233	__skb_queue_tail(&sch->q, skb);
	234	sch->qstats.backlog += skb->len;
	235	sch->bstats.bytes += skb->len;
	236	sch->bstats.packets++;
	237	return 0;
1da177e4	238	}
22b33429 TG	239
	240	q->stats.pdrop++;
	241	drop:
	242	kfree_skb(skb);
	243	sch->qstats.drops++;
	244	return NET_XMIT_DROP;
1da177e4 LT	245	}
	246
	247	static int
	248	gred_requeue(struct sk_buff skb, struct Qdisc sch)
	249	{
	250	struct gred_sched_data *q;
	251	struct gred_sched *t= qdisc_priv(sch);
	252	q= t->tab[(skb->tc_index&0xf)];
	253	/* error checking here -- probably unnecessary */
22b33429 TG	254
	255	if (red_is_idling(&q->parms))
	256	red_end_of_idle_period(&q->parms);
1da177e4 LT	257
	258	__skb_queue_head(&sch->q, skb);
	259	sch->qstats.backlog += skb->len;
	260	sch->qstats.requeues++;
	261	q->backlog += skb->len;
	262	return 0;
	263	}
	264
	265	static struct sk_buff *
	266	gred_dequeue(struct Qdisc* sch)
	267	{
	268	struct sk_buff *skb;
	269	struct gred_sched_data *q;
	270	struct gred_sched *t= qdisc_priv(sch);
	271
	272	skb = __skb_dequeue(&sch->q);
	273	if (skb) {
	274	sch->qstats.backlog -= skb->len;
	275	q= t->tab[(skb->tc_index&0xf)];
	276	if (q) {
	277	q->backlog -= skb->len;
dea3f628	278	if (!q->backlog && !gred_wred_mode(t))
22b33429	279	red_start_of_idle_period(&q->parms);
1da177e4 LT	280	} else {
	281	D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
	282	}
	283	return skb;
	284	}
	285
dea3f628	286	if (gred_wred_mode(t)) {
1da177e4 LT	287	q= t->tab[t->def];
	288	if (!q)
	289	D2PRINTK("no default VQ set: Results will be "
	290	"screwed up\n");
	291	else
22b33429	292	red_start_of_idle_period(&q->parms);
1da177e4 LT	293	}
	294
	295	return NULL;
	296	}
	297
	298	static unsigned int gred_drop(struct Qdisc* sch)
	299	{
	300	struct sk_buff *skb;
	301
	302	struct gred_sched_data *q;
	303	struct gred_sched *t= qdisc_priv(sch);
	304
	305	skb = __skb_dequeue_tail(&sch->q);
	306	if (skb) {
	307	unsigned int len = skb->len;
	308	sch->qstats.backlog -= len;
	309	sch->qstats.drops++;
	310	q= t->tab[(skb->tc_index&0xf)];
	311	if (q) {
	312	q->backlog -= len;
22b33429	313	q->stats.other++;
dea3f628	314	if (!q->backlog && !gred_wred_mode(t))
22b33429	315	red_start_of_idle_period(&q->parms);
1da177e4 LT	316	} else {
	317	D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
	318	}
	319
	320	kfree_skb(skb);
	321	return len;
	322	}
	323
	324	q=t->tab[t->def];
	325	if (!q) {
	326	D2PRINTK("no default VQ set: Results might be screwed up\n");
	327	return 0;
	328	}
	329
22b33429	330	red_start_of_idle_period(&q->parms);
1da177e4 LT	331	return 0;
	332
	333	}
	334
	335	static void gred_reset(struct Qdisc* sch)
	336	{
	337	int i;
	338	struct gred_sched_data *q;
	339	struct gred_sched *t= qdisc_priv(sch);
	340
	341	__skb_queue_purge(&sch->q);
	342
	343	sch->qstats.backlog = 0;
	344
	345	for (i=0;i<t->DPs;i++) {
	346	q= t->tab[i];
	347	if (!q)
	348	continue;
22b33429	349	red_restart(&q->parms);
1da177e4	350	q->backlog = 0;
22b33429 TG	351	q->stats.other = 0;
	352	q->stats.forced_drop = 0;
	353	q->stats.prob_drop = 0;
	354	q->stats.pdrop = 0;
1da177e4 LT	355	}
	356	}
	357
6639607e TG	358	static inline void gred_destroy_vq(struct gred_sched_data *q)
	359	{
	360	kfree(q);
	361	}
	362
	363	static inline int gred_change_table_def(struct Qdisc sch, struct rtattr dps)
1da177e4 LT	364	{
1da177e4 LT	365	struct gred_sched *table = qdisc_priv(sch);
1da177e4	366	struct tc_gred_sopt *sopt;
6639607e	367	int i;
1da177e4	368
6639607e	369	if (dps == NULL \|\| RTA_PAYLOAD(dps) < sizeof(*sopt))
1da177e4 LT	370	return -EINVAL;
1da177e4 LT	371
6639607e	372	sopt = RTA_DATA(dps);
1da177e4	373
6639607e TG	374	if (sopt->DPs > MAX_DPs \|\| sopt->DPs == 0 \|\| sopt->def_DP >= sopt->DPs)
6639607e TG	375	return -EINVAL;
1da177e4	376
6639607e TG	377	sch_tree_lock(sch);
	378	table->DPs = sopt->DPs;
	379	table->def = sopt->def_DP;
dea3f628	380
6639607e TG	381	/*
	382	* Every entry point to GRED is synchronized with the above code
	383	* and the DP is checked against DPs, i.e. shadowed VQs can no
	384	* longer be found so we can unlock right here.
	385	*/
	386	sch_tree_unlock(sch);
dea3f628	387
6639607e TG	388	if (sopt->grio) {
	389	gred_enable_rio_mode(table);
	390	gred_disable_wred_mode(table);
	391	if (gred_wred_mode_check(sch))
	392	gred_enable_wred_mode(table);
	393	} else {
	394	gred_disable_rio_mode(table);
	395	gred_disable_wred_mode(table);
	396	}
	397
	398	for (i = table->DPs; i < MAX_DPs; i++) {
	399	if (table->tab[i]) {
	400	printk(KERN_WARNING "GRED: Warning: Destroying "
	401	"shadowed VQ 0x%x\n", i);
	402	gred_destroy_vq(table->tab[i]);
	403	table->tab[i] = NULL;
	404	}
	405	}
1da177e4	406
6639607e TG	407	table->initd = 0;
	408
	409	return 0;
	410	}
	411
f62d6b93 TG	412	static inline int gred_change_vq(struct Qdisc *sch, int dp,
f62d6b93 TG	413	struct tc_gred_qopt ctl, int prio, u8 stab)
6639607e TG	414	{
	415	struct gred_sched *table = qdisc_priv(sch);
	416	struct gred_sched_data *q;
f62d6b93 TG	417
	418	if (table->tab[dp] == NULL) {
	419	table->tab[dp] = kmalloc(sizeof(*q), GFP_KERNEL);
	420	if (table->tab[dp] == NULL)
	421	return -ENOMEM;
	422	memset(table->tab[dp], 0, sizeof(*q));
	423	}
	424
	425	q = table->tab[dp];
	426	q->DP = dp;
	427	q->prio = prio;
f62d6b93	428	q->limit = ctl->limit;
22b33429 TG	429
	430	if (q->backlog == 0)
	431	red_end_of_idle_period(&q->parms);
	432
	433	red_set_parms(&q->parms,
	434	ctl->qth_min, ctl->qth_max, ctl->Wlog, ctl->Plog,
	435	ctl->Scell_log, stab);
	436
	437	q->stats.other = 0;
	438	q->stats.forced_drop = 0;
	439	q->stats.prob_drop = 0;
	440	q->stats.pdrop = 0;
f62d6b93 TG	441
	442	return 0;
	443	}
	444
	445	static int gred_change(struct Qdisc sch, struct rtattr opt)
	446	{
	447	struct gred_sched *table = qdisc_priv(sch);
6639607e	448	struct tc_gred_qopt *ctl;
f62d6b93 TG	449	struct rtattr *tb[TCA_GRED_MAX];
	450	int err = -EINVAL, prio = GRED_DEF_PRIO;
	451	u8 *stab;
6639607e	452
f62d6b93	453	if (opt == NULL \|\| rtattr_parse_nested(tb, TCA_GRED_MAX, opt))
6639607e TG	454	return -EINVAL;
	455
	456	if (tb[TCA_GRED_PARMS-1] == NULL && tb[TCA_GRED_STAB-1] == NULL)
f62d6b93	457	return gred_change_table_def(sch, opt);
1da177e4	458
f62d6b93 TG	459	if (tb[TCA_GRED_PARMS-1] == NULL \|\|
	460	RTA_PAYLOAD(tb[TCA_GRED_PARMS-1]) < sizeof(*ctl) \|\|
	461	tb[TCA_GRED_STAB-1] == NULL \|\|
	462	RTA_PAYLOAD(tb[TCA_GRED_STAB-1]) < 256)
	463	return -EINVAL;
1da177e4 LT	464
1da177e4 LT	465	ctl = RTA_DATA(tb[TCA_GRED_PARMS-1]);
f62d6b93	466	stab = RTA_DATA(tb[TCA_GRED_STAB-1]);
a8aaa995 TG	467
a8aaa995 TG	468	if (ctl->DP >= table->DPs)
f62d6b93	469	goto errout;
1da177e4	470
d6fd4e96	471	if (gred_rio_mode(table)) {
f62d6b93 TG	472	if (ctl->prio == 0) {
	473	int def_prio = GRED_DEF_PRIO;
	474
	475	if (table->tab[table->def])
	476	def_prio = table->tab[table->def]->prio;
	477
	478	printk(KERN_DEBUG "GRED: DP %u does not have a prio "
	479	"setting default to %d\n", ctl->DP, def_prio);
	480
	481	prio = def_prio;
	482	} else
	483	prio = ctl->prio;
1da177e4 LT	484	}
1da177e4 LT	485
f62d6b93	486	sch_tree_lock(sch);
1da177e4	487
f62d6b93 TG	488	err = gred_change_vq(sch, ctl->DP, ctl, prio, stab);
	489	if (err < 0)
	490	goto errout_locked;
1da177e4	491
f62d6b93 TG	492	if (table->tab[table->def] == NULL) {
	493	if (gred_rio_mode(table))
	494	prio = table->tab[ctl->DP]->prio;
	495
	496	err = gred_change_vq(sch, table->def, ctl, prio, stab);
	497	if (err < 0)
	498	goto errout_locked;
	499	}
	500
	501	table->initd = 1;
1da177e4	502
d6fd4e96	503	if (gred_rio_mode(table)) {
dea3f628 TG	504	gred_disable_wred_mode(table);
	505	if (gred_wred_mode_check(sch))
	506	gred_enable_wred_mode(table);
1da177e4 LT	507	}
1da177e4 LT	508
f62d6b93	509	err = 0;
1da177e4	510
f62d6b93 TG	511	errout_locked:
	512	sch_tree_unlock(sch);
	513	errout:
	514	return err;
1da177e4 LT	515	}
	516
	517	static int gred_init(struct Qdisc sch, struct rtattr opt)
	518	{
6639607e	519	struct rtattr *tb[TCA_GRED_MAX];
1da177e4	520
6639607e	521	if (opt == NULL \|\| rtattr_parse_nested(tb, TCA_GRED_MAX, opt))
1da177e4 LT	522	return -EINVAL;
1da177e4 LT	523
6639607e TG	524	if (tb[TCA_GRED_PARMS-1] \|\| tb[TCA_GRED_STAB-1])
6639607e TG	525	return -EINVAL;
1da177e4	526
6639607e	527	return gred_change_table_def(sch, tb[TCA_GRED_DPS-1]);
1da177e4 LT	528	}
	529
	530	static int gred_dump(struct Qdisc sch, struct sk_buff skb)
	531	{
1da177e4	532	struct gred_sched *table = qdisc_priv(sch);
05f1cc01	533	struct rtattr parms, opts = NULL;
1da177e4	534	int i;
e0636822 TG	535	struct tc_gred_sopt sopt = {
	536	.DPs = table->DPs,
	537	.def_DP = table->def,
	538	.grio = gred_rio_mode(table),
	539	};
1da177e4	540
05f1cc01	541	opts = RTA_NEST(skb, TCA_OPTIONS);
e0636822	542	RTA_PUT(skb, TCA_GRED_DPS, sizeof(sopt), &sopt);
05f1cc01	543	parms = RTA_NEST(skb, TCA_GRED_PARMS);
1da177e4	544
05f1cc01 TG	545	for (i = 0; i < MAX_DPs; i++) {
	546	struct gred_sched_data *q = table->tab[i];
	547	struct tc_gred_qopt opt;
1da177e4	548
05f1cc01	549	memset(&opt, 0, sizeof(opt));
1da177e4 LT	550
	551	if (!q) {
	552	/* hack -- fix at some point with proper message
	553	This is how we indicate to tc that there is no VQ
	554	at this DP */
	555
05f1cc01 TG	556	opt.DP = MAX_DPs + i;
05f1cc01 TG	557	goto append_opt;
1da177e4 LT	558	}
1da177e4 LT	559
05f1cc01 TG	560	opt.limit = q->limit;
	561	opt.DP = q->DP;
	562	opt.backlog = q->backlog;
	563	opt.prio = q->prio;
22b33429 TG	564	opt.qth_min = q->parms.qth_min >> q->parms.Wlog;
	565	opt.qth_max = q->parms.qth_max >> q->parms.Wlog;
	566	opt.Wlog = q->parms.Wlog;
	567	opt.Plog = q->parms.Plog;
	568	opt.Scell_log = q->parms.Scell_log;
	569	opt.other = q->stats.other;
	570	opt.early = q->stats.prob_drop;
	571	opt.forced = q->stats.forced_drop;
	572	opt.pdrop = q->stats.pdrop;
05f1cc01 TG	573	opt.packets = q->packetsin;
	574	opt.bytesin = q->bytesin;
	575
22b33429 TG	576	if (gred_wred_mode(table)) {
	577	q->parms.qidlestart =
	578	table->tab[table->def]->parms.qidlestart;
	579	q->parms.qavg = table->tab[table->def]->parms.qavg;
1da177e4	580	}
05f1cc01	581
22b33429 TG	582	opt.qave = red_calc_qavg(&q->parms, q->parms.qavg);
22b33429 TG	583
05f1cc01 TG	584	append_opt:
05f1cc01 TG	585	RTA_APPEND(skb, sizeof(opt), &opt);
1da177e4 LT	586	}
1da177e4 LT	587
05f1cc01	588	RTA_NEST_END(skb, parms);
1da177e4	589
05f1cc01	590	return RTA_NEST_END(skb, opts);
1da177e4 LT	591
1da177e4 LT	592	rtattr_failure:
05f1cc01	593	return RTA_NEST_CANCEL(skb, opts);
1da177e4 LT	594	}
	595
	596	static void gred_destroy(struct Qdisc *sch)
	597	{
	598	struct gred_sched *table = qdisc_priv(sch);
	599	int i;
	600
	601	for (i = 0;i < table->DPs; i++) {
	602	if (table->tab[i])
6639607e	603	gred_destroy_vq(table->tab[i]);
1da177e4 LT	604	}
	605	}
	606
	607	static struct Qdisc_ops gred_qdisc_ops = {
	608	.next = NULL,
	609	.cl_ops = NULL,
	610	.id = "gred",
	611	.priv_size = sizeof(struct gred_sched),
	612	.enqueue = gred_enqueue,
	613	.dequeue = gred_dequeue,
	614	.requeue = gred_requeue,
	615	.drop = gred_drop,
	616	.init = gred_init,
	617	.reset = gred_reset,
	618	.destroy = gred_destroy,
	619	.change = gred_change,
	620	.dump = gred_dump,
	621	.owner = THIS_MODULE,
	622	};
	623
	624	static int __init gred_module_init(void)
	625	{
	626	return register_qdisc(&gred_qdisc_ops);
	627	}
	628	static void __exit gred_module_exit(void)
	629	{
	630	unregister_qdisc(&gred_qdisc_ops);
	631	}
	632	module_init(gred_module_init)
	633	module_exit(gred_module_exit)
	634	MODULE_LICENSE("GPL");