[linux.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 ([email protected]) 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 include/net/red.h
 */

#include <linux/module.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/skbuff.h>
#include <net/pkt_sched.h>
#include <net/red.h>

#define GRED_DEF_PRIO (MAX_DPs / 2)
#define GRED_VQ_MASK (MAX_DPs - 1)

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		red_flags;
	u32 		DPs;
	u32 		def;
	struct red_parms wred_set;
};

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 inline u16 tc_index_to_dp(struct sk_buff *skb)
{
	return skb->tc_index & GRED_VQ_MASK;
}

static inline void gred_load_wred_set(struct gred_sched *table,
				      struct gred_sched_data *q)
{
	q->parms.qavg = table->wred_set.qavg;
	q->parms.qidlestart = table->wred_set.qidlestart;
}

static inline void gred_store_wred_set(struct gred_sched *table,
				       struct gred_sched_data *q)
{
	table->wred_set.qavg = q->parms.qavg;
}

static inline int gred_use_ecn(struct gred_sched *t)
{
	return t->red_flags & TC_RED_ECN;
}

static inline int gred_use_harddrop(struct gred_sched *t)
{
	return t->red_flags & TC_RED_HARDDROP;
}

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;
	u16 dp = tc_index_to_dp(skb);

	if (dp >= t->DPs  || (q = t->tab[dp]) == NULL) {
		dp = t->def;

		if ((q = t->tab[dp]) == NULL) {
			/* Pass through packets not assigned to a DP
			 * if no default DP has been configured. This
			 * allows for DP flows to be left untouched.
			 */
			if (skb_queue_len(&sch->q) < sch->dev->tx_queue_len)
				return qdisc_enqueue_tail(skb, sch);
			else
				goto drop;
		}

		/* fix tc_index? --could be controvesial but needed for
		   requeueing */
		skb->tc_index = (skb->tc_index & ~GRED_VQ_MASK) | dp;
	}

	/* sum up all the qaves of prios <= to ours to get the new qave */
	if (!gred_wred_mode(t) && gred_rio_mode(t)) {
		int i;

		for (i = 0; i < t->DPs; i++) {
			if (t->tab[i] && 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))
		gred_load_wred_set(t, q);

	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))
		gred_store_wred_set(t, q);

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

		case RED_PROB_MARK:
			sch->qstats.overlimits++;
			if (!gred_use_ecn(t) || !INET_ECN_set_ce(skb)) {
				q->stats.prob_drop++;
				goto congestion_drop;
			}

			q->stats.prob_mark++;
			break;

		case RED_HARD_MARK:
			sch->qstats.overlimits++;
			if (gred_use_harddrop(t) || !gred_use_ecn(t) ||
			    !INET_ECN_set_ce(skb)) {
				q->stats.forced_drop++;
				goto congestion_drop;
			}
			q->stats.forced_mark++;
			break;
	}

	if (q->backlog + skb->len <= q->limit) {
		q->backlog += skb->len;
		return qdisc_enqueue_tail(skb, sch);
	}

	q->stats.pdrop++;
drop:
	return qdisc_drop(skb, sch);

congestion_drop:
	qdisc_drop(skb, sch);
	return NET_XMIT_CN;
}

static int gred_requeue(struct sk_buff *skb, struct Qdisc* sch)
{
	struct gred_sched *t = qdisc_priv(sch);
	struct gred_sched_data *q;
	u16 dp = tc_index_to_dp(skb);

	if (dp >= t->DPs || (q = t->tab[dp]) == NULL) {
		if (net_ratelimit())
			printk(KERN_WARNING "GRED: Unable to relocate VQ 0x%x "
			       "for requeue, screwing up backlog.\n",
			       tc_index_to_dp(skb));
	} else {
		if (red_is_idling(&q->parms))
			red_end_of_idle_period(&q->parms);
		q->backlog += skb->len;
	}

	return qdisc_requeue(skb, sch);
}

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

	skb = qdisc_dequeue_head(sch);

	if (skb) {
		struct gred_sched_data *q;
		u16 dp = tc_index_to_dp(skb);

		if (dp >= t->DPs || (q = t->tab[dp]) == NULL) {
			if (net_ratelimit())
				printk(KERN_WARNING "GRED: Unable to relocate "
				       "VQ 0x%x after dequeue, screwing up "
				       "backlog.\n", tc_index_to_dp(skb));
		} else {
			q->backlog -= skb->len;

			if (!q->backlog && !gred_wred_mode(t))
				red_start_of_idle_period(&q->parms);
		}

		return skb;
	}

	if (gred_wred_mode(t) && !red_is_idling(&t->wred_set))
		red_start_of_idle_period(&t->wred_set);

	return NULL;
}

static unsigned int gred_drop(struct Qdisc* sch)
{
	struct sk_buff *skb;
	struct gred_sched *t = qdisc_priv(sch);

	skb = qdisc_dequeue_tail(sch);
	if (skb) {
		unsigned int len = skb->len;
		struct gred_sched_data *q;
		u16 dp = tc_index_to_dp(skb);

		if (dp >= t->DPs || (q = t->tab[dp]) == NULL) {
			if (net_ratelimit())
				printk(KERN_WARNING "GRED: Unable to relocate "
				       "VQ 0x%x while dropping, screwing up "
				       "backlog.\n", tc_index_to_dp(skb));
		} else {
			q->backlog -= len;
			q->stats.other++;

			if (!q->backlog && !gred_wred_mode(t))
				red_start_of_idle_period(&q->parms);
		}

		qdisc_drop(skb, sch);
		return len;
	}

	if (gred_wred_mode(t) && !red_is_idling(&t->wred_set))
		red_start_of_idle_period(&t->wred_set);

	return 0;

}

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

	qdisc_reset_queue(sch);

	for (i = 0; i < t->DPs; i++) {
		struct gred_sched_data *q = t->tab[i];

		if (!q)
			continue;

		red_restart(&q->parms);
		q->backlog = 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;
	table->red_flags = sopt->flags;

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

	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] = kzalloc(sizeof(*q), GFP_KERNEL);
		if (table->tab[dp] == NULL)
			return -ENOMEM;
	}

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

	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 (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),
		.flags	= table->red_flags,
	};

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