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