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 <asm/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/pkt_sched.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 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 #ifdef CONFIG_NET_CLS_POLICE
72 struct tcf_police *police;
73 #endif
74
75 u32 handle;
76 struct route4_bucket *bkt;
77 };
78
79 #define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
80
81 static __inline__ int route4_fastmap_hash(u32 id, int iif)
82 {
83 return id&0xF;
84 }
85
86 static void route4_reset_fastmap(struct net_device *dev, struct route4_head *head, u32 id)
87 {
88 spin_lock_bh(&dev->queue_lock);
89 memset(head->fastmap, 0, sizeof(head->fastmap));
90 spin_unlock_bh(&dev->queue_lock);
91 }
92
93 static void __inline__
94 route4_set_fastmap(struct route4_head *head, u32 id, int iif,
95 struct route4_filter *f)
96 {
97 int h = route4_fastmap_hash(id, iif);
98 head->fastmap[h].id = id;
99 head->fastmap[h].iif = iif;
100 head->fastmap[h].filter = f;
101 }
102
103 static __inline__ int route4_hash_to(u32 id)
104 {
105 return id&0xFF;
106 }
107
108 static __inline__ int route4_hash_from(u32 id)
109 {
110 return (id>>16)&0xF;
111 }
112
113 static __inline__ int route4_hash_iif(int iif)
114 {
115 return 16 + ((iif>>16)&0xF);
116 }
117
118 static __inline__ int route4_hash_wild(void)
119 {
120 return 32;
121 }
122
123 #ifdef CONFIG_NET_CLS_POLICE
124 #define IF_ROUTE_POLICE \
125 if (f->police) { \
126 int pol_res = tcf_police(skb, f->police); \
127 if (pol_res >= 0) return pol_res; \
128 dont_cache = 1; \
129 continue; \
130 } \
131 if (!dont_cache)
132 #else
133 #define IF_ROUTE_POLICE
134 #endif
135
136
137 static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp,
138 struct tcf_result *res)
139 {
140 struct route4_head *head = (struct route4_head*)tp->root;
141 struct dst_entry *dst;
142 struct route4_bucket *b;
143 struct route4_filter *f;
144 #ifdef CONFIG_NET_CLS_POLICE
145 int dont_cache = 0;
146 #endif
147 u32 id, h;
148 int iif;
149
150 if ((dst = skb->dst) == NULL)
151 goto failure;
152
153 id = dst->tclassid;
154 if (head == NULL)
155 goto old_method;
156
157 iif = ((struct rtable*)dst)->key.iif;
158
159 h = route4_fastmap_hash(id, iif);
160 if (id == head->fastmap[h].id &&
161 iif == head->fastmap[h].iif &&
162 (f = head->fastmap[h].filter) != NULL) {
163 if (f == ROUTE4_FAILURE)
164 goto failure;
165
166 *res = f->res;
167 return 0;
168 }
169
170 h = route4_hash_to(id);
171
172 restart:
173 if ((b = head->table[h]) != NULL) {
174 f = b->ht[route4_hash_from(id)];
175
176 for ( ; f; f = f->next) {
177 if (f->id == id) {
178 *res = f->res;
179 IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);
180 return 0;
181 }
182 }
183
184 for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next) {
185 if (f->iif == iif) {
186 *res = f->res;
187 IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);
188 return 0;
189 }
190 }
191
192 for (f = b->ht[route4_hash_wild()]; f; f = f->next) {
193 *res = f->res;
194 IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);
195 return 0;
196 }
197
198 }
199 if (h < 256) {
200 h = 256;
201 id &= ~0xFFFF;
202 goto restart;
203 }
204
205 #ifdef CONFIG_NET_CLS_POLICE
206 if (!dont_cache)
207 #endif
208 route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
209 failure:
210 return -1;
211
212 old_method:
213 if (id && (TC_H_MAJ(id) == 0 ||
214 !(TC_H_MAJ(id^tp->q->handle)))) {
215 res->classid = id;
216 res->class = 0;
217 return 0;
218 }
219 return -1;
220 }
221
222 static u32 to_hash(u32 id)
223 {
224 u32 h = id&0xFF;
225 if (id&0x8000)
226 h += 256;
227 return h;
228 }
229
230 static u32 from_hash(u32 id)
231 {
232 id &= 0xFFFF;
233 if (id == 0xFFFF)
234 return 32;
235 if (!(id & 0x8000)) {
236 if (id > 255)
237 return 256;
238 return id&0xF;
239 }
240 return 16 + (id&0xF);
241 }
242
243 static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
244 {
245 struct route4_head *head = (struct route4_head*)tp->root;
246 struct route4_bucket *b;
247 struct route4_filter *f;
248 unsigned h1, h2;
249
250 if (!head)
251 return 0;
252
253 h1 = to_hash(handle);
254 if (h1 > 256)
255 return 0;
256
257 h2 = from_hash(handle>>16);
258 if (h2 > 32)
259 return 0;
260
261 if ((b = head->table[h1]) != NULL) {
262 for (f = b->ht[h2]; f; f = f->next)
263 if (f->handle == handle)
264 return (unsigned long)f;
265 }
266 return 0;
267 }
268
269 static void route4_put(struct tcf_proto *tp, unsigned long f)
270 {
271 }
272
273 static int route4_init(struct tcf_proto *tp)
274 {
275 MOD_INC_USE_COUNT;
276 return 0;
277 }
278
279 static void route4_destroy(struct tcf_proto *tp)
280 {
281 struct route4_head *head = xchg(&tp->root, NULL);
282 int h1, h2;
283
284 if (head == NULL) {
285 MOD_DEC_USE_COUNT;
286 return;
287 }
288
289 for (h1=0; h1<=256; h1++) {
290 struct route4_bucket *b;
291
292 if ((b = head->table[h1]) != NULL) {
293 for (h2=0; h2<=32; h2++) {
294 struct route4_filter *f;
295
296 while ((f = b->ht[h2]) != NULL) {
297 unsigned long cl;
298
299 b->ht[h2] = f->next;
300 if ((cl = __cls_set_class(&f->res.class, 0)) != 0)
301 tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
302 #ifdef CONFIG_NET_CLS_POLICE
303 tcf_police_release(f->police);
304 #endif
305 kfree(f);
306 }
307 }
308 kfree(b);
309 }
310 }
311 kfree(head);
312 MOD_DEC_USE_COUNT;
313 }
314
315 static int route4_delete(struct tcf_proto *tp, unsigned long arg)
316 {
317 struct route4_head *head = (struct route4_head*)tp->root;
318 struct route4_filter **fp, *f = (struct route4_filter*)arg;
319 unsigned h = f->handle;
320 struct route4_bucket *b;
321 int i;
322
323 if (!head || !f)
324 return -EINVAL;
325
326 b = f->bkt;
327
328 for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {
329 if (*fp == f) {
330 unsigned long cl;
331
332 tcf_tree_lock(tp);
333 *fp = f->next;
334 tcf_tree_unlock(tp);
335
336 route4_reset_fastmap(tp->q->dev, head, f->id);
337
338 if ((cl = cls_set_class(tp, &f->res.class, 0)) != 0)
339 tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
340
341 #ifdef CONFIG_NET_CLS_POLICE
342 tcf_police_release(f->police);
343 #endif
344 kfree(f);
345
346 /* Strip tree */
347
348 for (i=0; i<=32; i++)
349 if (b->ht[i])
350 return 0;
351
352 /* OK, session has no flows */
353 tcf_tree_lock(tp);
354 head->table[to_hash(h)] = NULL;
355 tcf_tree_unlock(tp);
356
357 kfree(b);
358 return 0;
359 }
360 }
361 return 0;
362 }
363
364 static int route4_change(struct tcf_proto *tp, unsigned long base,
365 u32 handle,
366 struct rtattr **tca,
367 unsigned long *arg)
368 {
369 struct route4_head *head = tp->root;
370 struct route4_filter *f, *f1, **ins_f;
371 struct route4_bucket *b;
372 struct rtattr *opt = tca[TCA_OPTIONS-1];
373 struct rtattr *tb[TCA_ROUTE4_MAX];
374 unsigned h1, h2;
375 int err;
376
377 if (opt == NULL)
378 return handle ? -EINVAL : 0;
379
380 if (rtattr_parse(tb, TCA_ROUTE4_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)
381 return -EINVAL;
382
383 if ((f = (struct route4_filter*)*arg) != NULL) {
384 /* Node exists: adjust only classid */
385
386 if (f->handle != handle && handle)
387 return -EINVAL;
388 if (tb[TCA_ROUTE4_CLASSID-1]) {
389 unsigned long cl;
390
391 f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
392 cl = cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
393 if (cl)
394 tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
395 }
396 #ifdef CONFIG_NET_CLS_POLICE
397 if (tb[TCA_ROUTE4_POLICE-1]) {
398 struct tcf_police *police = tcf_police_locate(tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);
399
400 tcf_tree_lock(tp);
401 police = xchg(&f->police, police);
402 tcf_tree_unlock(tp);
403
404 tcf_police_release(police);
405 }
406 #endif
407 return 0;
408 }
409
410 /* Now more serious part... */
411
412 if (head == NULL) {
413 head = kmalloc(sizeof(struct route4_head), GFP_KERNEL);
414 if (head == NULL)
415 return -ENOBUFS;
416 memset(head, 0, sizeof(struct route4_head));
417
418 tcf_tree_lock(tp);
419 tp->root = head;
420 tcf_tree_unlock(tp);
421 }
422
423 f = kmalloc(sizeof(struct route4_filter), GFP_KERNEL);
424 if (f == NULL)
425 return -ENOBUFS;
426
427 memset(f, 0, sizeof(*f));
428
429 err = -EINVAL;
430 f->handle = 0x8000;
431 if (tb[TCA_ROUTE4_TO-1]) {
432 if (handle&0x8000)
433 goto errout;
434 if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < 4)
435 goto errout;
436 f->id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_TO-1]);
437 if (f->id > 0xFF)
438 goto errout;
439 f->handle = f->id;
440 }
441 if (tb[TCA_ROUTE4_FROM-1]) {
442 u32 sid;
443 if (tb[TCA_ROUTE4_IIF-1])
444 goto errout;
445 if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < 4)
446 goto errout;
447 sid = (*(u32*)RTA_DATA(tb[TCA_ROUTE4_FROM-1]));
448 if (sid > 0xFF)
449 goto errout;
450 f->handle |= sid<<16;
451 f->id |= sid<<16;
452 } else if (tb[TCA_ROUTE4_IIF-1]) {
453 if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < 4)
454 goto errout;
455 f->iif = *(u32*)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);
456 if (f->iif > 0x7FFF)
457 goto errout;
458 f->handle |= (f->iif|0x8000)<<16;
459 } else
460 f->handle |= 0xFFFF<<16;
461
462 if (handle) {
463 f->handle |= handle&0x7F00;
464 if (f->handle != handle)
465 goto errout;
466 }
467
468 if (tb[TCA_ROUTE4_CLASSID-1]) {
469 if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < 4)
470 goto errout;
471 f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
472 }
473
474 h1 = to_hash(f->handle);
475 if ((b = head->table[h1]) == NULL) {
476 err = -ENOBUFS;
477 b = kmalloc(sizeof(struct route4_bucket), GFP_KERNEL);
478 if (b == NULL)
479 goto errout;
480 memset(b, 0, sizeof(*b));
481
482 tcf_tree_lock(tp);
483 head->table[h1] = b;
484 tcf_tree_unlock(tp);
485 }
486 f->bkt = b;
487
488 err = -EEXIST;
489 h2 = from_hash(f->handle>>16);
490 for (ins_f = &b->ht[h2]; (f1=*ins_f) != NULL; ins_f = &f1->next) {
491 if (f->handle < f1->handle)
492 break;
493 if (f1->handle == f->handle)
494 goto errout;
495 }
496
497 cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
498 #ifdef CONFIG_NET_CLS_POLICE
499 if (tb[TCA_ROUTE4_POLICE-1])
500 f->police = tcf_police_locate(tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);
501 #endif
502
503 f->next = f1;
504 tcf_tree_lock(tp);
505 *ins_f = f;
506 tcf_tree_unlock(tp);
507
508 route4_reset_fastmap(tp->q->dev, head, f->id);
509 *arg = (unsigned long)f;
510 return 0;
511
512 errout:
513 if (f)
514 kfree(f);
515 return err;
516 }
517
518 static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
519 {
520 struct route4_head *head = tp->root;
521 unsigned h, h1;
522
523 if (head == NULL)
524 arg->stop = 1;
525
526 if (arg->stop)
527 return;
528
529 for (h = 0; h <= 256; h++) {
530 struct route4_bucket *b = head->table[h];
531
532 if (b) {
533 for (h1 = 0; h1 <= 32; h1++) {
534 struct route4_filter *f;
535
536 for (f = b->ht[h1]; f; f = f->next) {
537 if (arg->count < arg->skip) {
538 arg->count++;
539 continue;
540 }
541 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
542 arg->stop = 1;
543 break;
544 }
545 arg->count++;
546 }
547 }
548 }
549 }
550 }
551
552 #ifdef CONFIG_RTNETLINK
553 static int route4_dump(struct tcf_proto *tp, unsigned long fh,
554 struct sk_buff *skb, struct tcmsg *t)
555 {
556 struct route4_filter *f = (struct route4_filter*)fh;
557 unsigned char *b = skb->tail;
558 struct rtattr *rta;
559 u32 id;
560
561 if (f == NULL)
562 return skb->len;
563
564 t->tcm_handle = f->handle;
565
566 rta = (struct rtattr*)b;
567 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
568
569 if (!(f->handle&0x8000)) {
570 id = f->id&0xFF;
571 RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);
572 }
573 if (f->handle&0x80000000) {
574 if ((f->handle>>16) != 0xFFFF)
575 RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
576 } else {
577 id = f->id>>16;
578 RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
579 }
580 if (f->res.classid)
581 RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);
582 #ifdef CONFIG_NET_CLS_POLICE
583 if (f->police) {
584 struct rtattr * p_rta = (struct rtattr*)skb->tail;
585
586 RTA_PUT(skb, TCA_ROUTE4_POLICE, 0, NULL);
587
588 if (tcf_police_dump(skb, f->police) < 0)
589 goto rtattr_failure;
590
591 p_rta->rta_len = skb->tail - (u8*)p_rta;
592 }
593 #endif
594
595 rta->rta_len = skb->tail - b;
596 #ifdef CONFIG_NET_CLS_POLICE
597 if (f->police) {
598 if (qdisc_copy_stats(skb, &f->police->stats))
599 goto rtattr_failure;
600 }
601 #endif
602 return skb->len;
603
604 rtattr_failure:
605 skb_trim(skb, b - skb->data);
606 return -1;
607 }
608 #endif
609
610 struct tcf_proto_ops cls_route4_ops = {
611 NULL,
612 "route",
613 route4_classify,
614 route4_init,
615 route4_destroy,
616
617 route4_get,
618 route4_put,
619 route4_change,
620 route4_delete,
621 route4_walk,
622 #ifdef CONFIG_RTNETLINK
623 route4_dump
624 #else
625 NULL
626 #endif
627 };
628
629 #ifdef MODULE
630 int init_module(void)
631 {
632 return register_tcf_proto_ops(&cls_route4_ops);
633 }
634
635 void cleanup_module(void)
636 {
637 unregister_tcf_proto_ops(&cls_route4_ops);
638 }
639 #endif
640
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.