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. */
73 struct rsvp_session __rcu
*ht
[256];
78 struct rsvp_session __rcu
*next
;
79 __be32 dst
[RSVP_DST_LEN
];
80 struct tc_rsvp_gpi dpi
;
83 /* 16 (src,sport) hash slots, and one wildcard source slot */
84 struct rsvp_filter __rcu
*ht
[16 + 1];
90 struct rsvp_filter __rcu
*next
;
91 __be32 src
[RSVP_DST_LEN
];
92 struct tc_rsvp_gpi spi
;
95 struct tcf_result res
;
99 struct rsvp_session
*sess
;
103 static inline unsigned int hash_dst(__be32
*dst
, u8 protocol
, u8 tunnelid
)
105 unsigned int h
= (__force __u32
)dst
[RSVP_DST_LEN
- 1];
109 return (h
^ protocol
^ tunnelid
) & 0xFF;
112 static inline unsigned int hash_src(__be32
*src
)
114 unsigned int h
= (__force __u32
)src
[RSVP_DST_LEN
-1];
122 #define RSVP_APPLY_RESULT() \
124 int r = tcf_exts_exec(skb, &f->exts, res); \
131 static int rsvp_classify(struct sk_buff
*skb
, const struct tcf_proto
*tp
,
132 struct tcf_result
*res
)
134 struct rsvp_head
*head
= rcu_dereference_bh(tp
->root
);
135 struct rsvp_session
*s
;
136 struct rsvp_filter
*f
;
142 #if RSVP_DST_LEN == 4
143 struct ipv6hdr
*nhptr
;
145 if (!pskb_network_may_pull(skb
, sizeof(*nhptr
)))
147 nhptr
= ipv6_hdr(skb
);
151 if (!pskb_network_may_pull(skb
, sizeof(*nhptr
)))
158 #if RSVP_DST_LEN == 4
159 src
= &nhptr
->saddr
.s6_addr32
[0];
160 dst
= &nhptr
->daddr
.s6_addr32
[0];
161 protocol
= nhptr
->nexthdr
;
162 xprt
= ((u8
*)nhptr
) + sizeof(struct ipv6hdr
);
166 protocol
= nhptr
->protocol
;
167 xprt
= ((u8
*)nhptr
) + (nhptr
->ihl
<<2);
168 if (ip_is_fragment(nhptr
))
172 h1
= hash_dst(dst
, protocol
, tunnelid
);
175 for (s
= rcu_dereference_bh(head
->ht
[h1
]); s
;
176 s
= rcu_dereference_bh(s
->next
)) {
177 if (dst
[RSVP_DST_LEN
-1] == s
->dst
[RSVP_DST_LEN
- 1] &&
178 protocol
== s
->protocol
&&
180 (*(u32
*)(xprt
+ s
->dpi
.offset
) ^ s
->dpi
.key
)) &&
181 #if RSVP_DST_LEN == 4
182 dst
[0] == s
->dst
[0] &&
183 dst
[1] == s
->dst
[1] &&
184 dst
[2] == s
->dst
[2] &&
186 tunnelid
== s
->tunnelid
) {
188 for (f
= rcu_dereference_bh(s
->ht
[h2
]); f
;
189 f
= rcu_dereference_bh(f
->next
)) {
190 if (src
[RSVP_DST_LEN
-1] == f
->src
[RSVP_DST_LEN
- 1] &&
191 !(f
->spi
.mask
& (*(u32
*)(xprt
+ f
->spi
.offset
) ^ f
->spi
.key
))
192 #if RSVP_DST_LEN == 4
194 src
[0] == f
->src
[0] &&
195 src
[1] == f
->src
[1] &&
203 if (f
->tunnelhdr
== 0)
206 tunnelid
= f
->res
.classid
;
207 nhptr
= (void *)(xprt
+ f
->tunnelhdr
- sizeof(*nhptr
));
212 /* And wildcard bucket... */
213 for (f
= rcu_dereference_bh(s
->ht
[16]); f
;
214 f
= rcu_dereference_bh(f
->next
)) {
225 static void rsvp_replace(struct tcf_proto
*tp
, struct rsvp_filter
*n
, u32 h
)
227 struct rsvp_head
*head
= rtnl_dereference(tp
->root
);
228 struct rsvp_session
*s
;
229 struct rsvp_filter __rcu
**ins
;
230 struct rsvp_filter
*pins
;
231 unsigned int h1
= h
& 0xFF;
232 unsigned int h2
= (h
>> 8) & 0xFF;
234 for (s
= rtnl_dereference(head
->ht
[h1
]); s
;
235 s
= rtnl_dereference(s
->next
)) {
236 for (ins
= &s
->ht
[h2
], pins
= rtnl_dereference(*ins
); ;
237 ins
= &pins
->next
, pins
= rtnl_dereference(*ins
)) {
238 if (pins
->handle
== h
) {
239 RCU_INIT_POINTER(n
->next
, pins
->next
);
240 rcu_assign_pointer(*ins
, n
);
246 /* Something went wrong if we are trying to replace a non-existant
247 * node. Mind as well halt instead of silently failing.
252 static unsigned long rsvp_get(struct tcf_proto
*tp
, u32 handle
)
254 struct rsvp_head
*head
= rtnl_dereference(tp
->root
);
255 struct rsvp_session
*s
;
256 struct rsvp_filter
*f
;
257 unsigned int h1
= handle
& 0xFF;
258 unsigned int h2
= (handle
>> 8) & 0xFF;
263 for (s
= rtnl_dereference(head
->ht
[h1
]); s
;
264 s
= rtnl_dereference(s
->next
)) {
265 for (f
= rtnl_dereference(s
->ht
[h2
]); f
;
266 f
= rtnl_dereference(f
->next
)) {
267 if (f
->handle
== handle
)
268 return (unsigned long)f
;
274 static void rsvp_put(struct tcf_proto
*tp
, unsigned long f
)
278 static int rsvp_init(struct tcf_proto
*tp
)
280 struct rsvp_head
*data
;
282 data
= kzalloc(sizeof(struct rsvp_head
), GFP_KERNEL
);
284 rcu_assign_pointer(tp
->root
, data
);
291 rsvp_delete_filter(struct tcf_proto
*tp
, struct rsvp_filter
*f
)
293 tcf_unbind_filter(tp
, &f
->res
);
294 tcf_exts_destroy(&f
->exts
);
298 static void rsvp_destroy(struct tcf_proto
*tp
)
300 struct rsvp_head
*data
= rtnl_dereference(tp
->root
);
306 RCU_INIT_POINTER(tp
->root
, NULL
);
308 for (h1
= 0; h1
< 256; h1
++) {
309 struct rsvp_session
*s
;
311 while ((s
= rtnl_dereference(data
->ht
[h1
])) != NULL
) {
312 RCU_INIT_POINTER(data
->ht
[h1
], s
->next
);
314 for (h2
= 0; h2
<= 16; h2
++) {
315 struct rsvp_filter
*f
;
317 while ((f
= rtnl_dereference(s
->ht
[h2
])) != NULL
) {
318 rcu_assign_pointer(s
->ht
[h2
], f
->next
);
319 rsvp_delete_filter(tp
, f
);
325 kfree_rcu(data
, rcu
);
328 static int rsvp_delete(struct tcf_proto
*tp
, unsigned long arg
)
330 struct rsvp_head
*head
= rtnl_dereference(tp
->root
);
331 struct rsvp_filter
*nfp
, *f
= (struct rsvp_filter
*)arg
;
332 struct rsvp_filter __rcu
**fp
;
333 unsigned int h
= f
->handle
;
334 struct rsvp_session __rcu
**sp
;
335 struct rsvp_session
*nsp
, *s
= f
->sess
;
338 fp
= &s
->ht
[(h
>> 8) & 0xFF];
339 for (nfp
= rtnl_dereference(*fp
); nfp
;
340 fp
= &nfp
->next
, nfp
= rtnl_dereference(*fp
)) {
342 RCU_INIT_POINTER(*fp
, f
->next
);
343 rsvp_delete_filter(tp
, f
);
347 for (i
= 0; i
<= 16; i
++)
351 /* OK, session has no flows */
352 sp
= &head
->ht
[h
& 0xFF];
353 for (nsp
= rtnl_dereference(*sp
); nsp
;
354 sp
= &nsp
->next
, nsp
= rtnl_dereference(*sp
)) {
356 RCU_INIT_POINTER(*sp
, s
->next
);
368 static unsigned int gen_handle(struct tcf_proto
*tp
, unsigned salt
)
370 struct rsvp_head
*data
= rtnl_dereference(tp
->root
);
376 if ((data
->hgenerator
+= 0x10000) == 0)
377 data
->hgenerator
= 0x10000;
378 h
= data
->hgenerator
|salt
;
379 if (rsvp_get(tp
, h
) == 0)
385 static int tunnel_bts(struct rsvp_head
*data
)
387 int n
= data
->tgenerator
>> 5;
388 u32 b
= 1 << (data
->tgenerator
& 0x1F);
390 if (data
->tmap
[n
] & b
)
396 static void tunnel_recycle(struct rsvp_head
*data
)
398 struct rsvp_session __rcu
**sht
= data
->ht
;
402 memset(tmap
, 0, sizeof(tmap
));
404 for (h1
= 0; h1
< 256; h1
++) {
405 struct rsvp_session
*s
;
406 for (s
= rtnl_dereference(sht
[h1
]); s
;
407 s
= rtnl_dereference(s
->next
)) {
408 for (h2
= 0; h2
<= 16; h2
++) {
409 struct rsvp_filter
*f
;
411 for (f
= rtnl_dereference(s
->ht
[h2
]); f
;
412 f
= rtnl_dereference(f
->next
)) {
413 if (f
->tunnelhdr
== 0)
415 data
->tgenerator
= f
->res
.classid
;
422 memcpy(data
->tmap
, tmap
, sizeof(tmap
));
425 static u32
gen_tunnel(struct rsvp_head
*data
)
429 for (k
= 0; k
< 2; k
++) {
430 for (i
= 255; i
> 0; i
--) {
431 if (++data
->tgenerator
== 0)
432 data
->tgenerator
= 1;
433 if (tunnel_bts(data
))
434 return data
->tgenerator
;
436 tunnel_recycle(data
);
441 static const struct nla_policy rsvp_policy
[TCA_RSVP_MAX
+ 1] = {
442 [TCA_RSVP_CLASSID
] = { .type
= NLA_U32
},
443 [TCA_RSVP_DST
] = { .type
= NLA_BINARY
,
444 .len
= RSVP_DST_LEN
* sizeof(u32
) },
445 [TCA_RSVP_SRC
] = { .type
= NLA_BINARY
,
446 .len
= RSVP_DST_LEN
* sizeof(u32
) },
447 [TCA_RSVP_PINFO
] = { .len
= sizeof(struct tc_rsvp_pinfo
) },
450 static int rsvp_change(struct net
*net
, struct sk_buff
*in_skb
,
451 struct tcf_proto
*tp
, unsigned long base
,
454 unsigned long *arg
, bool ovr
)
456 struct rsvp_head
*data
= rtnl_dereference(tp
->root
);
457 struct rsvp_filter
*f
, *nfp
;
458 struct rsvp_filter __rcu
**fp
;
459 struct rsvp_session
*nsp
, *s
;
460 struct rsvp_session __rcu
**sp
;
461 struct tc_rsvp_pinfo
*pinfo
= NULL
;
462 struct nlattr
*opt
= tca
[TCA_OPTIONS
];
463 struct nlattr
*tb
[TCA_RSVP_MAX
+ 1];
470 return handle
? -EINVAL
: 0;
472 err
= nla_parse_nested(tb
, TCA_RSVP_MAX
, opt
, rsvp_policy
);
476 tcf_exts_init(&e
, TCA_RSVP_ACT
, TCA_RSVP_POLICE
);
477 err
= tcf_exts_validate(net
, tp
, tb
, tca
[TCA_RATE
], &e
, ovr
);
481 f
= (struct rsvp_filter
*)*arg
;
483 /* Node exists: adjust only classid */
484 struct rsvp_filter
*n
;
486 if (f
->handle
!= handle
&& handle
)
489 n
= kmemdup(f
, sizeof(*f
), GFP_KERNEL
);
495 tcf_exts_init(&n
->exts
, TCA_RSVP_ACT
, TCA_RSVP_POLICE
);
497 if (tb
[TCA_RSVP_CLASSID
]) {
498 n
->res
.classid
= nla_get_u32(tb
[TCA_RSVP_CLASSID
]);
499 tcf_bind_filter(tp
, &n
->res
, base
);
502 tcf_exts_change(tp
, &n
->exts
, &e
);
503 rsvp_replace(tp
, n
, handle
);
507 /* Now more serious part... */
511 if (tb
[TCA_RSVP_DST
] == NULL
)
515 f
= kzalloc(sizeof(struct rsvp_filter
), GFP_KERNEL
);
519 tcf_exts_init(&f
->exts
, TCA_RSVP_ACT
, TCA_RSVP_POLICE
);
521 if (tb
[TCA_RSVP_SRC
]) {
522 memcpy(f
->src
, nla_data(tb
[TCA_RSVP_SRC
]), sizeof(f
->src
));
523 h2
= hash_src(f
->src
);
525 if (tb
[TCA_RSVP_PINFO
]) {
526 pinfo
= nla_data(tb
[TCA_RSVP_PINFO
]);
528 f
->tunnelhdr
= pinfo
->tunnelhdr
;
530 if (tb
[TCA_RSVP_CLASSID
])
531 f
->res
.classid
= nla_get_u32(tb
[TCA_RSVP_CLASSID
]);
533 dst
= nla_data(tb
[TCA_RSVP_DST
]);
534 h1
= hash_dst(dst
, pinfo
? pinfo
->protocol
: 0, pinfo
? pinfo
->tunnelid
: 0);
537 if ((f
->handle
= gen_handle(tp
, h1
| (h2
<<8))) == 0)
542 if (f
->res
.classid
> 255)
546 if (f
->res
.classid
== 0 &&
547 (f
->res
.classid
= gen_tunnel(data
)) == 0)
551 for (sp
= &data
->ht
[h1
];
552 (s
= rtnl_dereference(*sp
)) != NULL
;
554 if (dst
[RSVP_DST_LEN
-1] == s
->dst
[RSVP_DST_LEN
-1] &&
555 pinfo
&& pinfo
->protocol
== s
->protocol
&&
556 memcmp(&pinfo
->dpi
, &s
->dpi
, sizeof(s
->dpi
)) == 0 &&
557 #if RSVP_DST_LEN == 4
558 dst
[0] == s
->dst
[0] &&
559 dst
[1] == s
->dst
[1] &&
560 dst
[2] == s
->dst
[2] &&
562 pinfo
->tunnelid
== s
->tunnelid
) {
565 /* OK, we found appropriate session */
570 if (f
->tunnelhdr
== 0)
571 tcf_bind_filter(tp
, &f
->res
, base
);
573 tcf_exts_change(tp
, &f
->exts
, &e
);
576 for (nfp
= rtnl_dereference(*fp
); nfp
;
577 fp
= &nfp
->next
, nfp
= rtnl_dereference(*fp
)) {
578 __u32 mask
= nfp
->spi
.mask
& f
->spi
.mask
;
580 if (mask
!= f
->spi
.mask
)
583 RCU_INIT_POINTER(f
->next
, nfp
);
584 rcu_assign_pointer(*fp
, f
);
586 *arg
= (unsigned long)f
;
591 /* No session found. Create new one. */
594 s
= kzalloc(sizeof(struct rsvp_session
), GFP_KERNEL
);
597 memcpy(s
->dst
, dst
, sizeof(s
->dst
));
601 s
->protocol
= pinfo
->protocol
;
602 s
->tunnelid
= pinfo
->tunnelid
;
605 for (nsp
= rtnl_dereference(*sp
); nsp
;
606 sp
= &nsp
->next
, nsp
= rtnl_dereference(*sp
)) {
607 if ((nsp
->dpi
.mask
& s
->dpi
.mask
) != s
->dpi
.mask
)
610 RCU_INIT_POINTER(s
->next
, nsp
);
611 rcu_assign_pointer(*sp
, s
);
618 tcf_exts_destroy(&e
);
622 static void rsvp_walk(struct tcf_proto
*tp
, struct tcf_walker
*arg
)
624 struct rsvp_head
*head
= rtnl_dereference(tp
->root
);
630 for (h
= 0; h
< 256; h
++) {
631 struct rsvp_session
*s
;
633 for (s
= rtnl_dereference(head
->ht
[h
]); s
;
634 s
= rtnl_dereference(s
->next
)) {
635 for (h1
= 0; h1
<= 16; h1
++) {
636 struct rsvp_filter
*f
;
638 for (f
= rtnl_dereference(s
->ht
[h1
]); f
;
639 f
= rtnl_dereference(f
->next
)) {
640 if (arg
->count
< arg
->skip
) {
644 if (arg
->fn(tp
, (unsigned long)f
, arg
) < 0) {
655 static int rsvp_dump(struct net
*net
, struct tcf_proto
*tp
, unsigned long fh
,
656 struct sk_buff
*skb
, struct tcmsg
*t
)
658 struct rsvp_filter
*f
= (struct rsvp_filter
*)fh
;
659 struct rsvp_session
*s
;
660 unsigned char *b
= skb_tail_pointer(skb
);
662 struct tc_rsvp_pinfo pinfo
;
668 t
->tcm_handle
= f
->handle
;
670 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
672 goto nla_put_failure
;
674 if (nla_put(skb
, TCA_RSVP_DST
, sizeof(s
->dst
), &s
->dst
))
675 goto nla_put_failure
;
678 pinfo
.protocol
= s
->protocol
;
679 pinfo
.tunnelid
= s
->tunnelid
;
680 pinfo
.tunnelhdr
= f
->tunnelhdr
;
682 if (nla_put(skb
, TCA_RSVP_PINFO
, sizeof(pinfo
), &pinfo
))
683 goto nla_put_failure
;
684 if (f
->res
.classid
&&
685 nla_put_u32(skb
, TCA_RSVP_CLASSID
, f
->res
.classid
))
686 goto nla_put_failure
;
687 if (((f
->handle
>> 8) & 0xFF) != 16 &&
688 nla_put(skb
, TCA_RSVP_SRC
, sizeof(f
->src
), f
->src
))
689 goto nla_put_failure
;
691 if (tcf_exts_dump(skb
, &f
->exts
) < 0)
692 goto nla_put_failure
;
694 nla_nest_end(skb
, nest
);
696 if (tcf_exts_dump_stats(skb
, &f
->exts
) < 0)
697 goto nla_put_failure
;
705 static struct tcf_proto_ops RSVP_OPS __read_mostly
= {
707 .classify
= rsvp_classify
,
709 .destroy
= rsvp_destroy
,
712 .change
= rsvp_change
,
713 .delete = rsvp_delete
,
716 .owner
= THIS_MODULE
,
719 static int __init
init_rsvp(void)
721 return register_tcf_proto_ops(&RSVP_OPS
);
724 static void __exit
exit_rsvp(void)
726 unregister_tcf_proto_ops(&RSVP_OPS
);
729 module_init(init_rsvp
)
730 module_exit(exit_rsvp
)