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. */
68 #include <linux/config.h>
75 struct rsvp_session *ht[256];
80 struct rsvp_session *next;
81 u32 dst[RSVP_DST_LEN];
82 struct tc_rsvp_gpi dpi;
85 /* 16 (src,sport) hash slots, and one wildcard source slot */
86 struct rsvp_filter *ht[16+1];
92 struct rsvp_filter *next;
93 u32 src[RSVP_DST_LEN];
94 struct tc_rsvp_gpi spi;
97 struct tcf_result res;
98 #ifdef CONFIG_NET_CLS_POLICE
99 struct tcf_police *police;
103 struct rsvp_session *sess;
106 static __inline__ unsigned hash_dst(u32 *dst, u8 protocol, u8 tunnelid)
108 unsigned h = dst[RSVP_DST_LEN-1];
111 return (h ^ protocol ^ tunnelid) & 0xFF;
114 static __inline__ unsigned hash_src(u32 *src)
116 unsigned h = src[RSVP_DST_LEN-1];
123 #ifdef CONFIG_NET_CLS_POLICE
124 #define RSVP_POLICE() \
126 int pol_res = tcf_police(skb, f->police); \
127 if (pol_res < 0) continue; \
128 if (pol_res) return pol_res; \
131 #define RSVP_POLICE()
135 static int rsvp_classify(struct sk_buff *skb, struct tcf_proto *tp,
136 struct tcf_result *res)
138 struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
139 struct rsvp_session *s;
140 struct rsvp_filter *f;
146 #if RSVP_DST_LEN == 4
147 struct ipv6hdr *nhptr = skb->nh.ipv6h;
149 struct iphdr *nhptr = skb->nh.iph;
154 #if RSVP_DST_LEN == 4
155 src = &nhptr->saddr.s6_addr32[0];
156 dst = &nhptr->daddr.s6_addr32[0];
157 protocol = nhptr->nexthdr;
158 xprt = ((u8*)nhptr) + sizeof(struct ipv6hdr);
162 protocol = nhptr->protocol;
163 xprt = ((u8*)nhptr) + (nhptr->ihl<<2);
164 if (nhptr->frag_off&__constant_htons(IP_MF|IP_OFFSET))
168 h1 = hash_dst(dst, protocol, tunnelid);
171 for (s = sht[h1]; s; s = s->next) {
172 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
173 protocol == s->protocol &&
174 !(s->dpi.mask & (*(u32*)(xprt+s->dpi.offset)^s->dpi.key))
175 #if RSVP_DST_LEN == 4
176 && dst[0] == s->dst[0]
177 && dst[1] == s->dst[1]
178 && dst[2] == s->dst[2]
180 && tunnelid == s->tunnelid) {
182 for (f = s->ht[h2]; f; f = f->next) {
183 if (src[RSVP_DST_LEN-1] == f->src[RSVP_DST_LEN-1] &&
184 !(f->spi.mask & (*(u32*)(xprt+f->spi.offset)^f->spi.key))
185 #if RSVP_DST_LEN == 4
186 && src[0] == f->src[0]
187 && src[1] == f->src[1]
188 && src[2] == f->src[2]
196 if (f->tunnelhdr == 0)
199 tunnelid = f->res.classid;
200 nhptr = (void*)(xprt + f->tunnelhdr - sizeof(*nhptr));
205 /* And wildcard bucket... */
206 for (f = s->ht[16]; f; f = f->next) {
217 static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
219 struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
220 struct rsvp_session *s;
221 struct rsvp_filter *f;
222 unsigned h1 = handle&0xFF;
223 unsigned h2 = (handle>>8)&0xFF;
228 for (s = sht[h1]; s; s = s->next) {
229 for (f = s->ht[h2]; f; f = f->next) {
230 if (f->handle == handle)
231 return (unsigned long)f;
237 static void rsvp_put(struct tcf_proto *tp, unsigned long f)
241 static int rsvp_init(struct tcf_proto *tp)
243 struct rsvp_head *data;
245 data = kmalloc(sizeof(struct rsvp_head), GFP_KERNEL);
247 memset(data, 0, sizeof(struct rsvp_head));
254 static void rsvp_destroy(struct tcf_proto *tp)
256 struct rsvp_head *data = xchg(&tp->root, NULL);
257 struct rsvp_session **sht;
265 for (h1=0; h1<256; h1++) {
266 struct rsvp_session *s;
268 while ((s = sht[h1]) != NULL) {
271 for (h2=0; h2<=16; h2++) {
272 struct rsvp_filter *f;
274 while ((f = s->ht[h2]) != NULL) {
276 tcf_unbind_filter(tp, &f->res);
277 #ifdef CONFIG_NET_CLS_POLICE
278 tcf_police_release(f->police,TCA_ACT_UNBIND);
289 static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
291 struct rsvp_filter **fp, *f = (struct rsvp_filter*)arg;
292 unsigned h = f->handle;
293 struct rsvp_session **sp;
294 struct rsvp_session *s = f->sess;
297 for (fp = &s->ht[(h>>8)&0xFF]; *fp; fp = &(*fp)->next) {
302 tcf_unbind_filter(tp, &f->res);
303 #ifdef CONFIG_NET_CLS_POLICE
304 tcf_police_release(f->police,TCA_ACT_UNBIND);
311 for (i=0; i<=16; i++)
315 /* OK, session has no flows */
316 for (sp = &((struct rsvp_head*)tp->root)->ht[h&0xFF];
317 *sp; sp = &(*sp)->next) {
334 static unsigned gen_handle(struct tcf_proto *tp, unsigned salt)
336 struct rsvp_head *data = tp->root;
341 if ((data->hgenerator += 0x10000) == 0)
342 data->hgenerator = 0x10000;
343 h = data->hgenerator|salt;
344 if (rsvp_get(tp, h) == 0)
350 static int tunnel_bts(struct rsvp_head *data)
352 int n = data->tgenerator>>5;
353 u32 b = 1<<(data->tgenerator&0x1F);
361 static void tunnel_recycle(struct rsvp_head *data)
363 struct rsvp_session **sht = data->ht;
367 memset(tmap, 0, sizeof(tmap));
369 for (h1=0; h1<256; h1++) {
370 struct rsvp_session *s;
371 for (s = sht[h1]; s; s = s->next) {
372 for (h2=0; h2<=16; h2++) {
373 struct rsvp_filter *f;
375 for (f = s->ht[h2]; f; f = f->next) {
376 if (f->tunnelhdr == 0)
378 data->tgenerator = f->res.classid;
385 memcpy(data->tmap, tmap, sizeof(tmap));
388 static u32 gen_tunnel(struct rsvp_head *data)
392 for (k=0; k<2; k++) {
393 for (i=255; i>0; i--) {
394 if (++data->tgenerator == 0)
395 data->tgenerator = 1;
396 if (tunnel_bts(data))
397 return data->tgenerator;
399 tunnel_recycle(data);
404 static int rsvp_change(struct tcf_proto *tp, unsigned long base,
409 struct rsvp_head *data = tp->root;
410 struct rsvp_filter *f, **fp;
411 struct rsvp_session *s, **sp;
412 struct tc_rsvp_pinfo *pinfo = NULL;
413 struct rtattr *opt = tca[TCA_OPTIONS-1];
414 struct rtattr *tb[TCA_RSVP_MAX];
420 return handle ? -EINVAL : 0;
422 if (rtattr_parse(tb, TCA_RSVP_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)
425 if ((f = (struct rsvp_filter*)*arg) != NULL) {
426 /* Node exists: adjust only classid */
428 if (f->handle != handle && handle)
430 if (tb[TCA_RSVP_CLASSID-1]) {
431 f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
432 tcf_bind_filter(tp, &f->res, base);
434 #ifdef CONFIG_NET_CLS_POLICE
435 if (tb[TCA_RSVP_POLICE-1]) {
436 err = tcf_change_police(tp, &f->police,
437 tb[TCA_RSVP_POLICE-1], tca[TCA_RATE-1]);
445 /* Now more serious part... */
448 if (tb[TCA_RSVP_DST-1] == NULL)
451 f = kmalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
455 memset(f, 0, sizeof(*f));
457 if (tb[TCA_RSVP_SRC-1]) {
459 if (RTA_PAYLOAD(tb[TCA_RSVP_SRC-1]) != sizeof(f->src))
461 memcpy(f->src, RTA_DATA(tb[TCA_RSVP_SRC-1]), sizeof(f->src));
462 h2 = hash_src(f->src);
464 if (tb[TCA_RSVP_PINFO-1]) {
466 if (RTA_PAYLOAD(tb[TCA_RSVP_PINFO-1]) < sizeof(struct tc_rsvp_pinfo))
468 pinfo = RTA_DATA(tb[TCA_RSVP_PINFO-1]);
470 f->tunnelhdr = pinfo->tunnelhdr;
472 if (tb[TCA_RSVP_CLASSID-1]) {
474 if (RTA_PAYLOAD(tb[TCA_RSVP_CLASSID-1]) != 4)
476 f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
480 if (RTA_PAYLOAD(tb[TCA_RSVP_DST-1]) != sizeof(f->src))
482 dst = RTA_DATA(tb[TCA_RSVP_DST-1]);
483 h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
486 if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
491 if (f->res.classid > 255)
495 if (f->res.classid == 0 &&
496 (f->res.classid = gen_tunnel(data)) == 0)
500 for (sp = &data->ht[h1]; (s=*sp) != NULL; sp = &s->next) {
501 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
502 pinfo && pinfo->protocol == s->protocol &&
503 memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0
504 #if RSVP_DST_LEN == 4
505 && dst[0] == s->dst[0]
506 && dst[1] == s->dst[1]
507 && dst[2] == s->dst[2]
509 && pinfo->tunnelid == s->tunnelid) {
512 /* OK, we found appropriate session */
517 if (f->tunnelhdr == 0)
518 tcf_bind_filter(tp, &f->res, base);
519 #ifdef CONFIG_NET_CLS_POLICE
520 if (tb[TCA_RSVP_POLICE-1])
521 tcf_change_police(tp, &f->police, tb[TCA_RSVP_POLICE-1], tca[TCA_RATE-1]);
524 for (fp = &s->ht[h2]; *fp; fp = &(*fp)->next)
525 if (((*fp)->spi.mask&f->spi.mask) != f->spi.mask)
531 *arg = (unsigned long)f;
536 /* No session found. Create new one. */
539 s = kmalloc(sizeof(struct rsvp_session), GFP_KERNEL);
542 memset(s, 0, sizeof(*s));
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)
566 static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
568 struct rsvp_head *head = tp->root;
574 for (h = 0; h < 256; h++) {
575 struct rsvp_session *s;
577 for (s = head->ht[h]; s; s = s->next) {
578 for (h1 = 0; h1 <= 16; h1++) {
579 struct rsvp_filter *f;
581 for (f = s->ht[h1]; f; f = f->next) {
582 if (arg->count < arg->skip) {
586 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
597 static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
598 struct sk_buff *skb, struct tcmsg *t)
600 struct rsvp_filter *f = (struct rsvp_filter*)fh;
601 struct rsvp_session *s;
602 unsigned char *b = skb->tail;
604 struct tc_rsvp_pinfo pinfo;
610 t->tcm_handle = f->handle;
613 rta = (struct rtattr*)b;
614 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
616 RTA_PUT(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst);
619 pinfo.protocol = s->protocol;
620 pinfo.tunnelid = s->tunnelid;
621 pinfo.tunnelhdr = f->tunnelhdr;
622 RTA_PUT(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo);
624 RTA_PUT(skb, TCA_RSVP_CLASSID, 4, &f->res.classid);
625 if (((f->handle>>8)&0xFF) != 16)
626 RTA_PUT(skb, TCA_RSVP_SRC, sizeof(f->src), f->src);
627 #ifdef CONFIG_NET_CLS_POLICE
628 if (tcf_dump_police(skb, f->police, TCA_RSVP_POLICE) < 0)
632 rta->rta_len = skb->tail - b;
633 #ifdef CONFIG_NET_CLS_POLICE
635 if (tcf_police_dump_stats(skb, f->police) < 0)
641 skb_trim(skb, b - skb->data);
645 static struct tcf_proto_ops RSVP_OPS = {
648 .classify = rsvp_classify,
650 .destroy = rsvp_destroy,
653 .change = rsvp_change,
654 .delete = rsvp_delete,
657 .owner = THIS_MODULE,
660 static int __init init_rsvp(void)
662 return register_tcf_proto_ops(&RSVP_OPS);
665 static void __exit exit_rsvp(void)
667 unregister_tcf_proto_ops(&RSVP_OPS);
670 module_init(init_rsvp)
671 module_exit(exit_rsvp)