[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 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 rtattr **tb, struct rtattr *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-1])
		if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < sizeof(u32))
			goto errout;

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

	if (tb[TCA_ROUTE4_FROM-1]) {
		if (tb[TCA_ROUTE4_IIF-1])
			goto errout;
		if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < sizeof(u32))
			goto errout;
		id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_FROM-1]);
		if (id > 0xFF)
			goto errout;
		nhandle |= id << 16;
	} else if (tb[TCA_ROUTE4_IIF-1]) {
		if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < sizeof(u32))
			goto errout;
		id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);
		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-1])
		f->id = to;

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

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

	if (tb[TCA_ROUTE4_CLASSID-1]) {
		f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
		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 rtattr **tca,
		       unsigned long *arg)
{
	struct route4_head *head = tp->root;
	struct route4_filter *f, *f1, **fp;
	struct route4_bucket *b;
	struct rtattr *opt = tca[TCA_OPTIONS-1];
	struct rtattr *tb[TCA_ROUTE4_MAX];
	unsigned int h, th;
	u32 old_handle = 0;
	int err;

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

	if (rtattr_parse_nested(tb, TCA_ROUTE4_MAX, opt) < 0)
		return -EINVAL;

	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-1], 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], 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 rtattr *rta;
	u32 id;

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

	t->tcm_handle = f->handle;

	rta = (struct rtattr*)b;
	RTA_PUT(skb, TCA_OPTIONS, 0, NULL);

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

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

	rta->rta_len = skb_tail_pointer(skb) - b;

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

	return skb->len;

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

static struct tcf_proto_ops cls_route4_ops = {
	.next		=	NULL,
	.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,
328	struct rtattr *tb, struct rtattr est, int new)
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;
342	if (tb[TCA_ROUTE4_CLASSID-1])
343	if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < sizeof(u32))
344	goto errout;
345
346	if (tb[TCA_ROUTE4_TO-1]) {
347	if (new && handle & 0x8000)
348	goto errout;
349	if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < sizeof(u32))
350	goto errout;
351	to = (u32)RTA_DATA(tb[TCA_ROUTE4_TO-1]);
352	if (to > 0xFF)
353	goto errout;
354	nhandle = to;
355	}
356
357	if (tb[TCA_ROUTE4_FROM-1]) {
358	if (tb[TCA_ROUTE4_IIF-1])
359	goto errout;
360	if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < sizeof(u32))
361	goto errout;
362	id = (u32)RTA_DATA(tb[TCA_ROUTE4_FROM-1]);
363	if (id > 0xFF)
364	goto errout;
365	nhandle \|= id << 16;
366	} else if (tb[TCA_ROUTE4_IIF-1]) {
367	if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < sizeof(u32))
368	goto errout;
369	id = (u32)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);
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);
	401	if (tb[TCA_ROUTE4_TO-1])
	402	f->id = to;
	403
	404	if (tb[TCA_ROUTE4_FROM-1])
	405	f->id = to \| id<<16;
	406	else if (tb[TCA_ROUTE4_IIF-1])
	407	f->iif = id;
	408
	409	f->handle = nhandle;
	410	f->bkt = b;
	411	tcf_tree_unlock(tp);
	412
	413	if (tb[TCA_ROUTE4_CLASSID-1]) {
	414	f->res.classid = (u32)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
	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,
	428	struct rtattr **tca,
	429	unsigned long *arg)
	430	{
	431	struct route4_head *head = tp->root;
	432	struct route4_filter f, f1, **fp;
	433	struct route4_bucket *b;
	434	struct rtattr *opt = tca[TCA_OPTIONS-1];
	435	struct rtattr *tb[TCA_ROUTE4_MAX];
	436	unsigned int h, th;
	437	u32 old_handle = 0;
	438	int err;
	439
	440	if (opt == NULL)
	441	return handle ? -EINVAL : 0;
	442
	443	if (rtattr_parse_nested(tb, TCA_ROUTE4_MAX, opt) < 0)
	444	return -EINVAL;
	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,
454	tca[TCA_RATE-1], 0);
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
	476	err = route4_set_parms(tp, base, f, handle, head, tb,
	477	tca[TCA_RATE-1], 1);
	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
	505	route4_reset_fastmap(tp->q->dev, head, f->id);
	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);
1da177e4 LT	553	struct rtattr *rta;
	554	u32 id;
	555
	556	if (f == NULL)
	557	return skb->len;
	558
	559	t->tcm_handle = f->handle;
	560
	561	rta = (struct rtattr*)b;
	562	RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
	563
	564	if (!(f->handle&0x8000)) {
	565	id = f->id&0xFF;
	566	RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);
	567	}
	568	if (f->handle&0x80000000) {
	569	if ((f->handle>>16) != 0xFFFF)
	570	RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
	571	} else {
	572	id = f->id>>16;
	573	RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
	574	}
	575	if (f->res.classid)
	576	RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);
	577
	578	if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
	579	goto rtattr_failure;
	580
27a884dc	581	rta->rta_len = skb_tail_pointer(skb) - b;
1da177e4 LT	582
	583	if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0)
	584	goto rtattr_failure;
	585
	586	return skb->len;
	587
	588	rtattr_failure:
dc5fc579	589	nlmsg_trim(skb, b);
1da177e4 LT	590	return -1;
	591	}
	592
	593	static struct tcf_proto_ops cls_route4_ops = {
	594	.next = NULL,
	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");