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