[mirror_ubuntu-artful-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 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 net_device *dev, struct route4_head *head, u32 id)
{
	qdisc_lock_tree(dev);
	memset(head->fastmap, 0, sizeof(head->fastmap));
	qdisc_unlock_tree(dev);
}

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) == 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 = xchg(&tp->root, NULL);
	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->dev, 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 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_CLASSID])
		if (nla_len(tb[TCA_ROUTE4_CLASSID]) < sizeof(u32))
			goto errout;

	if (tb[TCA_ROUTE4_TO]) {
		if (new && handle & 0x8000)
			goto errout;
		if (nla_len(tb[TCA_ROUTE4_TO]) < sizeof(u32))
			goto errout;
		to = *(u32*)nla_data(tb[TCA_ROUTE4_TO]);
		if (to > 0xFF)
			goto errout;
		nhandle = to;
	}

	if (tb[TCA_ROUTE4_FROM]) {
		if (tb[TCA_ROUTE4_IIF])
			goto errout;
		if (nla_len(tb[TCA_ROUTE4_FROM]) < sizeof(u32))
			goto errout;
		id = *(u32*)nla_data(tb[TCA_ROUTE4_FROM]);
		if (id > 0xFF)
			goto errout;
		nhandle |= id << 16;
	} else if (tb[TCA_ROUTE4_IIF]) {
		if (nla_len(tb[TCA_ROUTE4_IIF]) < sizeof(u32))
			goto errout;
		id = *(u32*)nla_data(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 = *(u32*)nla_data(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, NULL);
	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->dev, 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(skb, TCA_ROUTE4_TO, sizeof(id), &id);
	}
	if (f->handle&0x80000000) {
		if ((f->handle>>16) != 0xFFFF)
			NLA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
	} else {
		id = f->id>>16;
		NLA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
	}
	if (f->res.classid)
		NLA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &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
	65	static struct tcf_ext_map route_ext_map = {
	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
	76	void route4_reset_fastmap(struct net_device dev, struct route4_head head, u32 id)
	77	{
fd44de7c	78	qdisc_lock_tree(dev);
1da177e4	79	memset(head->fastmap, 0, sizeof(head->fastmap));
fd44de7c	80	qdisc_unlock_tree(dev);
1da177e4 LT	81	}
1da177e4 LT	82
b6f99a21	83	static inline void
1da177e4 LT	84	route4_set_fastmap(struct route4_head *head, u32 id, int iif,
	85	struct route4_filter *f)
	86	{
	87	int h = route4_fastmap_hash(id, iif);
	88	head->fastmap[h].id = id;
	89	head->fastmap[h].iif = iif;
	90	head->fastmap[h].filter = f;
	91	}
	92
	93	static __inline__ int route4_hash_to(u32 id)
	94	{
	95	return id&0xFF;
	96	}
	97
	98	static __inline__ int route4_hash_from(u32 id)
	99	{
	100	return (id>>16)&0xF;
	101	}
	102
	103	static __inline__ int route4_hash_iif(int iif)
	104	{
	105	return 16 + ((iif>>16)&0xF);
	106	}
	107
	108	static __inline__ int route4_hash_wild(void)
	109	{
	110	return 32;
	111	}
	112
	113	#define ROUTE4_APPLY_RESULT() \
	114	{ \
	115	*res = f->res; \
	116	if (tcf_exts_is_available(&f->exts)) { \
	117	int r = tcf_exts_exec(skb, &f->exts, res); \
	118	if (r < 0) { \
	119	dont_cache = 1; \
	120	continue; \
	121	} \
	122	return r; \
	123	} else if (!dont_cache) \
	124	route4_set_fastmap(head, id, iif, f); \
	125	return 0; \
	126	}
	127
	128	static int route4_classify(struct sk_buff skb, struct tcf_proto tp,
	129	struct tcf_result *res)
	130	{
	131	struct route4_head head = (struct route4_head)tp->root;
	132	struct dst_entry *dst;
	133	struct route4_bucket *b;
	134	struct route4_filter *f;
	135	u32 id, h;
	136	int iif, dont_cache = 0;
	137
	138	if ((dst = skb->dst) == NULL)
	139	goto failure;
	140
	141	id = dst->tclassid;
	142	if (head == NULL)
	143	goto old_method;
	144
	145	iif = ((struct rtable*)dst)->fl.iif;
	146
	147	h = route4_fastmap_hash(id, iif);
148	if (id == head->fastmap[h].id &&
149	iif == head->fastmap[h].iif &&
150	(f = head->fastmap[h].filter) != NULL) {
151	if (f == ROUTE4_FAILURE)
152	goto failure;
153
154	*res = f->res;
155	return 0;
156	}
157
158	h = route4_hash_to(id);
159
160	restart:
161	if ((b = head->table[h]) != NULL) {
162	for (f = b->ht[route4_hash_from(id)]; f; f = f->next)
163	if (f->id == id)
164	ROUTE4_APPLY_RESULT();
165
166	for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)
167	if (f->iif == iif)
168	ROUTE4_APPLY_RESULT();
169
170	for (f = b->ht[route4_hash_wild()]; f; f = f->next)
171	ROUTE4_APPLY_RESULT();
172
173	}
174	if (h < 256) {
175	h = 256;
176	id &= ~0xFFFF;
177	goto restart;
178	}
179
180	if (!dont_cache)
181	route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
182	failure:
183	return -1;
184
185	old_method:
186	if (id && (TC_H_MAJ(id) == 0 \|\|
187	!(TC_H_MAJ(id^tp->q->handle)))) {
188	res->classid = id;
189	res->class = 0;
190	return 0;
191	}
192	return -1;
193	}
194
195	static inline u32 to_hash(u32 id)
196	{
197	u32 h = id&0xFF;
198	if (id&0x8000)
199	h += 256;
200	return h;
201	}
202
203	static inline u32 from_hash(u32 id)
204	{
205	id &= 0xFFFF;
206	if (id == 0xFFFF)
207	return 32;
208	if (!(id & 0x8000)) {
209	if (id > 255)
210	return 256;
211	return id&0xF;
212	}
213	return 16 + (id&0xF);
214	}
215
216	static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
217	{
218	struct route4_head head = (struct route4_head)tp->root;
219	struct route4_bucket *b;
220	struct route4_filter *f;
221	unsigned h1, h2;
222
223	if (!head)
224	return 0;
225
226	h1 = to_hash(handle);
227	if (h1 > 256)
228	return 0;
229
230	h2 = from_hash(handle>>16);
231	if (h2 > 32)
232	return 0;
233
234	if ((b = head->table[h1]) != NULL) {
235	for (f = b->ht[h2]; f; f = f->next)
236	if (f->handle == handle)
237	return (unsigned long)f;
238	}
239	return 0;
240	}
241
242	static void route4_put(struct tcf_proto *tp, unsigned long f)
243	{
244	}
245
246	static int route4_init(struct tcf_proto *tp)
247	{
248	return 0;
249	}
250
251	static inline void
252	route4_delete_filter(struct tcf_proto tp, struct route4_filter f)
253	{
254	tcf_unbind_filter(tp, &f->res);
255	tcf_exts_destroy(tp, &f->exts);
256	kfree(f);
257	}
258
259	static void route4_destroy(struct tcf_proto *tp)
260	{
261	struct route4_head *head = xchg(&tp->root, NULL);
262	int h1, h2;
263
264	if (head == NULL)
265	return;
266
267	for (h1=0; h1<=256; h1++) {
268	struct route4_bucket *b;
269
270	if ((b = head->table[h1]) != NULL) {
271	for (h2=0; h2<=32; h2++) {
272	struct route4_filter *f;
273
274	while ((f = b->ht[h2]) != NULL) {
275	b->ht[h2] = f->next;
276	route4_delete_filter(tp, f);
277	}
278	}
279	kfree(b);
280	}
281	}
282	kfree(head);
283	}
284
285	static int route4_delete(struct tcf_proto *tp, unsigned long arg)
286	{
287	struct route4_head head = (struct route4_head)tp->root;
288	struct route4_filter *fp, f = (struct route4_filter*)arg;
289	unsigned h = 0;
290	struct route4_bucket *b;
291	int i;
292
293	if (!head \|\| !f)
294	return -EINVAL;
295
296	h = f->handle;
297	b = f->bkt;
298
299	for (fp = &b->ht[from_hash(h>>16)]; fp; fp = &(fp)->next) {
300	if (*fp == f) {
301	tcf_tree_lock(tp);
302	*fp = f->next;
303	tcf_tree_unlock(tp);
304
305	route4_reset_fastmap(tp->q->dev, head, f->id);
306	route4_delete_filter(tp, f);
307
308	/* Strip tree */
309
310	for (i=0; i<=32; i++)
311	if (b->ht[i])
312	return 0;
313
314	/* OK, session has no flows */
315	tcf_tree_lock(tp);
316	head->table[to_hash(h)] = NULL;
317	tcf_tree_unlock(tp);
318
319	kfree(b);
320	return 0;
321	}
322	}
323	return 0;
324	}
325
326	static int route4_set_parms(struct tcf_proto *tp, unsigned long base,
327	struct route4_filter f, u32 handle, struct route4_head head,
add93b61	328	struct nlattr *tb, struct nlattr est, int new)
1da177e4 LT	329	{
	330	int err;
	331	u32 id = 0, to = 0, nhandle = 0x8000;
	332	struct route4_filter *fp;
	333	unsigned int h1;
	334	struct route4_bucket *b;
	335	struct tcf_exts e;
	336
	337	err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map);
	338	if (err < 0)
	339	return err;
	340
	341	err = -EINVAL;
add93b61 PM	342	if (tb[TCA_ROUTE4_CLASSID])
add93b61 PM	343	if (nla_len(tb[TCA_ROUTE4_CLASSID]) < sizeof(u32))
1da177e4 LT	344	goto errout;
1da177e4 LT	345
add93b61	346	if (tb[TCA_ROUTE4_TO]) {
1da177e4 LT	347	if (new && handle & 0x8000)
1da177e4 LT	348	goto errout;
add93b61	349	if (nla_len(tb[TCA_ROUTE4_TO]) < sizeof(u32))
1da177e4	350	goto errout;
add93b61	351	to = (u32)nla_data(tb[TCA_ROUTE4_TO]);
1da177e4 LT	352	if (to > 0xFF)
	353	goto errout;
	354	nhandle = to;
	355	}
	356
add93b61 PM	357	if (tb[TCA_ROUTE4_FROM]) {
add93b61 PM	358	if (tb[TCA_ROUTE4_IIF])
1da177e4	359	goto errout;
add93b61	360	if (nla_len(tb[TCA_ROUTE4_FROM]) < sizeof(u32))
1da177e4	361	goto errout;
add93b61	362	id = (u32)nla_data(tb[TCA_ROUTE4_FROM]);
1da177e4 LT	363	if (id > 0xFF)
	364	goto errout;
	365	nhandle \|= id << 16;
add93b61 PM	366	} else if (tb[TCA_ROUTE4_IIF]) {
add93b61 PM	367	if (nla_len(tb[TCA_ROUTE4_IIF]) < sizeof(u32))
1da177e4	368	goto errout;
add93b61	369	id = (u32)nla_data(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 PM	413	if (tb[TCA_ROUTE4_CLASSID]) {
add93b61 PM	414	f->res.classid = (u32)nla_data(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
cee63723 PM	443	err = nla_parse_nested(tb, TCA_ROUTE4_MAX, opt, NULL);
	444	if (err < 0)
	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
	506	route4_reset_fastmap(tp->q->dev, head, f->id);
	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;
add93b61	568	NLA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);
1da177e4 LT	569	}
	570	if (f->handle&0x80000000) {
	571	if ((f->handle>>16) != 0xFFFF)
add93b61	572	NLA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
1da177e4 LT	573	} else {
1da177e4 LT	574	id = f->id>>16;
add93b61	575	NLA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
1da177e4 LT	576	}
1da177e4 LT	577	if (f->res.classid)
add93b61	578	NLA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &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");