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;
101 struct rsvp_session *sess;
104 static __inline__ unsigned hash_dst(u32 *dst, u8 protocol, u8 tunnelid)
106 unsigned h = dst[RSVP_DST_LEN-1];
109 return (h ^ protocol ^ tunnelid) & 0xFF;
112 static __inline__ unsigned hash_src(u32 *src)
114 unsigned h = src[RSVP_DST_LEN-1];
121 static struct tcf_ext_map rsvp_ext_map = {
122 .police = TCA_RSVP_POLICE,
123 .action = TCA_RSVP_ACT
126 #define RSVP_APPLY_RESULT() \
128 int r = tcf_exts_exec(skb, &f->exts, res); \
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]
195 if (f->tunnelhdr == 0)
198 tunnelid = f->res.classid;
199 nhptr = (void*)(xprt + f->tunnelhdr - sizeof(*nhptr));
204 /* And wildcard bucket... */
205 for (f = s->ht[16]; f; f = f->next) {
216 static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
218 struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
219 struct rsvp_session *s;
220 struct rsvp_filter *f;
221 unsigned h1 = handle&0xFF;
222 unsigned h2 = (handle>>8)&0xFF;
227 for (s = sht[h1]; s; s = s->next) {
228 for (f = s->ht[h2]; f; f = f->next) {
229 if (f->handle == handle)
230 return (unsigned long)f;
236 static void rsvp_put(struct tcf_proto *tp, unsigned long f)
240 static int rsvp_init(struct tcf_proto *tp)
242 struct rsvp_head *data;
244 data = kmalloc(sizeof(struct rsvp_head), GFP_KERNEL);
246 memset(data, 0, sizeof(struct rsvp_head));
254 rsvp_delete_filter(struct tcf_proto *tp, struct rsvp_filter *f)
256 tcf_unbind_filter(tp, &f->res);
257 tcf_exts_destroy(tp, &f->exts);
261 static void rsvp_destroy(struct tcf_proto *tp)
263 struct rsvp_head *data = xchg(&tp->root, NULL);
264 struct rsvp_session **sht;
272 for (h1=0; h1<256; h1++) {
273 struct rsvp_session *s;
275 while ((s = sht[h1]) != NULL) {
278 for (h2=0; h2<=16; h2++) {
279 struct rsvp_filter *f;
281 while ((f = s->ht[h2]) != NULL) {
283 rsvp_delete_filter(tp, f);
292 static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
294 struct rsvp_filter **fp, *f = (struct rsvp_filter*)arg;
295 unsigned h = f->handle;
296 struct rsvp_session **sp;
297 struct rsvp_session *s = f->sess;
300 for (fp = &s->ht[(h>>8)&0xFF]; *fp; fp = &(*fp)->next) {
305 rsvp_delete_filter(tp, f);
309 for (i=0; i<=16; i++)
313 /* OK, session has no flows */
314 for (sp = &((struct rsvp_head*)tp->root)->ht[h&0xFF];
315 *sp; sp = &(*sp)->next) {
332 static unsigned gen_handle(struct tcf_proto *tp, unsigned salt)
334 struct rsvp_head *data = tp->root;
339 if ((data->hgenerator += 0x10000) == 0)
340 data->hgenerator = 0x10000;
341 h = data->hgenerator|salt;
342 if (rsvp_get(tp, h) == 0)
348 static int tunnel_bts(struct rsvp_head *data)
350 int n = data->tgenerator>>5;
351 u32 b = 1<<(data->tgenerator&0x1F);
359 static void tunnel_recycle(struct rsvp_head *data)
361 struct rsvp_session **sht = data->ht;
365 memset(tmap, 0, sizeof(tmap));
367 for (h1=0; h1<256; h1++) {
368 struct rsvp_session *s;
369 for (s = sht[h1]; s; s = s->next) {
370 for (h2=0; h2<=16; h2++) {
371 struct rsvp_filter *f;
373 for (f = s->ht[h2]; f; f = f->next) {
374 if (f->tunnelhdr == 0)
376 data->tgenerator = f->res.classid;
383 memcpy(data->tmap, tmap, sizeof(tmap));
386 static u32 gen_tunnel(struct rsvp_head *data)
390 for (k=0; k<2; k++) {
391 for (i=255; i>0; i--) {
392 if (++data->tgenerator == 0)
393 data->tgenerator = 1;
394 if (tunnel_bts(data))
395 return data->tgenerator;
397 tunnel_recycle(data);
402 static int rsvp_change(struct tcf_proto *tp, unsigned long base,
407 struct rsvp_head *data = tp->root;
408 struct rsvp_filter *f, **fp;
409 struct rsvp_session *s, **sp;
410 struct tc_rsvp_pinfo *pinfo = NULL;
411 struct rtattr *opt = tca[TCA_OPTIONS-1];
412 struct rtattr *tb[TCA_RSVP_MAX];
419 return handle ? -EINVAL : 0;
421 if (rtattr_parse_nested(tb, TCA_RSVP_MAX, opt) < 0)
424 err = tcf_exts_validate(tp, tb, tca[TCA_RATE-1], &e, &rsvp_ext_map);
428 if ((f = (struct rsvp_filter*)*arg) != NULL) {
429 /* Node exists: adjust only classid */
431 if (f->handle != handle && handle)
433 if (tb[TCA_RSVP_CLASSID-1]) {
434 f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
435 tcf_bind_filter(tp, &f->res, base);
438 tcf_exts_change(tp, &f->exts, &e);
442 /* Now more serious part... */
446 if (tb[TCA_RSVP_DST-1] == NULL)
450 f = kmalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
454 memset(f, 0, sizeof(*f));
456 if (tb[TCA_RSVP_SRC-1]) {
458 if (RTA_PAYLOAD(tb[TCA_RSVP_SRC-1]) != sizeof(f->src))
460 memcpy(f->src, RTA_DATA(tb[TCA_RSVP_SRC-1]), sizeof(f->src));
461 h2 = hash_src(f->src);
463 if (tb[TCA_RSVP_PINFO-1]) {
465 if (RTA_PAYLOAD(tb[TCA_RSVP_PINFO-1]) < sizeof(struct tc_rsvp_pinfo))
467 pinfo = RTA_DATA(tb[TCA_RSVP_PINFO-1]);
469 f->tunnelhdr = pinfo->tunnelhdr;
471 if (tb[TCA_RSVP_CLASSID-1]) {
473 if (RTA_PAYLOAD(tb[TCA_RSVP_CLASSID-1]) != 4)
475 f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
479 if (RTA_PAYLOAD(tb[TCA_RSVP_DST-1]) != sizeof(f->src))
481 dst = RTA_DATA(tb[TCA_RSVP_DST-1]);
482 h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
485 if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
490 if (f->res.classid > 255)
494 if (f->res.classid == 0 &&
495 (f->res.classid = gen_tunnel(data)) == 0)
499 for (sp = &data->ht[h1]; (s=*sp) != NULL; sp = &s->next) {
500 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
501 pinfo && pinfo->protocol == s->protocol &&
502 memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0
503 #if RSVP_DST_LEN == 4
504 && dst[0] == s->dst[0]
505 && dst[1] == s->dst[1]
506 && dst[2] == s->dst[2]
508 && pinfo->tunnelid == s->tunnelid) {
511 /* OK, we found appropriate session */
516 if (f->tunnelhdr == 0)
517 tcf_bind_filter(tp, &f->res, base);
519 tcf_exts_change(tp, &f->exts, &e);
521 for (fp = &s->ht[h2]; *fp; fp = &(*fp)->next)
522 if (((*fp)->spi.mask&f->spi.mask) != f->spi.mask)
528 *arg = (unsigned long)f;
533 /* No session found. Create new one. */
536 s = kmalloc(sizeof(struct rsvp_session), GFP_KERNEL);
539 memset(s, 0, sizeof(*s));
540 memcpy(s->dst, dst, sizeof(s->dst));
544 s->protocol = pinfo->protocol;
545 s->tunnelid = pinfo->tunnelid;
547 for (sp = &data->ht[h1]; *sp; sp = &(*sp)->next) {
548 if (((*sp)->dpi.mask&s->dpi.mask) != s->dpi.mask)
561 tcf_exts_destroy(tp, &e);
565 static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
567 struct rsvp_head *head = tp->root;
573 for (h = 0; h < 256; h++) {
574 struct rsvp_session *s;
576 for (s = head->ht[h]; s; s = s->next) {
577 for (h1 = 0; h1 <= 16; h1++) {
578 struct rsvp_filter *f;
580 for (f = s->ht[h1]; f; f = f->next) {
581 if (arg->count < arg->skip) {
585 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
596 static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
597 struct sk_buff *skb, struct tcmsg *t)
599 struct rsvp_filter *f = (struct rsvp_filter*)fh;
600 struct rsvp_session *s;
601 unsigned char *b = skb->tail;
603 struct tc_rsvp_pinfo pinfo;
609 t->tcm_handle = f->handle;
612 rta = (struct rtattr*)b;
613 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
615 RTA_PUT(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst);
618 pinfo.protocol = s->protocol;
619 pinfo.tunnelid = s->tunnelid;
620 pinfo.tunnelhdr = f->tunnelhdr;
621 RTA_PUT(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo);
623 RTA_PUT(skb, TCA_RSVP_CLASSID, 4, &f->res.classid);
624 if (((f->handle>>8)&0xFF) != 16)
625 RTA_PUT(skb, TCA_RSVP_SRC, sizeof(f->src), f->src);
627 if (tcf_exts_dump(skb, &f->exts, &rsvp_ext_map) < 0)
630 rta->rta_len = skb->tail - b;
632 if (tcf_exts_dump_stats(skb, &f->exts, &rsvp_ext_map) < 0)
637 skb_trim(skb, b - skb->data);
641 static struct tcf_proto_ops RSVP_OPS = {
644 .classify = rsvp_classify,
646 .destroy = rsvp_destroy,
649 .change = rsvp_change,
650 .delete = rsvp_delete,
653 .owner = THIS_MODULE,
656 static int __init init_rsvp(void)
658 return register_tcf_proto_ops(&RSVP_OPS);
661 static void __exit exit_rsvp(void)
663 unregister_tcf_proto_ops(&RSVP_OPS);
666 module_init(init_rsvp)
667 module_exit(exit_rsvp)