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