2 * net/sched/cls_route.c ROUTE4 classifier.
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.
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
12 #include <linux/module.h>
13 #include <linux/types.h>
14 #include <linux/kernel.h>
15 #include <linux/string.h>
16 #include <linux/errno.h>
17 #include <linux/skbuff.h>
19 #include <net/route.h>
20 #include <net/netlink.h>
21 #include <net/act_api.h>
22 #include <net/pkt_cls.h>
25 1. For now we assume that route tags < 256.
26 It allows to use direct table lookups, instead of hash tables.
27 2. For now we assume that "from TAG" and "fromdev DEV" statements
28 are mutually exclusive.
29 3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
34 struct route4_filter
*filter
;
41 struct route4_fastmap fastmap
[16];
42 struct route4_bucket
*table
[256+1];
47 /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
48 struct route4_filter
*ht
[16+16+1];
53 struct route4_filter
*next
;
57 struct tcf_result res
;
60 struct route4_bucket
*bkt
;
63 #define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
65 static const struct tcf_ext_map route_ext_map
= {
66 .police
= TCA_ROUTE4_POLICE
,
67 .action
= TCA_ROUTE4_ACT
70 static __inline__
int route4_fastmap_hash(u32 id
, int iif
)
76 void route4_reset_fastmap(struct Qdisc
*q
, struct route4_head
*head
, u32 id
)
78 spinlock_t
*root_lock
= qdisc_root_lock(q
);
80 spin_lock_bh(root_lock
);
81 memset(head
->fastmap
, 0, sizeof(head
->fastmap
));
82 spin_unlock_bh(root_lock
);
86 route4_set_fastmap(struct route4_head
*head
, u32 id
, int iif
,
87 struct route4_filter
*f
)
89 int h
= route4_fastmap_hash(id
, iif
);
90 head
->fastmap
[h
].id
= id
;
91 head
->fastmap
[h
].iif
= iif
;
92 head
->fastmap
[h
].filter
= f
;
95 static __inline__
int route4_hash_to(u32 id
)
100 static __inline__
int route4_hash_from(u32 id
)
105 static __inline__
int route4_hash_iif(int iif
)
107 return 16 + ((iif
>>16)&0xF);
110 static __inline__
int route4_hash_wild(void)
115 #define ROUTE4_APPLY_RESULT() \
118 if (tcf_exts_is_available(&f->exts)) { \
119 int r = tcf_exts_exec(skb, &f->exts, res); \
125 } else if (!dont_cache) \
126 route4_set_fastmap(head, id, iif, f); \
130 static int route4_classify(struct sk_buff
*skb
, struct tcf_proto
*tp
,
131 struct tcf_result
*res
)
133 struct route4_head
*head
= (struct route4_head
*)tp
->root
;
134 struct dst_entry
*dst
;
135 struct route4_bucket
*b
;
136 struct route4_filter
*f
;
138 int iif
, dont_cache
= 0;
140 if ((dst
= skb
->dst
) == NULL
)
147 iif
= ((struct rtable
*)dst
)->fl
.iif
;
149 h
= route4_fastmap_hash(id
, iif
);
150 if (id
== head
->fastmap
[h
].id
&&
151 iif
== head
->fastmap
[h
].iif
&&
152 (f
= head
->fastmap
[h
].filter
) != NULL
) {
153 if (f
== ROUTE4_FAILURE
)
160 h
= route4_hash_to(id
);
163 if ((b
= head
->table
[h
]) != NULL
) {
164 for (f
= b
->ht
[route4_hash_from(id
)]; f
; f
= f
->next
)
166 ROUTE4_APPLY_RESULT();
168 for (f
= b
->ht
[route4_hash_iif(iif
)]; f
; f
= f
->next
)
170 ROUTE4_APPLY_RESULT();
172 for (f
= b
->ht
[route4_hash_wild()]; f
; f
= f
->next
)
173 ROUTE4_APPLY_RESULT();
183 route4_set_fastmap(head
, id
, iif
, ROUTE4_FAILURE
);
188 if (id
&& (TC_H_MAJ(id
) == 0 ||
189 !(TC_H_MAJ(id
^tp
->q
->handle
)))) {
197 static inline u32
to_hash(u32 id
)
205 static inline u32
from_hash(u32 id
)
210 if (!(id
& 0x8000)) {
215 return 16 + (id
&0xF);
218 static unsigned long route4_get(struct tcf_proto
*tp
, u32 handle
)
220 struct route4_head
*head
= (struct route4_head
*)tp
->root
;
221 struct route4_bucket
*b
;
222 struct route4_filter
*f
;
228 h1
= to_hash(handle
);
232 h2
= from_hash(handle
>>16);
236 if ((b
= head
->table
[h1
]) != NULL
) {
237 for (f
= b
->ht
[h2
]; f
; f
= f
->next
)
238 if (f
->handle
== handle
)
239 return (unsigned long)f
;
244 static void route4_put(struct tcf_proto
*tp
, unsigned long f
)
248 static int route4_init(struct tcf_proto
*tp
)
254 route4_delete_filter(struct tcf_proto
*tp
, struct route4_filter
*f
)
256 tcf_unbind_filter(tp
, &f
->res
);
257 tcf_exts_destroy(tp
, &f
->exts
);
261 static void route4_destroy(struct tcf_proto
*tp
)
263 struct route4_head
*head
= xchg(&tp
->root
, NULL
);
269 for (h1
=0; h1
<=256; h1
++) {
270 struct route4_bucket
*b
;
272 if ((b
= head
->table
[h1
]) != NULL
) {
273 for (h2
=0; h2
<=32; h2
++) {
274 struct route4_filter
*f
;
276 while ((f
= b
->ht
[h2
]) != NULL
) {
278 route4_delete_filter(tp
, f
);
287 static int route4_delete(struct tcf_proto
*tp
, unsigned long arg
)
289 struct route4_head
*head
= (struct route4_head
*)tp
->root
;
290 struct route4_filter
**fp
, *f
= (struct route4_filter
*)arg
;
292 struct route4_bucket
*b
;
301 for (fp
= &b
->ht
[from_hash(h
>>16)]; *fp
; fp
= &(*fp
)->next
) {
307 route4_reset_fastmap(tp
->q
, head
, f
->id
);
308 route4_delete_filter(tp
, f
);
312 for (i
=0; i
<=32; i
++)
316 /* OK, session has no flows */
318 head
->table
[to_hash(h
)] = NULL
;
328 static const struct nla_policy route4_policy
[TCA_ROUTE4_MAX
+ 1] = {
329 [TCA_ROUTE4_CLASSID
] = { .type
= NLA_U32
},
330 [TCA_ROUTE4_TO
] = { .type
= NLA_U32
},
331 [TCA_ROUTE4_FROM
] = { .type
= NLA_U32
},
332 [TCA_ROUTE4_IIF
] = { .type
= NLA_U32
},
335 static int route4_set_parms(struct tcf_proto
*tp
, unsigned long base
,
336 struct route4_filter
*f
, u32 handle
, struct route4_head
*head
,
337 struct nlattr
**tb
, struct nlattr
*est
, int new)
340 u32 id
= 0, to
= 0, nhandle
= 0x8000;
341 struct route4_filter
*fp
;
343 struct route4_bucket
*b
;
346 err
= tcf_exts_validate(tp
, tb
, est
, &e
, &route_ext_map
);
351 if (tb
[TCA_ROUTE4_TO
]) {
352 if (new && handle
& 0x8000)
354 to
= nla_get_u32(tb
[TCA_ROUTE4_TO
]);
360 if (tb
[TCA_ROUTE4_FROM
]) {
361 if (tb
[TCA_ROUTE4_IIF
])
363 id
= nla_get_u32(tb
[TCA_ROUTE4_FROM
]);
367 } else if (tb
[TCA_ROUTE4_IIF
]) {
368 id
= nla_get_u32(tb
[TCA_ROUTE4_IIF
]);
371 nhandle
|= (id
| 0x8000) << 16;
373 nhandle
|= 0xFFFF << 16;
376 nhandle
|= handle
& 0x7F00;
377 if (nhandle
!= handle
)
381 h1
= to_hash(nhandle
);
382 if ((b
= head
->table
[h1
]) == NULL
) {
384 b
= kzalloc(sizeof(struct route4_bucket
), GFP_KERNEL
);
392 unsigned int h2
= from_hash(nhandle
>> 16);
394 for (fp
= b
->ht
[h2
]; fp
; fp
= fp
->next
)
395 if (fp
->handle
== f
->handle
)
400 if (tb
[TCA_ROUTE4_TO
])
403 if (tb
[TCA_ROUTE4_FROM
])
405 else if (tb
[TCA_ROUTE4_IIF
])
412 if (tb
[TCA_ROUTE4_CLASSID
]) {
413 f
->res
.classid
= nla_get_u32(tb
[TCA_ROUTE4_CLASSID
]);
414 tcf_bind_filter(tp
, &f
->res
, base
);
417 tcf_exts_change(tp
, &f
->exts
, &e
);
421 tcf_exts_destroy(tp
, &e
);
425 static int route4_change(struct tcf_proto
*tp
, unsigned long base
,
430 struct route4_head
*head
= tp
->root
;
431 struct route4_filter
*f
, *f1
, **fp
;
432 struct route4_bucket
*b
;
433 struct nlattr
*opt
= tca
[TCA_OPTIONS
];
434 struct nlattr
*tb
[TCA_ROUTE4_MAX
+ 1];
440 return handle
? -EINVAL
: 0;
442 err
= nla_parse_nested(tb
, TCA_ROUTE4_MAX
, opt
, route4_policy
);
446 if ((f
= (struct route4_filter
*)*arg
) != NULL
) {
447 if (f
->handle
!= handle
&& handle
)
451 old_handle
= f
->handle
;
453 err
= route4_set_parms(tp
, base
, f
, handle
, head
, tb
,
463 head
= kzalloc(sizeof(struct route4_head
), GFP_KERNEL
);
472 f
= kzalloc(sizeof(struct route4_filter
), GFP_KERNEL
);
476 err
= route4_set_parms(tp
, base
, f
, handle
, head
, tb
,
482 h
= from_hash(f
->handle
>> 16);
483 for (fp
= &f
->bkt
->ht
[h
]; (f1
=*fp
) != NULL
; fp
= &f1
->next
)
484 if (f
->handle
< f1
->handle
)
491 if (old_handle
&& f
->handle
!= old_handle
) {
492 th
= to_hash(old_handle
);
493 h
= from_hash(old_handle
>> 16);
494 if ((b
= head
->table
[th
]) != NULL
) {
495 for (fp
= &b
->ht
[h
]; *fp
; fp
= &(*fp
)->next
) {
505 route4_reset_fastmap(tp
->q
, head
, f
->id
);
506 *arg
= (unsigned long)f
;
514 static void route4_walk(struct tcf_proto
*tp
, struct tcf_walker
*arg
)
516 struct route4_head
*head
= tp
->root
;
525 for (h
= 0; h
<= 256; h
++) {
526 struct route4_bucket
*b
= head
->table
[h
];
529 for (h1
= 0; h1
<= 32; h1
++) {
530 struct route4_filter
*f
;
532 for (f
= b
->ht
[h1
]; f
; f
= f
->next
) {
533 if (arg
->count
< arg
->skip
) {
537 if (arg
->fn(tp
, (unsigned long)f
, arg
) < 0) {
548 static int route4_dump(struct tcf_proto
*tp
, unsigned long fh
,
549 struct sk_buff
*skb
, struct tcmsg
*t
)
551 struct route4_filter
*f
= (struct route4_filter
*)fh
;
552 unsigned char *b
= skb_tail_pointer(skb
);
559 t
->tcm_handle
= f
->handle
;
561 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
563 goto nla_put_failure
;
565 if (!(f
->handle
&0x8000)) {
567 NLA_PUT_U32(skb
, TCA_ROUTE4_TO
, id
);
569 if (f
->handle
&0x80000000) {
570 if ((f
->handle
>>16) != 0xFFFF)
571 NLA_PUT_U32(skb
, TCA_ROUTE4_IIF
, f
->iif
);
574 NLA_PUT_U32(skb
, TCA_ROUTE4_FROM
, id
);
577 NLA_PUT_U32(skb
, TCA_ROUTE4_CLASSID
, f
->res
.classid
);
579 if (tcf_exts_dump(skb
, &f
->exts
, &route_ext_map
) < 0)
580 goto nla_put_failure
;
582 nla_nest_end(skb
, nest
);
584 if (tcf_exts_dump_stats(skb
, &f
->exts
, &route_ext_map
) < 0)
585 goto nla_put_failure
;
594 static struct tcf_proto_ops cls_route4_ops __read_mostly
= {
596 .classify
= route4_classify
,
598 .destroy
= route4_destroy
,
601 .change
= route4_change
,
602 .delete = route4_delete
,
605 .owner
= THIS_MODULE
,
608 static int __init
init_route4(void)
610 return register_tcf_proto_ops(&cls_route4_ops
);
613 static void __exit
exit_route4(void)
615 unregister_tcf_proto_ops(&cls_route4_ops
);
618 module_init(init_route4
)
619 module_exit(exit_route4
)
620 MODULE_LICENSE("GPL");