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

/*
 * net/sched/cls_route.c	ROUTE4 classifier.
 *
 *		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:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 */

#include <linux/module.h>
#include <linux/slab.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/string.h>
#include <linux/errno.h>
#include <linux/skbuff.h>
#include <net/dst.h>
#include <net/route.h>
#include <net/netlink.h>
#include <net/act_api.h>
#include <net/pkt_cls.h>

/*
   1. For now we assume that route tags < 256.
      It allows to use direct table lookups, instead of hash tables.
   2. For now we assume that "from TAG" and "fromdev DEV" statements
      are mutually  exclusive.
   3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
 */

struct route4_fastmap
{
	struct route4_filter	*filter;
	u32			id;
	int			iif;
};

struct route4_head
{
	struct route4_fastmap	fastmap[16];
	struct route4_bucket	*table[256+1];
};

struct route4_bucket
{
	/* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
	struct route4_filter	*ht[16+16+1];
};

struct route4_filter
{
	struct route4_filter	*next;
	u32			id;
	int			iif;

	struct tcf_result	res;
	struct tcf_exts		exts;
	u32			handle;
	struct route4_bucket	*bkt;
};

#define ROUTE4_FAILURE ((struct route4_filter*)(-1L))

static const struct tcf_ext_map route_ext_map = {
	.police = TCA_ROUTE4_POLICE,
	.action = TCA_ROUTE4_ACT
};

static __inline__ int route4_fastmap_hash(u32 id, int iif)
{
	return id&0xF;
}

static inline
void route4_reset_fastmap(struct Qdisc *q, struct route4_head *head, u32 id)
{
	spinlock_t *root_lock = qdisc_root_sleeping_lock(q);

	spin_lock_bh(root_lock);
	memset(head->fastmap, 0, sizeof(head->fastmap));
	spin_unlock_bh(root_lock);
}

static inline void
route4_set_fastmap(struct route4_head *head, u32 id, int iif,
		   struct route4_filter *f)
{
	int h = route4_fastmap_hash(id, iif);
	head->fastmap[h].id = id;
	head->fastmap[h].iif = iif;
	head->fastmap[h].filter = f;
}

static __inline__ int route4_hash_to(u32 id)
{
	return id&0xFF;
}

static __inline__ int route4_hash_from(u32 id)
{
	return (id>>16)&0xF;
}

static __inline__ int route4_hash_iif(int iif)
{
	return 16 + ((iif>>16)&0xF);
}

static __inline__ int route4_hash_wild(void)
{
	return 32;
}

#define ROUTE4_APPLY_RESULT()					\
{								\
	*res = f->res;						\
	if (tcf_exts_is_available(&f->exts)) {			\
		int r = tcf_exts_exec(skb, &f->exts, res);	\
		if (r < 0) {					\
			dont_cache = 1;				\
			continue;				\
		}						\
		return r;					\
	} else if (!dont_cache)					\
		route4_set_fastmap(head, id, iif, f);		\
	return 0;						\
}

static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp,
			   struct tcf_result *res)
{
	struct route4_head *head = (struct route4_head*)tp->root;
	struct dst_entry *dst;
	struct route4_bucket *b;
	struct route4_filter *f;
	u32 id, h;
	int iif, dont_cache = 0;

	if ((dst = skb_dst(skb)) == NULL)
		goto failure;

	id = dst->tclassid;
	if (head == NULL)
		goto old_method;

	iif = ((struct rtable*)dst)->fl.iif;

	h = route4_fastmap_hash(id, iif);
	if (id == head->fastmap[h].id &&
	    iif == head->fastmap[h].iif &&
	    (f = head->fastmap[h].filter) != NULL) {
		if (f == ROUTE4_FAILURE)
			goto failure;

		*res = f->res;
		return 0;
	}

	h = route4_hash_to(id);

restart:
	if ((b = head->table[h]) != NULL) {
		for (f = b->ht[route4_hash_from(id)]; f; f = f->next)
			if (f->id == id)
				ROUTE4_APPLY_RESULT();

		for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)
			if (f->iif == iif)
				ROUTE4_APPLY_RESULT();

		for (f = b->ht[route4_hash_wild()]; f; f = f->next)
			ROUTE4_APPLY_RESULT();

	}
	if (h < 256) {
		h = 256;
		id &= ~0xFFFF;
		goto restart;
	}

	if (!dont_cache)
		route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
failure:
	return -1;

old_method:
	if (id && (TC_H_MAJ(id) == 0 ||
		   !(TC_H_MAJ(id^tp->q->handle)))) {
		res->classid = id;
		res->class = 0;
		return 0;
	}
	return -1;
}

static inline u32 to_hash(u32 id)
{
	u32 h = id&0xFF;
	if (id&0x8000)
		h += 256;
	return h;
}

static inline u32 from_hash(u32 id)
{
	id &= 0xFFFF;
	if (id == 0xFFFF)
		return 32;
	if (!(id & 0x8000)) {
		if (id > 255)
			return 256;
		return id&0xF;
	}
	return 16 + (id&0xF);
}

static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
{
	struct route4_head *head = (struct route4_head*)tp->root;
	struct route4_bucket *b;
	struct route4_filter *f;
	unsigned h1, h2;

	if (!head)
		return 0;

	h1 = to_hash(handle);
	if (h1 > 256)
		return 0;

	h2 = from_hash(handle>>16);
	if (h2 > 32)
		return 0;

	if ((b = head->table[h1]) != NULL) {
		for (f = b->ht[h2]; f; f = f->next)
			if (f->handle == handle)
				return (unsigned long)f;
	}
	return 0;
}

static void route4_put(struct tcf_proto *tp, unsigned long f)
{
}

static int route4_init(struct tcf_proto *tp)
{
	return 0;
}

static inline void
route4_delete_filter(struct tcf_proto *tp, struct route4_filter *f)
{
	tcf_unbind_filter(tp, &f->res);
	tcf_exts_destroy(tp, &f->exts);
	kfree(f);
}

static void route4_destroy(struct tcf_proto *tp)
{
	struct route4_head *head = tp->root;
	int h1, h2;

	if (head == NULL)
		return;

	for (h1=0; h1<=256; h1++) {
		struct route4_bucket *b;

		if ((b = head->table[h1]) != NULL) {
			for (h2=0; h2<=32; h2++) {
				struct route4_filter *f;

				while ((f = b->ht[h2]) != NULL) {
					b->ht[h2] = f->next;
					route4_delete_filter(tp, f);
				}
			}
			kfree(b);
		}
	}
	kfree(head);
}

static int route4_delete(struct tcf_proto *tp, unsigned long arg)
{
	struct route4_head *head = (struct route4_head*)tp->root;
	struct route4_filter **fp, *f = (struct route4_filter*)arg;
	unsigned h = 0;
	struct route4_bucket *b;
	int i;

	if (!head || !f)
		return -EINVAL;

	h = f->handle;
	b = f->bkt;

	for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {
		if (*fp == f) {
			tcf_tree_lock(tp);
			*fp = f->next;
			tcf_tree_unlock(tp);

			route4_reset_fastmap(tp->q, head, f->id);
			route4_delete_filter(tp, f);

			/* Strip tree */

			for (i=0; i<=32; i++)
				if (b->ht[i])
					return 0;

			/* OK, session has no flows */
			tcf_tree_lock(tp);
			head->table[to_hash(h)] = NULL;
			tcf_tree_unlock(tp);

			kfree(b);
			return 0;
		}
	}
	return 0;
}

static const struct nla_policy route4_policy[TCA_ROUTE4_MAX + 1] = {
	[TCA_ROUTE4_CLASSID]	= { .type = NLA_U32 },
	[TCA_ROUTE4_TO]		= { .type = NLA_U32 },
	[TCA_ROUTE4_FROM]	= { .type = NLA_U32 },
	[TCA_ROUTE4_IIF]	= { .type = NLA_U32 },
};

static int route4_set_parms(struct tcf_proto *tp, unsigned long base,
	struct route4_filter *f, u32 handle, struct route4_head *head,
	struct nlattr **tb, struct nlattr *est, int new)
{
	int err;
	u32 id = 0, to = 0, nhandle = 0x8000;
	struct route4_filter *fp;
	unsigned int h1;
	struct route4_bucket *b;
	struct tcf_exts e;

	err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map);
	if (err < 0)
		return err;

	err = -EINVAL;
	if (tb[TCA_ROUTE4_TO]) {
		if (new && handle & 0x8000)
			goto errout;
		to = nla_get_u32(tb[TCA_ROUTE4_TO]);
		if (to > 0xFF)
			goto errout;
		nhandle = to;
	}

	if (tb[TCA_ROUTE4_FROM]) {
		if (tb[TCA_ROUTE4_IIF])
			goto errout;
		id = nla_get_u32(tb[TCA_ROUTE4_FROM]);
		if (id > 0xFF)
			goto errout;
		nhandle |= id << 16;
	} else if (tb[TCA_ROUTE4_IIF]) {
		id = nla_get_u32(tb[TCA_ROUTE4_IIF]);
		if (id > 0x7FFF)
			goto errout;
		nhandle |= (id | 0x8000) << 16;
	} else
		nhandle |= 0xFFFF << 16;

	if (handle && new) {
		nhandle |= handle & 0x7F00;
		if (nhandle != handle)
			goto errout;
	}

	h1 = to_hash(nhandle);
	if ((b = head->table[h1]) == NULL) {
		err = -ENOBUFS;
		b = kzalloc(sizeof(struct route4_bucket), GFP_KERNEL);
		if (b == NULL)
			goto errout;

		tcf_tree_lock(tp);
		head->table[h1] = b;
		tcf_tree_unlock(tp);
	} else {
		unsigned int h2 = from_hash(nhandle >> 16);
		err = -EEXIST;
		for (fp = b->ht[h2]; fp; fp = fp->next)
			if (fp->handle == f->handle)
				goto errout;
	}

	tcf_tree_lock(tp);
	if (tb[TCA_ROUTE4_TO])
		f->id = to;

	if (tb[TCA_ROUTE4_FROM])
		f->id = to | id<<16;
	else if (tb[TCA_ROUTE4_IIF])
		f->iif = id;

	f->handle = nhandle;
	f->bkt = b;
	tcf_tree_unlock(tp);

	if (tb[TCA_ROUTE4_CLASSID]) {
		f->res.classid = nla_get_u32(tb[TCA_ROUTE4_CLASSID]);
		tcf_bind_filter(tp, &f->res, base);
	}

	tcf_exts_change(tp, &f->exts, &e);

	return 0;
errout:
	tcf_exts_destroy(tp, &e);
	return err;
}

static int route4_change(struct tcf_proto *tp, unsigned long base,
		       u32 handle,
		       struct nlattr **tca,
		       unsigned long *arg)
{
	struct route4_head *head = tp->root;
	struct route4_filter *f, *f1, **fp;
	struct route4_bucket *b;
	struct nlattr *opt = tca[TCA_OPTIONS];
	struct nlattr *tb[TCA_ROUTE4_MAX + 1];
	unsigned int h, th;
	u32 old_handle = 0;
	int err;

	if (opt == NULL)
		return handle ? -EINVAL : 0;

	err = nla_parse_nested(tb, TCA_ROUTE4_MAX, opt, route4_policy);
	if (err < 0)
		return err;

	if ((f = (struct route4_filter*)*arg) != NULL) {
		if (f->handle != handle && handle)
			return -EINVAL;

		if (f->bkt)
			old_handle = f->handle;

		err = route4_set_parms(tp, base, f, handle, head, tb,
			tca[TCA_RATE], 0);
		if (err < 0)
			return err;

		goto reinsert;
	}

	err = -ENOBUFS;
	if (head == NULL) {
		head = kzalloc(sizeof(struct route4_head), GFP_KERNEL);
		if (head == NULL)
			goto errout;

		tcf_tree_lock(tp);
		tp->root = head;
		tcf_tree_unlock(tp);
	}

	f = kzalloc(sizeof(struct route4_filter), GFP_KERNEL);
	if (f == NULL)
		goto errout;

	err = route4_set_parms(tp, base, f, handle, head, tb,
		tca[TCA_RATE], 1);
	if (err < 0)
		goto errout;

reinsert:
	h = from_hash(f->handle >> 16);
	for (fp = &f->bkt->ht[h]; (f1=*fp) != NULL; fp = &f1->next)
		if (f->handle < f1->handle)
			break;

	f->next = f1;
	tcf_tree_lock(tp);
	*fp = f;

	if (old_handle && f->handle != old_handle) {
		th = to_hash(old_handle);
		h = from_hash(old_handle >> 16);
		if ((b = head->table[th]) != NULL) {
			for (fp = &b->ht[h]; *fp; fp = &(*fp)->next) {
				if (*fp == f) {
					*fp = f->next;
					break;
				}
			}
		}
	}
	tcf_tree_unlock(tp);

	route4_reset_fastmap(tp->q, head, f->id);
	*arg = (unsigned long)f;
	return 0;

errout:
	kfree(f);
	return err;
}

static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
{
	struct route4_head *head = tp->root;
	unsigned h, h1;

	if (head == NULL)
		arg->stop = 1;

	if (arg->stop)
		return;

	for (h = 0; h <= 256; h++) {
		struct route4_bucket *b = head->table[h];

		if (b) {
			for (h1 = 0; h1 <= 32; h1++) {
				struct route4_filter *f;

				for (f = b->ht[h1]; f; f = f->next) {
					if (arg->count < arg->skip) {
						arg->count++;
						continue;
					}
					if (arg->fn(tp, (unsigned long)f, arg) < 0) {
						arg->stop = 1;
						return;
					}
					arg->count++;
				}
			}
		}
	}
}

static int route4_dump(struct tcf_proto *tp, unsigned long fh,
		       struct sk_buff *skb, struct tcmsg *t)
{
	struct route4_filter *f = (struct route4_filter*)fh;
	unsigned char *b = skb_tail_pointer(skb);
	struct nlattr *nest;
	u32 id;

	if (f == NULL)
		return skb->len;

	t->tcm_handle = f->handle;

	nest = nla_nest_start(skb, TCA_OPTIONS);
	if (nest == NULL)
		goto nla_put_failure;

	if (!(f->handle&0x8000)) {
		id = f->id&0xFF;
		NLA_PUT_U32(skb, TCA_ROUTE4_TO, id);
	}
	if (f->handle&0x80000000) {
		if ((f->handle>>16) != 0xFFFF)
			NLA_PUT_U32(skb, TCA_ROUTE4_IIF, f->iif);
	} else {
		id = f->id>>16;
		NLA_PUT_U32(skb, TCA_ROUTE4_FROM, id);
	}
	if (f->res.classid)
		NLA_PUT_U32(skb, TCA_ROUTE4_CLASSID, f->res.classid);

	if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
		goto nla_put_failure;

	nla_nest_end(skb, nest);

	if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0)
		goto nla_put_failure;

	return skb->len;

nla_put_failure:
	nlmsg_trim(skb, b);
	return -1;
}

static struct tcf_proto_ops cls_route4_ops __read_mostly = {
	.kind		=	"route",
	.classify	=	route4_classify,
	.init		=	route4_init,
	.destroy	=	route4_destroy,
	.get		=	route4_get,
	.put		=	route4_put,
	.change		=	route4_change,
	.delete		=	route4_delete,
	.walk		=	route4_walk,
	.dump		=	route4_dump,
	.owner		=	THIS_MODULE,
};

static int __init init_route4(void)
{
	return register_tcf_proto_ops(&cls_route4_ops);
}

static void __exit exit_route4(void)
{
	unregister_tcf_proto_ops(&cls_route4_ops);
}

module_init(init_route4)
module_exit(exit_route4)
MODULE_LICENSE("GPL");
Commit	Line	Data
1da177e4 LT	1	/*
	2	* net/sched/cls_route.c ROUTE4 classifier.
	3	*
	4	* This program is free software; you can redistribute it and/or
	5	* modify it under the terms of the GNU General Public License
	6	* as published by the Free Software Foundation; either version
	7	* 2 of the License, or (at your option) any later version.
	8	*
	9	* Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
	10	*/
	11
	12	#include <linux/module.h>
5a0e3ad6	13	#include <linux/slab.h>
1da177e4 LT	14	#include <linux/types.h>
1da177e4 LT	15	#include <linux/kernel.h>
1da177e4	16	#include <linux/string.h>
1da177e4	17	#include <linux/errno.h>
1da177e4	18	#include <linux/skbuff.h>
0ba48053 PM	19	#include <net/dst.h>
	20	#include <net/route.h>
	21	#include <net/netlink.h>
1da177e4 LT	22	#include <net/act_api.h>
	23	#include <net/pkt_cls.h>
	24
	25	/*
	26	1. For now we assume that route tags < 256.
	27	It allows to use direct table lookups, instead of hash tables.
	28	2. For now we assume that "from TAG" and "fromdev DEV" statements
	29	are mutually exclusive.
	30	3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
	31	*/
	32
	33	struct route4_fastmap
	34	{
	35	struct route4_filter *filter;
	36	u32 id;
	37	int iif;
	38	};
	39
	40	struct route4_head
	41	{
	42	struct route4_fastmap fastmap[16];
	43	struct route4_bucket *table[256+1];
	44	};
	45
	46	struct route4_bucket
	47	{
	48	/* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
	49	struct route4_filter *ht[16+16+1];
	50	};
	51
	52	struct route4_filter
	53	{
	54	struct route4_filter *next;
	55	u32 id;
	56	int iif;
	57
	58	struct tcf_result res;
	59	struct tcf_exts exts;
	60	u32 handle;
	61	struct route4_bucket *bkt;
	62	};
	63
	64	#define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
	65
5239008b	66	static const struct tcf_ext_map route_ext_map = {
1da177e4 LT	67	.police = TCA_ROUTE4_POLICE,
	68	.action = TCA_ROUTE4_ACT
	69	};
	70
	71	static __inline__ int route4_fastmap_hash(u32 id, int iif)
	72	{
	73	return id&0xF;
	74	}
	75
	76	static inline
15b458fa	77	void route4_reset_fastmap(struct Qdisc q, struct route4_head head, u32 id)
1da177e4	78	{
102396ae	79	spinlock_t *root_lock = qdisc_root_sleeping_lock(q);
15b458fa DM	80
15b458fa DM	81	spin_lock_bh(root_lock);
1da177e4	82	memset(head->fastmap, 0, sizeof(head->fastmap));
15b458fa	83	spin_unlock_bh(root_lock);
1da177e4 LT	84	}
1da177e4 LT	85
b6f99a21	86	static inline void
1da177e4 LT	87	route4_set_fastmap(struct route4_head *head, u32 id, int iif,
	88	struct route4_filter *f)
	89	{
	90	int h = route4_fastmap_hash(id, iif);
	91	head->fastmap[h].id = id;
	92	head->fastmap[h].iif = iif;
	93	head->fastmap[h].filter = f;
	94	}
	95
	96	static __inline__ int route4_hash_to(u32 id)
	97	{
	98	return id&0xFF;
	99	}
	100
	101	static __inline__ int route4_hash_from(u32 id)
	102	{
	103	return (id>>16)&0xF;
	104	}
	105
	106	static __inline__ int route4_hash_iif(int iif)
	107	{
	108	return 16 + ((iif>>16)&0xF);
	109	}
	110
	111	static __inline__ int route4_hash_wild(void)
	112	{
	113	return 32;
	114	}
	115
	116	#define ROUTE4_APPLY_RESULT() \
	117	{ \
	118	*res = f->res; \
	119	if (tcf_exts_is_available(&f->exts)) { \
	120	int r = tcf_exts_exec(skb, &f->exts, res); \
	121	if (r < 0) { \
	122	dont_cache = 1; \
	123	continue; \
	124	} \
	125	return r; \
	126	} else if (!dont_cache) \
	127	route4_set_fastmap(head, id, iif, f); \
	128	return 0; \
	129	}
	130
	131	static int route4_classify(struct sk_buff skb, struct tcf_proto tp,
	132	struct tcf_result *res)
	133	{
	134	struct route4_head head = (struct route4_head)tp->root;
	135	struct dst_entry *dst;
	136	struct route4_bucket *b;
	137	struct route4_filter *f;
	138	u32 id, h;
	139	int iif, dont_cache = 0;
	140
adf30907	141	if ((dst = skb_dst(skb)) == NULL)
1da177e4 LT	142	goto failure;
	143
	144	id = dst->tclassid;
	145	if (head == NULL)
	146	goto old_method;
	147
	148	iif = ((struct rtable*)dst)->fl.iif;
	149
	150	h = route4_fastmap_hash(id, iif);
	151	if (id == head->fastmap[h].id &&
	152	iif == head->fastmap[h].iif &&
	153	(f = head->fastmap[h].filter) != NULL) {
	154	if (f == ROUTE4_FAILURE)
	155	goto failure;
	156
	157	*res = f->res;
	158	return 0;
	159	}
	160
	161	h = route4_hash_to(id);
	162
	163	restart:
	164	if ((b = head->table[h]) != NULL) {
	165	for (f = b->ht[route4_hash_from(id)]; f; f = f->next)
	166	if (f->id == id)
	167	ROUTE4_APPLY_RESULT();
	168
	169	for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)
	170	if (f->iif == iif)
	171	ROUTE4_APPLY_RESULT();
	172
	173	for (f = b->ht[route4_hash_wild()]; f; f = f->next)
	174	ROUTE4_APPLY_RESULT();
	175
	176	}
	177	if (h < 256) {
	178	h = 256;
	179	id &= ~0xFFFF;
	180	goto restart;
	181	}
	182
	183	if (!dont_cache)
	184	route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
	185	failure:
	186	return -1;
	187
	188	old_method:
	189	if (id && (TC_H_MAJ(id) == 0 \|\|
	190	!(TC_H_MAJ(id^tp->q->handle)))) {
	191	res->classid = id;
	192	res->class = 0;
	193	return 0;
	194	}
	195	return -1;
	196	}
	197
	198	static inline u32 to_hash(u32 id)
	199	{
	200	u32 h = id&0xFF;
	201	if (id&0x8000)
	202	h += 256;
	203	return h;
	204	}
	205
206	static inline u32 from_hash(u32 id)
207	{
208	id &= 0xFFFF;
209	if (id == 0xFFFF)
210	return 32;
211	if (!(id & 0x8000)) {
212	if (id > 255)
213	return 256;
214	return id&0xF;
215	}
216	return 16 + (id&0xF);
217	}
218
219	static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
220	{
221	struct route4_head head = (struct route4_head)tp->root;
222	struct route4_bucket *b;
223	struct route4_filter *f;
224	unsigned h1, h2;
225
226	if (!head)
227	return 0;
228
229	h1 = to_hash(handle);
230	if (h1 > 256)
231	return 0;
232
233	h2 = from_hash(handle>>16);
234	if (h2 > 32)
235	return 0;
236
237	if ((b = head->table[h1]) != NULL) {
238	for (f = b->ht[h2]; f; f = f->next)
239	if (f->handle == handle)
240	return (unsigned long)f;
241	}
242	return 0;
243	}
244
245	static void route4_put(struct tcf_proto *tp, unsigned long f)
246	{
247	}
248
249	static int route4_init(struct tcf_proto *tp)
250	{
251	return 0;
252	}
253
254	static inline void
255	route4_delete_filter(struct tcf_proto tp, struct route4_filter f)
256	{
257	tcf_unbind_filter(tp, &f->res);
258	tcf_exts_destroy(tp, &f->exts);
259	kfree(f);
260	}
261
262	static void route4_destroy(struct tcf_proto *tp)
263	{
47a1a1d4	264	struct route4_head *head = tp->root;
1da177e4 LT	265	int h1, h2;
	266
	267	if (head == NULL)
	268	return;
	269
	270	for (h1=0; h1<=256; h1++) {
	271	struct route4_bucket *b;
	272
	273	if ((b = head->table[h1]) != NULL) {
	274	for (h2=0; h2<=32; h2++) {
	275	struct route4_filter *f;
	276
	277	while ((f = b->ht[h2]) != NULL) {
	278	b->ht[h2] = f->next;
	279	route4_delete_filter(tp, f);
	280	}
	281	}
	282	kfree(b);
	283	}
	284	}
	285	kfree(head);
	286	}
	287
	288	static int route4_delete(struct tcf_proto *tp, unsigned long arg)
	289	{
	290	struct route4_head head = (struct route4_head)tp->root;
	291	struct route4_filter *fp, f = (struct route4_filter*)arg;
	292	unsigned h = 0;
	293	struct route4_bucket *b;
	294	int i;
	295
	296	if (!head \|\| !f)
	297	return -EINVAL;
	298
	299	h = f->handle;
	300	b = f->bkt;
	301
	302	for (fp = &b->ht[from_hash(h>>16)]; fp; fp = &(fp)->next) {
	303	if (*fp == f) {
	304	tcf_tree_lock(tp);
	305	*fp = f->next;
	306	tcf_tree_unlock(tp);
	307
15b458fa	308	route4_reset_fastmap(tp->q, head, f->id);
1da177e4 LT	309	route4_delete_filter(tp, f);
	310
	311	/* Strip tree */
	312
	313	for (i=0; i<=32; i++)
	314	if (b->ht[i])
	315	return 0;
	316
	317	/* OK, session has no flows */
	318	tcf_tree_lock(tp);
	319	head->table[to_hash(h)] = NULL;
	320	tcf_tree_unlock(tp);
	321
	322	kfree(b);
	323	return 0;
	324	}
	325	}
	326	return 0;
	327	}
	328
6fa8c014 PM	329	static const struct nla_policy route4_policy[TCA_ROUTE4_MAX + 1] = {
	330	[TCA_ROUTE4_CLASSID] = { .type = NLA_U32 },
	331	[TCA_ROUTE4_TO] = { .type = NLA_U32 },
	332	[TCA_ROUTE4_FROM] = { .type = NLA_U32 },
	333	[TCA_ROUTE4_IIF] = { .type = NLA_U32 },
	334	};
	335
1da177e4 LT	336	static int route4_set_parms(struct tcf_proto *tp, unsigned long base,
1da177e4 LT	337	struct route4_filter f, u32 handle, struct route4_head head,
add93b61	338	struct nlattr *tb, struct nlattr est, int new)
1da177e4 LT	339	{
	340	int err;
	341	u32 id = 0, to = 0, nhandle = 0x8000;
	342	struct route4_filter *fp;
	343	unsigned int h1;
	344	struct route4_bucket *b;
	345	struct tcf_exts e;
	346
	347	err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map);
	348	if (err < 0)
	349	return err;
	350
	351	err = -EINVAL;
add93b61	352	if (tb[TCA_ROUTE4_TO]) {
1da177e4 LT	353	if (new && handle & 0x8000)
1da177e4 LT	354	goto errout;
1587bac4	355	to = nla_get_u32(tb[TCA_ROUTE4_TO]);
1da177e4 LT	356	if (to > 0xFF)
	357	goto errout;
	358	nhandle = to;
	359	}
	360
add93b61 PM	361	if (tb[TCA_ROUTE4_FROM]) {
add93b61 PM	362	if (tb[TCA_ROUTE4_IIF])
1da177e4	363	goto errout;
1587bac4	364	id = nla_get_u32(tb[TCA_ROUTE4_FROM]);
1da177e4 LT	365	if (id > 0xFF)
	366	goto errout;
	367	nhandle \|= id << 16;
add93b61	368	} else if (tb[TCA_ROUTE4_IIF]) {
1587bac4	369	id = nla_get_u32(tb[TCA_ROUTE4_IIF]);
1da177e4 LT	370	if (id > 0x7FFF)
	371	goto errout;
	372	nhandle \|= (id \| 0x8000) << 16;
	373	} else
	374	nhandle \|= 0xFFFF << 16;
	375
	376	if (handle && new) {
	377	nhandle \|= handle & 0x7F00;
	378	if (nhandle != handle)
	379	goto errout;
	380	}
	381
	382	h1 = to_hash(nhandle);
	383	if ((b = head->table[h1]) == NULL) {
	384	err = -ENOBUFS;
0da974f4	385	b = kzalloc(sizeof(struct route4_bucket), GFP_KERNEL);
1da177e4 LT	386	if (b == NULL)
1da177e4 LT	387	goto errout;
1da177e4 LT	388
	389	tcf_tree_lock(tp);
	390	head->table[h1] = b;
	391	tcf_tree_unlock(tp);
	392	} else {
	393	unsigned int h2 = from_hash(nhandle >> 16);
	394	err = -EEXIST;
	395	for (fp = b->ht[h2]; fp; fp = fp->next)
	396	if (fp->handle == f->handle)
	397	goto errout;
	398	}
	399
	400	tcf_tree_lock(tp);
add93b61	401	if (tb[TCA_ROUTE4_TO])
1da177e4 LT	402	f->id = to;
1da177e4 LT	403
add93b61	404	if (tb[TCA_ROUTE4_FROM])
1da177e4	405	f->id = to \| id<<16;
add93b61	406	else if (tb[TCA_ROUTE4_IIF])
1da177e4 LT	407	f->iif = id;
	408
	409	f->handle = nhandle;
	410	f->bkt = b;
	411	tcf_tree_unlock(tp);
	412
add93b61	413	if (tb[TCA_ROUTE4_CLASSID]) {
1587bac4	414	f->res.classid = nla_get_u32(tb[TCA_ROUTE4_CLASSID]);
1da177e4 LT	415	tcf_bind_filter(tp, &f->res, base);
	416	}
	417
	418	tcf_exts_change(tp, &f->exts, &e);
	419
	420	return 0;
	421	errout:
	422	tcf_exts_destroy(tp, &e);
	423	return err;
	424	}
	425
	426	static int route4_change(struct tcf_proto *tp, unsigned long base,
	427	u32 handle,
add93b61	428	struct nlattr **tca,
1da177e4 LT	429	unsigned long *arg)
	430	{
	431	struct route4_head *head = tp->root;
	432	struct route4_filter f, f1, **fp;
	433	struct route4_bucket *b;
add93b61 PM	434	struct nlattr *opt = tca[TCA_OPTIONS];
add93b61 PM	435	struct nlattr *tb[TCA_ROUTE4_MAX + 1];
1da177e4 LT	436	unsigned int h, th;
	437	u32 old_handle = 0;
	438	int err;
	439
	440	if (opt == NULL)
	441	return handle ? -EINVAL : 0;
	442
6fa8c014	443	err = nla_parse_nested(tb, TCA_ROUTE4_MAX, opt, route4_policy);
cee63723 PM	444	if (err < 0)
cee63723 PM	445	return err;
1da177e4 LT	446
	447	if ((f = (struct route4_filter)arg) != NULL) {
	448	if (f->handle != handle && handle)
	449	return -EINVAL;
	450
	451	if (f->bkt)
	452	old_handle = f->handle;
	453
	454	err = route4_set_parms(tp, base, f, handle, head, tb,
add93b61	455	tca[TCA_RATE], 0);
1da177e4 LT	456	if (err < 0)
	457	return err;
	458
	459	goto reinsert;
	460	}
	461
	462	err = -ENOBUFS;
	463	if (head == NULL) {
0da974f4	464	head = kzalloc(sizeof(struct route4_head), GFP_KERNEL);
1da177e4 LT	465	if (head == NULL)
1da177e4 LT	466	goto errout;
1da177e4 LT	467
	468	tcf_tree_lock(tp);
	469	tp->root = head;
	470	tcf_tree_unlock(tp);
	471	}
	472
0da974f4	473	f = kzalloc(sizeof(struct route4_filter), GFP_KERNEL);
1da177e4 LT	474	if (f == NULL)
1da177e4 LT	475	goto errout;
1da177e4 LT	476
1da177e4 LT	477	err = route4_set_parms(tp, base, f, handle, head, tb,
add93b61	478	tca[TCA_RATE], 1);
1da177e4 LT	479	if (err < 0)
	480	goto errout;
	481
	482	reinsert:
	483	h = from_hash(f->handle >> 16);
	484	for (fp = &f->bkt->ht[h]; (f1=*fp) != NULL; fp = &f1->next)
	485	if (f->handle < f1->handle)
	486	break;
	487
	488	f->next = f1;
	489	tcf_tree_lock(tp);
	490	*fp = f;
	491
	492	if (old_handle && f->handle != old_handle) {
	493	th = to_hash(old_handle);
	494	h = from_hash(old_handle >> 16);
	495	if ((b = head->table[th]) != NULL) {
	496	for (fp = &b->ht[h]; fp; fp = &(fp)->next) {
	497	if (*fp == f) {
	498	*fp = f->next;
	499	break;
	500	}
	501	}
	502	}
	503	}
	504	tcf_tree_unlock(tp);
	505
15b458fa	506	route4_reset_fastmap(tp->q, head, f->id);
1da177e4 LT	507	*arg = (unsigned long)f;
	508	return 0;
	509
	510	errout:
a51482bd	511	kfree(f);
1da177e4 LT	512	return err;
	513	}
	514
	515	static void route4_walk(struct tcf_proto tp, struct tcf_walker arg)
	516	{
	517	struct route4_head *head = tp->root;
	518	unsigned h, h1;
	519
	520	if (head == NULL)
	521	arg->stop = 1;
	522
	523	if (arg->stop)
	524	return;
	525
	526	for (h = 0; h <= 256; h++) {
	527	struct route4_bucket *b = head->table[h];
	528
	529	if (b) {
	530	for (h1 = 0; h1 <= 32; h1++) {
	531	struct route4_filter *f;
	532
	533	for (f = b->ht[h1]; f; f = f->next) {
	534	if (arg->count < arg->skip) {
	535	arg->count++;
	536	continue;
	537	}
	538	if (arg->fn(tp, (unsigned long)f, arg) < 0) {
	539	arg->stop = 1;
	540	return;
	541	}
	542	arg->count++;
	543	}
	544	}
	545	}
	546	}
	547	}
	548
	549	static int route4_dump(struct tcf_proto *tp, unsigned long fh,
	550	struct sk_buff skb, struct tcmsg t)
	551	{
	552	struct route4_filter f = (struct route4_filter)fh;
27a884dc	553	unsigned char *b = skb_tail_pointer(skb);
4b3550ef	554	struct nlattr *nest;
1da177e4 LT	555	u32 id;
	556
	557	if (f == NULL)
	558	return skb->len;
	559
	560	t->tcm_handle = f->handle;
	561
4b3550ef PM	562	nest = nla_nest_start(skb, TCA_OPTIONS);
	563	if (nest == NULL)
	564	goto nla_put_failure;
1da177e4 LT	565
	566	if (!(f->handle&0x8000)) {
	567	id = f->id&0xFF;
24beeab5	568	NLA_PUT_U32(skb, TCA_ROUTE4_TO, id);
1da177e4 LT	569	}
	570	if (f->handle&0x80000000) {
	571	if ((f->handle>>16) != 0xFFFF)
24beeab5	572	NLA_PUT_U32(skb, TCA_ROUTE4_IIF, f->iif);
1da177e4 LT	573	} else {
1da177e4 LT	574	id = f->id>>16;
24beeab5	575	NLA_PUT_U32(skb, TCA_ROUTE4_FROM, id);
1da177e4 LT	576	}
1da177e4 LT	577	if (f->res.classid)
24beeab5	578	NLA_PUT_U32(skb, TCA_ROUTE4_CLASSID, f->res.classid);
1da177e4 LT	579
1da177e4 LT	580	if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
add93b61	581	goto nla_put_failure;
1da177e4	582
4b3550ef	583	nla_nest_end(skb, nest);
1da177e4 LT	584
1da177e4 LT	585	if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0)
add93b61	586	goto nla_put_failure;
1da177e4 LT	587
	588	return skb->len;
	589
add93b61	590	nla_put_failure:
dc5fc579	591	nlmsg_trim(skb, b);
1da177e4 LT	592	return -1;
	593	}
	594
2eb9d75c	595	static struct tcf_proto_ops cls_route4_ops __read_mostly = {
1da177e4 LT	596	.kind = "route",
	597	.classify = route4_classify,
	598	.init = route4_init,
	599	.destroy = route4_destroy,
	600	.get = route4_get,
	601	.put = route4_put,
	602	.change = route4_change,
	603	.delete = route4_delete,
	604	.walk = route4_walk,
	605	.dump = route4_dump,
	606	.owner = THIS_MODULE,
	607	};
	608
	609	static int __init init_route4(void)
	610	{
	611	return register_tcf_proto_ops(&cls_route4_ops);
	612	}
	613
	614	static void __exit exit_route4(void)
	615	{
	616	unregister_tcf_proto_ops(&cls_route4_ops);
	617	}
	618
	619	module_init(init_route4)
	620	module_exit(exit_route4)
	621	MODULE_LICENSE("GPL");