2 * net/sched/cls_rsvp.h Template file for RSVPv[46] classifiers.
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>
13 Comparing to general packet classification problem,
14 RSVP needs only sevaral relatively simple rules:
16 * (dst, protocol) are always specified,
17 so that we are able to hash them.
18 * src may be exact, or may be wildcard, so that
19 we can keep a hash table plus one wildcard entry.
20 * source port (or flow label) is important only if src is given.
24 We use a two level hash table: The top level is keyed by
25 destination address and protocol ID, every bucket contains a list
26 of "rsvp sessions", identified by destination address, protocol and
27 DPI(="Destination Port ID"): triple (key, mask, offset).
29 Every bucket has a smaller hash table keyed by source address
30 (cf. RSVP flowspec) and one wildcard entry for wildcard reservations.
31 Every bucket is again a list of "RSVP flows", selected by
32 source address and SPI(="Source Port ID" here rather than
33 "security parameter index"): triple (key, mask, offset).
36 NOTE 1. All the packets with IPv6 extension headers (but AH and ESP)
37 and all fragmented packets go to the best-effort traffic class.
40 NOTE 2. Two "port id"'s seems to be redundant, rfc2207 requires
41 only one "Generalized Port Identifier". So that for classic
42 ah, esp (and udp,tcp) both *pi should coincide or one of them
45 At first sight, this redundancy is just a waste of CPU
46 resources. But DPI and SPI add the possibility to assign different
47 priorities to GPIs. Look also at note 4 about tunnels below.
50 NOTE 3. One complication is the case of tunneled packets.
51 We implement it as following: if the first lookup
52 matches a special session with "tunnelhdr" value not zero,
53 flowid doesn't contain the true flow ID, but the tunnel ID (1...255).
54 In this case, we pull tunnelhdr bytes and restart lookup
55 with tunnel ID added to the list of keys. Simple and stupid 8)8)
56 It's enough for PIMREG and IPIP.
59 NOTE 4. Two GPIs make it possible to parse even GRE packets.
60 F.e. DPI can select ETH_P_IP (and necessary flags to make
61 tunnelhdr correct) in GRE protocol field and SPI matches
62 GRE key. Is it not nice? 8)8)
65 Well, as result, despite its simplicity, we get a pretty
66 powerful classification engine. */
74 struct rsvp_session
*ht
[256];
79 struct rsvp_session
*next
;
80 __be32 dst
[RSVP_DST_LEN
];
81 struct tc_rsvp_gpi dpi
;
84 /* 16 (src,sport) hash slots, and one wildcard source slot */
85 struct rsvp_filter
*ht
[16+1];
91 struct rsvp_filter
*next
;
92 __be32 src
[RSVP_DST_LEN
];
93 struct tc_rsvp_gpi spi
;
96 struct tcf_result res
;
100 struct rsvp_session
*sess
;
103 static __inline__
unsigned hash_dst(__be32
*dst
, u8 protocol
, u8 tunnelid
)
105 unsigned h
= (__force __u32
)dst
[RSVP_DST_LEN
-1];
108 return (h
^ protocol
^ tunnelid
) & 0xFF;
111 static __inline__
unsigned hash_src(__be32
*src
)
113 unsigned h
= (__force __u32
)src
[RSVP_DST_LEN
-1];
120 static struct tcf_ext_map rsvp_ext_map
= {
121 .police
= TCA_RSVP_POLICE
,
122 .action
= TCA_RSVP_ACT
125 #define RSVP_APPLY_RESULT() \
127 int r = tcf_exts_exec(skb, &f->exts, res); \
134 static int rsvp_classify(struct sk_buff
*skb
, struct tcf_proto
*tp
,
135 struct tcf_result
*res
)
137 struct rsvp_session
**sht
= ((struct rsvp_head
*)tp
->root
)->ht
;
138 struct rsvp_session
*s
;
139 struct rsvp_filter
*f
;
145 #if RSVP_DST_LEN == 4
146 struct ipv6hdr
*nhptr
;
148 if (!pskb_network_may_pull(skb
, sizeof(*nhptr
)))
150 nhptr
= ipv6_hdr(skb
);
154 if (!pskb_network_may_pull(skb
, sizeof(*nhptr
)))
161 #if RSVP_DST_LEN == 4
162 src
= &nhptr
->saddr
.s6_addr32
[0];
163 dst
= &nhptr
->daddr
.s6_addr32
[0];
164 protocol
= nhptr
->nexthdr
;
165 xprt
= ((u8
*)nhptr
) + sizeof(struct ipv6hdr
);
169 protocol
= nhptr
->protocol
;
170 xprt
= ((u8
*)nhptr
) + (nhptr
->ihl
<<2);
171 if (nhptr
->frag_off
& htons(IP_MF
|IP_OFFSET
))
175 h1
= hash_dst(dst
, protocol
, tunnelid
);
178 for (s
= sht
[h1
]; s
; s
= s
->next
) {
179 if (dst
[RSVP_DST_LEN
-1] == s
->dst
[RSVP_DST_LEN
-1] &&
180 protocol
== s
->protocol
&&
182 (*(u32
*)(xprt
+s
->dpi
.offset
)^s
->dpi
.key
)) &&
183 #if RSVP_DST_LEN == 4
184 dst
[0] == s
->dst
[0] &&
185 dst
[1] == s
->dst
[1] &&
186 dst
[2] == s
->dst
[2] &&
188 tunnelid
== s
->tunnelid
) {
190 for (f
= s
->ht
[h2
]; f
; f
= f
->next
) {
191 if (src
[RSVP_DST_LEN
-1] == f
->src
[RSVP_DST_LEN
-1] &&
192 !(f
->spi
.mask
& (*(u32
*)(xprt
+f
->spi
.offset
)^f
->spi
.key
))
193 #if RSVP_DST_LEN == 4
195 src
[0] == f
->src
[0] &&
196 src
[1] == f
->src
[1] &&
204 if (f
->tunnelhdr
== 0)
207 tunnelid
= f
->res
.classid
;
208 nhptr
= (void*)(xprt
+ f
->tunnelhdr
- sizeof(*nhptr
));
213 /* And wildcard bucket... */
214 for (f
= s
->ht
[16]; f
; f
= f
->next
) {
225 static unsigned long rsvp_get(struct tcf_proto
*tp
, u32 handle
)
227 struct rsvp_session
**sht
= ((struct rsvp_head
*)tp
->root
)->ht
;
228 struct rsvp_session
*s
;
229 struct rsvp_filter
*f
;
230 unsigned h1
= handle
&0xFF;
231 unsigned h2
= (handle
>>8)&0xFF;
236 for (s
= sht
[h1
]; s
; s
= s
->next
) {
237 for (f
= s
->ht
[h2
]; f
; f
= f
->next
) {
238 if (f
->handle
== handle
)
239 return (unsigned long)f
;
245 static void rsvp_put(struct tcf_proto
*tp
, unsigned long f
)
249 static int rsvp_init(struct tcf_proto
*tp
)
251 struct rsvp_head
*data
;
253 data
= kzalloc(sizeof(struct rsvp_head
), GFP_KERNEL
);
262 rsvp_delete_filter(struct tcf_proto
*tp
, struct rsvp_filter
*f
)
264 tcf_unbind_filter(tp
, &f
->res
);
265 tcf_exts_destroy(tp
, &f
->exts
);
269 static void rsvp_destroy(struct tcf_proto
*tp
)
271 struct rsvp_head
*data
= xchg(&tp
->root
, NULL
);
272 struct rsvp_session
**sht
;
280 for (h1
=0; h1
<256; h1
++) {
281 struct rsvp_session
*s
;
283 while ((s
= sht
[h1
]) != NULL
) {
286 for (h2
=0; h2
<=16; h2
++) {
287 struct rsvp_filter
*f
;
289 while ((f
= s
->ht
[h2
]) != NULL
) {
291 rsvp_delete_filter(tp
, f
);
300 static int rsvp_delete(struct tcf_proto
*tp
, unsigned long arg
)
302 struct rsvp_filter
**fp
, *f
= (struct rsvp_filter
*)arg
;
303 unsigned h
= f
->handle
;
304 struct rsvp_session
**sp
;
305 struct rsvp_session
*s
= f
->sess
;
308 for (fp
= &s
->ht
[(h
>>8)&0xFF]; *fp
; fp
= &(*fp
)->next
) {
313 rsvp_delete_filter(tp
, f
);
317 for (i
=0; i
<=16; i
++)
321 /* OK, session has no flows */
322 for (sp
= &((struct rsvp_head
*)tp
->root
)->ht
[h
&0xFF];
323 *sp
; sp
= &(*sp
)->next
) {
340 static unsigned gen_handle(struct tcf_proto
*tp
, unsigned salt
)
342 struct rsvp_head
*data
= tp
->root
;
347 if ((data
->hgenerator
+= 0x10000) == 0)
348 data
->hgenerator
= 0x10000;
349 h
= data
->hgenerator
|salt
;
350 if (rsvp_get(tp
, h
) == 0)
356 static int tunnel_bts(struct rsvp_head
*data
)
358 int n
= data
->tgenerator
>>5;
359 u32 b
= 1<<(data
->tgenerator
&0x1F);
367 static void tunnel_recycle(struct rsvp_head
*data
)
369 struct rsvp_session
**sht
= data
->ht
;
373 memset(tmap
, 0, sizeof(tmap
));
375 for (h1
=0; h1
<256; h1
++) {
376 struct rsvp_session
*s
;
377 for (s
= sht
[h1
]; s
; s
= s
->next
) {
378 for (h2
=0; h2
<=16; h2
++) {
379 struct rsvp_filter
*f
;
381 for (f
= s
->ht
[h2
]; f
; f
= f
->next
) {
382 if (f
->tunnelhdr
== 0)
384 data
->tgenerator
= f
->res
.classid
;
391 memcpy(data
->tmap
, tmap
, sizeof(tmap
));
394 static u32
gen_tunnel(struct rsvp_head
*data
)
398 for (k
=0; k
<2; k
++) {
399 for (i
=255; i
>0; i
--) {
400 if (++data
->tgenerator
== 0)
401 data
->tgenerator
= 1;
402 if (tunnel_bts(data
))
403 return data
->tgenerator
;
405 tunnel_recycle(data
);
410 static const struct nla_policy rsvp_policy
[TCA_RSVP_MAX
+ 1] = {
411 [TCA_RSVP_CLASSID
] = { .type
= NLA_U32
},
412 [TCA_RSVP_DST
] = { .type
= NLA_BINARY
,
413 .len
= RSVP_DST_LEN
* sizeof(u32
) },
414 [TCA_RSVP_SRC
] = { .type
= NLA_BINARY
,
415 .len
= RSVP_DST_LEN
* sizeof(u32
) },
416 [TCA_RSVP_PINFO
] = { .len
= sizeof(struct tc_rsvp_pinfo
) },
419 static int rsvp_change(struct tcf_proto
*tp
, unsigned long base
,
424 struct rsvp_head
*data
= tp
->root
;
425 struct rsvp_filter
*f
, **fp
;
426 struct rsvp_session
*s
, **sp
;
427 struct tc_rsvp_pinfo
*pinfo
= NULL
;
428 struct nlattr
*opt
= tca
[TCA_OPTIONS
-1];
429 struct nlattr
*tb
[TCA_RSVP_MAX
+ 1];
436 return handle
? -EINVAL
: 0;
438 err
= nla_parse_nested(tb
, TCA_RSVP_MAX
, opt
, rsvp_policy
);
442 err
= tcf_exts_validate(tp
, tb
, tca
[TCA_RATE
-1], &e
, &rsvp_ext_map
);
446 if ((f
= (struct rsvp_filter
*)*arg
) != NULL
) {
447 /* Node exists: adjust only classid */
449 if (f
->handle
!= handle
&& handle
)
451 if (tb
[TCA_RSVP_CLASSID
-1]) {
452 f
->res
.classid
= nla_get_u32(tb
[TCA_RSVP_CLASSID
-1]);
453 tcf_bind_filter(tp
, &f
->res
, base
);
456 tcf_exts_change(tp
, &f
->exts
, &e
);
460 /* Now more serious part... */
464 if (tb
[TCA_RSVP_DST
-1] == NULL
)
468 f
= kzalloc(sizeof(struct rsvp_filter
), GFP_KERNEL
);
473 if (tb
[TCA_RSVP_SRC
-1]) {
474 memcpy(f
->src
, nla_data(tb
[TCA_RSVP_SRC
-1]), sizeof(f
->src
));
475 h2
= hash_src(f
->src
);
477 if (tb
[TCA_RSVP_PINFO
-1]) {
478 pinfo
= nla_data(tb
[TCA_RSVP_PINFO
-1]);
480 f
->tunnelhdr
= pinfo
->tunnelhdr
;
482 if (tb
[TCA_RSVP_CLASSID
-1])
483 f
->res
.classid
= nla_get_u32(tb
[TCA_RSVP_CLASSID
-1]);
485 dst
= nla_data(tb
[TCA_RSVP_DST
-1]);
486 h1
= hash_dst(dst
, pinfo
? pinfo
->protocol
: 0, pinfo
? pinfo
->tunnelid
: 0);
489 if ((f
->handle
= gen_handle(tp
, h1
| (h2
<<8))) == 0)
494 if (f
->res
.classid
> 255)
498 if (f
->res
.classid
== 0 &&
499 (f
->res
.classid
= gen_tunnel(data
)) == 0)
503 for (sp
= &data
->ht
[h1
]; (s
=*sp
) != NULL
; sp
= &s
->next
) {
504 if (dst
[RSVP_DST_LEN
-1] == s
->dst
[RSVP_DST_LEN
-1] &&
505 pinfo
&& pinfo
->protocol
== s
->protocol
&&
506 memcmp(&pinfo
->dpi
, &s
->dpi
, sizeof(s
->dpi
)) == 0 &&
507 #if RSVP_DST_LEN == 4
508 dst
[0] == s
->dst
[0] &&
509 dst
[1] == s
->dst
[1] &&
510 dst
[2] == s
->dst
[2] &&
512 pinfo
->tunnelid
== s
->tunnelid
) {
515 /* OK, we found appropriate session */
520 if (f
->tunnelhdr
== 0)
521 tcf_bind_filter(tp
, &f
->res
, base
);
523 tcf_exts_change(tp
, &f
->exts
, &e
);
525 for (fp
= &s
->ht
[h2
]; *fp
; fp
= &(*fp
)->next
)
526 if (((*fp
)->spi
.mask
&f
->spi
.mask
) != f
->spi
.mask
)
532 *arg
= (unsigned long)f
;
537 /* No session found. Create new one. */
540 s
= kzalloc(sizeof(struct rsvp_session
), GFP_KERNEL
);
543 memcpy(s
->dst
, dst
, sizeof(s
->dst
));
547 s
->protocol
= pinfo
->protocol
;
548 s
->tunnelid
= pinfo
->tunnelid
;
550 for (sp
= &data
->ht
[h1
]; *sp
; sp
= &(*sp
)->next
) {
551 if (((*sp
)->dpi
.mask
&s
->dpi
.mask
) != s
->dpi
.mask
)
563 tcf_exts_destroy(tp
, &e
);
567 static void rsvp_walk(struct tcf_proto
*tp
, struct tcf_walker
*arg
)
569 struct rsvp_head
*head
= tp
->root
;
575 for (h
= 0; h
< 256; h
++) {
576 struct rsvp_session
*s
;
578 for (s
= head
->ht
[h
]; s
; s
= s
->next
) {
579 for (h1
= 0; h1
<= 16; h1
++) {
580 struct rsvp_filter
*f
;
582 for (f
= s
->ht
[h1
]; f
; f
= f
->next
) {
583 if (arg
->count
< arg
->skip
) {
587 if (arg
->fn(tp
, (unsigned long)f
, arg
) < 0) {
598 static int rsvp_dump(struct tcf_proto
*tp
, unsigned long fh
,
599 struct sk_buff
*skb
, struct tcmsg
*t
)
601 struct rsvp_filter
*f
= (struct rsvp_filter
*)fh
;
602 struct rsvp_session
*s
;
603 unsigned char *b
= skb_tail_pointer(skb
);
605 struct tc_rsvp_pinfo pinfo
;
611 t
->tcm_handle
= f
->handle
;
613 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
615 goto nla_put_failure
;
617 NLA_PUT(skb
, TCA_RSVP_DST
, sizeof(s
->dst
), &s
->dst
);
620 pinfo
.protocol
= s
->protocol
;
621 pinfo
.tunnelid
= s
->tunnelid
;
622 pinfo
.tunnelhdr
= f
->tunnelhdr
;
624 NLA_PUT(skb
, TCA_RSVP_PINFO
, sizeof(pinfo
), &pinfo
);
626 NLA_PUT_U32(skb
, TCA_RSVP_CLASSID
, f
->res
.classid
);
627 if (((f
->handle
>>8)&0xFF) != 16)
628 NLA_PUT(skb
, TCA_RSVP_SRC
, sizeof(f
->src
), f
->src
);
630 if (tcf_exts_dump(skb
, &f
->exts
, &rsvp_ext_map
) < 0)
631 goto nla_put_failure
;
633 nla_nest_end(skb
, nest
);
635 if (tcf_exts_dump_stats(skb
, &f
->exts
, &rsvp_ext_map
) < 0)
636 goto nla_put_failure
;
644 static struct tcf_proto_ops RSVP_OPS
= {
647 .classify
= rsvp_classify
,
649 .destroy
= rsvp_destroy
,
652 .change
= rsvp_change
,
653 .delete = rsvp_delete
,
656 .owner
= THIS_MODULE
,
659 static int __init
init_rsvp(void)
661 return register_tcf_proto_ops(&RSVP_OPS
);
664 static void __exit
exit_rsvp(void)
666 unregister_tcf_proto_ops(&RSVP_OPS
);
669 module_init(init_rsvp
)
670 module_exit(exit_rsvp
)