cls_route.c revision 1b34ec43c9b3de44a5420841ab293d1b2035a94c 
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>
13#include <linux/slab.h>
14#include <linux/types.h>
15#include <linux/kernel.h>
16#include <linux/string.h>
17#include <linux/errno.h>
18#include <linux/skbuff.h>
19#include <net/dst.h>
20#include <net/route.h>
21#include <net/netlink.h>
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
33struct route4_fastmap {
34	struct route4_filter	*filter;
35	u32			id;
36	int			iif;
37};
38
39struct route4_head {
40	struct route4_fastmap	fastmap[16];
41	struct route4_bucket	*table[256 + 1];
42};
43
44struct route4_bucket {
45	/* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
46	struct route4_filter	*ht[16 + 16 + 1];
47};
48
49struct route4_filter {
50	struct route4_filter	*next;
51	u32			id;
52	int			iif;
53
54	struct tcf_result	res;
55	struct tcf_exts		exts;
56	u32			handle;
57	struct route4_bucket	*bkt;
58};
59
60#define ROUTE4_FAILURE ((struct route4_filter *)(-1L))
61
62static const struct tcf_ext_map route_ext_map = {
63	.police = TCA_ROUTE4_POLICE,
64	.action = TCA_ROUTE4_ACT
65};
66
67static inline int route4_fastmap_hash(u32 id, int iif)
68{
69	return id & 0xF;
70}
71
72static void
73route4_reset_fastmap(struct Qdisc *q, struct route4_head *head, u32 id)
74{
75	spinlock_t *root_lock = qdisc_root_sleeping_lock(q);
76
77	spin_lock_bh(root_lock);
78	memset(head->fastmap, 0, sizeof(head->fastmap));
79	spin_unlock_bh(root_lock);
80}
81
82static void
83route4_set_fastmap(struct route4_head *head, u32 id, int iif,
84		   struct route4_filter *f)
85{
86	int h = route4_fastmap_hash(id, iif);
87
88	head->fastmap[h].id = id;
89	head->fastmap[h].iif = iif;
90	head->fastmap[h].filter = f;
91}
92
93static inline int route4_hash_to(u32 id)
94{
95	return id & 0xFF;
96}
97
98static inline int route4_hash_from(u32 id)
99{
100	return (id >> 16) & 0xF;
101}
102
103static inline int route4_hash_iif(int iif)
104{
105	return 16 + ((iif >> 16) & 0xF);
106}
107
108static 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
128static int route4_classify(struct sk_buff *skb, const 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	dst = skb_dst(skb);
139	if (!dst)
140		goto failure;
141
142	id = dst->tclassid;
143	if (head == NULL)
144		goto old_method;
145
146	iif = ((struct rtable *)dst)->rt_iif;
147
148	h = route4_fastmap_hash(id, iif);
149	if (id == head->fastmap[h].id &&
150	    iif == head->fastmap[h].iif &&
151	    (f = head->fastmap[h].filter) != NULL) {
152		if (f == ROUTE4_FAILURE)
153			goto failure;
154
155		*res = f->res;
156		return 0;
157	}
158
159	h = route4_hash_to(id);
160
161restart:
162	b = head->table[h];
163	if (b) {
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);
184failure:
185	return -1;
186
187old_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
197static inline u32 to_hash(u32 id)
198{
199	u32 h = id & 0xFF;
200
201	if (id & 0x8000)
202		h += 256;
203	return h;
204}
205
206static 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
219static 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 int 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	b = head->table[h1];
238	if (b) {
239		for (f = b->ht[h2]; f; f = f->next)
240			if (f->handle == handle)
241				return (unsigned long)f;
242	}
243	return 0;
244}
245
246static void route4_put(struct tcf_proto *tp, unsigned long f)
247{
248}
249
250static int route4_init(struct tcf_proto *tp)
251{
252	return 0;
253}
254
255static void
256route4_delete_filter(struct tcf_proto *tp, struct route4_filter *f)
257{
258	tcf_unbind_filter(tp, &f->res);
259	tcf_exts_destroy(tp, &f->exts);
260	kfree(f);
261}
262
263static void route4_destroy(struct tcf_proto *tp)
264{
265	struct route4_head *head = tp->root;
266	int h1, h2;
267
268	if (head == NULL)
269		return;
270
271	for (h1 = 0; h1 <= 256; h1++) {
272		struct route4_bucket *b;
273
274		b = head->table[h1];
275		if (b) {
276			for (h2 = 0; h2 <= 32; h2++) {
277				struct route4_filter *f;
278
279				while ((f = b->ht[h2]) != NULL) {
280					b->ht[h2] = f->next;
281					route4_delete_filter(tp, f);
282				}
283			}
284			kfree(b);
285		}
286	}
287	kfree(head);
288}
289
290static int route4_delete(struct tcf_proto *tp, unsigned long arg)
291{
292	struct route4_head *head = (struct route4_head *)tp->root;
293	struct route4_filter **fp, *f = (struct route4_filter *)arg;
294	unsigned int h = 0;
295	struct route4_bucket *b;
296	int i;
297
298	if (!head || !f)
299		return -EINVAL;
300
301	h = f->handle;
302	b = f->bkt;
303
304	for (fp = &b->ht[from_hash(h >> 16)]; *fp; fp = &(*fp)->next) {
305		if (*fp == f) {
306			tcf_tree_lock(tp);
307			*fp = f->next;
308			tcf_tree_unlock(tp);
309
310			route4_reset_fastmap(tp->q, head, f->id);
311			route4_delete_filter(tp, f);
312
313			/* Strip tree */
314
315			for (i = 0; i <= 32; i++)
316				if (b->ht[i])
317					return 0;
318
319			/* OK, session has no flows */
320			tcf_tree_lock(tp);
321			head->table[to_hash(h)] = NULL;
322			tcf_tree_unlock(tp);
323
324			kfree(b);
325			return 0;
326		}
327	}
328	return 0;
329}
330
331static const struct nla_policy route4_policy[TCA_ROUTE4_MAX + 1] = {
332	[TCA_ROUTE4_CLASSID]	= { .type = NLA_U32 },
333	[TCA_ROUTE4_TO]		= { .type = NLA_U32 },
334	[TCA_ROUTE4_FROM]	= { .type = NLA_U32 },
335	[TCA_ROUTE4_IIF]	= { .type = NLA_U32 },
336};
337
338static int route4_set_parms(struct tcf_proto *tp, unsigned long base,
339	struct route4_filter *f, u32 handle, struct route4_head *head,
340	struct nlattr **tb, struct nlattr *est, int new)
341{
342	int err;
343	u32 id = 0, to = 0, nhandle = 0x8000;
344	struct route4_filter *fp;
345	unsigned int h1;
346	struct route4_bucket *b;
347	struct tcf_exts e;
348
349	err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map);
350	if (err < 0)
351		return err;
352
353	err = -EINVAL;
354	if (tb[TCA_ROUTE4_TO]) {
355		if (new && handle & 0x8000)
356			goto errout;
357		to = nla_get_u32(tb[TCA_ROUTE4_TO]);
358		if (to > 0xFF)
359			goto errout;
360		nhandle = to;
361	}
362
363	if (tb[TCA_ROUTE4_FROM]) {
364		if (tb[TCA_ROUTE4_IIF])
365			goto errout;
366		id = nla_get_u32(tb[TCA_ROUTE4_FROM]);
367		if (id > 0xFF)
368			goto errout;
369		nhandle |= id << 16;
370	} else if (tb[TCA_ROUTE4_IIF]) {
371		id = nla_get_u32(tb[TCA_ROUTE4_IIF]);
372		if (id > 0x7FFF)
373			goto errout;
374		nhandle |= (id | 0x8000) << 16;
375	} else
376		nhandle |= 0xFFFF << 16;
377
378	if (handle && new) {
379		nhandle |= handle & 0x7F00;
380		if (nhandle != handle)
381			goto errout;
382	}
383
384	h1 = to_hash(nhandle);
385	b = head->table[h1];
386	if (!b) {
387		err = -ENOBUFS;
388		b = kzalloc(sizeof(struct route4_bucket), GFP_KERNEL);
389		if (b == NULL)
390			goto errout;
391
392		tcf_tree_lock(tp);
393		head->table[h1] = b;
394		tcf_tree_unlock(tp);
395	} else {
396		unsigned int h2 = from_hash(nhandle >> 16);
397
398		err = -EEXIST;
399		for (fp = b->ht[h2]; fp; fp = fp->next)
400			if (fp->handle == f->handle)
401				goto errout;
402	}
403
404	tcf_tree_lock(tp);
405	if (tb[TCA_ROUTE4_TO])
406		f->id = to;
407
408	if (tb[TCA_ROUTE4_FROM])
409		f->id = to | id<<16;
410	else if (tb[TCA_ROUTE4_IIF])
411		f->iif = id;
412
413	f->handle = nhandle;
414	f->bkt = b;
415	tcf_tree_unlock(tp);
416
417	if (tb[TCA_ROUTE4_CLASSID]) {
418		f->res.classid = nla_get_u32(tb[TCA_ROUTE4_CLASSID]);
419		tcf_bind_filter(tp, &f->res, base);
420	}
421
422	tcf_exts_change(tp, &f->exts, &e);
423
424	return 0;
425errout:
426	tcf_exts_destroy(tp, &e);
427	return err;
428}
429
430static int route4_change(struct tcf_proto *tp, unsigned long base,
431		       u32 handle,
432		       struct nlattr **tca,
433		       unsigned long *arg)
434{
435	struct route4_head *head = tp->root;
436	struct route4_filter *f, *f1, **fp;
437	struct route4_bucket *b;
438	struct nlattr *opt = tca[TCA_OPTIONS];
439	struct nlattr *tb[TCA_ROUTE4_MAX + 1];
440	unsigned int h, th;
441	u32 old_handle = 0;
442	int err;
443
444	if (opt == NULL)
445		return handle ? -EINVAL : 0;
446
447	err = nla_parse_nested(tb, TCA_ROUTE4_MAX, opt, route4_policy);
448	if (err < 0)
449		return err;
450
451	f = (struct route4_filter *)*arg;
452	if (f) {
453		if (f->handle != handle && handle)
454			return -EINVAL;
455
456		if (f->bkt)
457			old_handle = f->handle;
458
459		err = route4_set_parms(tp, base, f, handle, head, tb,
460			tca[TCA_RATE], 0);
461		if (err < 0)
462			return err;
463
464		goto reinsert;
465	}
466
467	err = -ENOBUFS;
468	if (head == NULL) {
469		head = kzalloc(sizeof(struct route4_head), GFP_KERNEL);
470		if (head == NULL)
471			goto errout;
472
473		tcf_tree_lock(tp);
474		tp->root = head;
475		tcf_tree_unlock(tp);
476	}
477
478	f = kzalloc(sizeof(struct route4_filter), GFP_KERNEL);
479	if (f == NULL)
480		goto errout;
481
482	err = route4_set_parms(tp, base, f, handle, head, tb,
483		tca[TCA_RATE], 1);
484	if (err < 0)
485		goto errout;
486
487reinsert:
488	h = from_hash(f->handle >> 16);
489	for (fp = &f->bkt->ht[h]; (f1 = *fp) != NULL; fp = &f1->next)
490		if (f->handle < f1->handle)
491			break;
492
493	f->next = f1;
494	tcf_tree_lock(tp);
495	*fp = f;
496
497	if (old_handle && f->handle != old_handle) {
498		th = to_hash(old_handle);
499		h = from_hash(old_handle >> 16);
500		b = head->table[th];
501		if (b) {
502			for (fp = &b->ht[h]; *fp; fp = &(*fp)->next) {
503				if (*fp == f) {
504					*fp = f->next;
505					break;
506				}
507			}
508		}
509	}
510	tcf_tree_unlock(tp);
511
512	route4_reset_fastmap(tp->q, head, f->id);
513	*arg = (unsigned long)f;
514	return 0;
515
516errout:
517	kfree(f);
518	return err;
519}
520
521static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
522{
523	struct route4_head *head = tp->root;
524	unsigned int h, h1;
525
526	if (head == NULL)
527		arg->stop = 1;
528
529	if (arg->stop)
530		return;
531
532	for (h = 0; h <= 256; h++) {
533		struct route4_bucket *b = head->table[h];
534
535		if (b) {
536			for (h1 = 0; h1 <= 32; h1++) {
537				struct route4_filter *f;
538
539				for (f = b->ht[h1]; f; f = f->next) {
540					if (arg->count < arg->skip) {
541						arg->count++;
542						continue;
543					}
544					if (arg->fn(tp, (unsigned long)f, arg) < 0) {
545						arg->stop = 1;
546						return;
547					}
548					arg->count++;
549				}
550			}
551		}
552	}
553}
554
555static int route4_dump(struct tcf_proto *tp, unsigned long fh,
556		       struct sk_buff *skb, struct tcmsg *t)
557{
558	struct route4_filter *f = (struct route4_filter *)fh;
559	unsigned char *b = skb_tail_pointer(skb);
560	struct nlattr *nest;
561	u32 id;
562
563	if (f == NULL)
564		return skb->len;
565
566	t->tcm_handle = f->handle;
567
568	nest = nla_nest_start(skb, TCA_OPTIONS);
569	if (nest == NULL)
570		goto nla_put_failure;
571
572	if (!(f->handle & 0x8000)) {
573		id = f->id & 0xFF;
574		if (nla_put_u32(skb, TCA_ROUTE4_TO, id))
575			goto nla_put_failure;
576	}
577	if (f->handle & 0x80000000) {
578		if ((f->handle >> 16) != 0xFFFF &&
579		    nla_put_u32(skb, TCA_ROUTE4_IIF, f->iif))
580			goto nla_put_failure;
581	} else {
582		id = f->id >> 16;
583		if (nla_put_u32(skb, TCA_ROUTE4_FROM, id))
584			goto nla_put_failure;
585	}
586	if (f->res.classid &&
587	    nla_put_u32(skb, TCA_ROUTE4_CLASSID, f->res.classid))
588		goto nla_put_failure;
589
590	if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
591		goto nla_put_failure;
592
593	nla_nest_end(skb, nest);
594
595	if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0)
596		goto nla_put_failure;
597
598	return skb->len;
599
600nla_put_failure:
601	nlmsg_trim(skb, b);
602	return -1;
603}
604
605static struct tcf_proto_ops cls_route4_ops __read_mostly = {
606	.kind		=	"route",
607	.classify	=	route4_classify,
608	.init		=	route4_init,
609	.destroy	=	route4_destroy,
610	.get		=	route4_get,
611	.put		=	route4_put,
612	.change		=	route4_change,
613	.delete		=	route4_delete,
614	.walk		=	route4_walk,
615	.dump		=	route4_dump,
616	.owner		=	THIS_MODULE,
617};
618
619static int __init init_route4(void)
620{
621	return register_tcf_proto_ops(&cls_route4_ops);
622}
623
624static void __exit exit_route4(void)
625{
626	unregister_tcf_proto_ops(&cls_route4_ops);
627}
628
629module_init(init_route4)
630module_exit(exit_route4)
631MODULE_LICENSE("GPL");
632