blob: 02996ac05c75d11b738649fd3069abeb17b82bdd [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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 if (f)
529 kfree(f);
530 return err;
531}
532
533static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
534{
535 struct route4_head *head = tp->root;
536 unsigned h, h1;
537
538 if (head == NULL)
539 arg->stop = 1;
540
541 if (arg->stop)
542 return;
543
544 for (h = 0; h <= 256; h++) {
545 struct route4_bucket *b = head->table[h];
546
547 if (b) {
548 for (h1 = 0; h1 <= 32; h1++) {
549 struct route4_filter *f;
550
551 for (f = b->ht[h1]; f; f = f->next) {
552 if (arg->count < arg->skip) {
553 arg->count++;
554 continue;
555 }
556 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
557 arg->stop = 1;
558 return;
559 }
560 arg->count++;
561 }
562 }
563 }
564 }
565}
566
567static int route4_dump(struct tcf_proto *tp, unsigned long fh,
568 struct sk_buff *skb, struct tcmsg *t)
569{
570 struct route4_filter *f = (struct route4_filter*)fh;
571 unsigned char *b = skb->tail;
572 struct rtattr *rta;
573 u32 id;
574
575 if (f == NULL)
576 return skb->len;
577
578 t->tcm_handle = f->handle;
579
580 rta = (struct rtattr*)b;
581 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
582
583 if (!(f->handle&0x8000)) {
584 id = f->id&0xFF;
585 RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);
586 }
587 if (f->handle&0x80000000) {
588 if ((f->handle>>16) != 0xFFFF)
589 RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
590 } else {
591 id = f->id>>16;
592 RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
593 }
594 if (f->res.classid)
595 RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);
596
597 if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
598 goto rtattr_failure;
599
600 rta->rta_len = skb->tail - b;
601
602 if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0)
603 goto rtattr_failure;
604
605 return skb->len;
606
607rtattr_failure:
608 skb_trim(skb, b - skb->data);
609 return -1;
610}
611
612static struct tcf_proto_ops cls_route4_ops = {
613 .next = NULL,
614 .kind = "route",
615 .classify = route4_classify,
616 .init = route4_init,
617 .destroy = route4_destroy,
618 .get = route4_get,
619 .put = route4_put,
620 .change = route4_change,
621 .delete = route4_delete,
622 .walk = route4_walk,
623 .dump = route4_dump,
624 .owner = THIS_MODULE,
625};
626
627static int __init init_route4(void)
628{
629 return register_tcf_proto_ops(&cls_route4_ops);
630}
631
632static void __exit exit_route4(void)
633{
634 unregister_tcf_proto_ops(&cls_route4_ops);
635}
636
637module_init(init_route4)
638module_exit(exit_route4)
639MODULE_LICENSE("GPL");