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