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 = ipv6_hdr(skb);
148 struct iphdr *nhptr = ip_hdr(skb);
153 #if RSVP_DST_LEN == 4
154 src = &nhptr->saddr.s6_addr32[0];
155 dst = &nhptr->daddr.s6_addr32[0];
156 protocol = nhptr->nexthdr;
157 xprt = ((u8*)nhptr) + sizeof(struct ipv6hdr);
161 protocol = nhptr->protocol;
162 xprt = ((u8*)nhptr) + (nhptr->ihl<<2);
163 if (nhptr->frag_off & htons(IP_MF|IP_OFFSET))
167 h1 = hash_dst(dst, protocol, tunnelid);
170 for (s = sht[h1]; s; s = s->next) {
171 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
172 protocol == s->protocol &&
173 !(s->dpi.mask & (*(u32*)(xprt+s->dpi.offset)^s->dpi.key))
174 #if RSVP_DST_LEN == 4
175 && dst[0] == s->dst[0]
176 && dst[1] == s->dst[1]
177 && dst[2] == s->dst[2]
179 && tunnelid == s->tunnelid) {
181 for (f = s->ht[h2]; f; f = f->next) {
182 if (src[RSVP_DST_LEN-1] == f->src[RSVP_DST_LEN-1] &&
183 !(f->spi.mask & (*(u32*)(xprt+f->spi.offset)^f->spi.key))
184 #if RSVP_DST_LEN == 4
185 && src[0] == f->src[0]
186 && src[1] == f->src[1]
187 && src[2] == f->src[2]
194 if (f->tunnelhdr == 0)
197 tunnelid = f->res.classid;
198 nhptr = (void*)(xprt + f->tunnelhdr - sizeof(*nhptr));
203 /* And wildcard bucket... */
204 for (f = s->ht[16]; f; f = f->next) {
215 static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
217 struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
218 struct rsvp_session *s;
219 struct rsvp_filter *f;
220 unsigned h1 = handle&0xFF;
221 unsigned h2 = (handle>>8)&0xFF;
226 for (s = sht[h1]; s; s = s->next) {
227 for (f = s->ht[h2]; f; f = f->next) {
228 if (f->handle == handle)
229 return (unsigned long)f;
235 static void rsvp_put(struct tcf_proto *tp, unsigned long f)
239 static int rsvp_init(struct tcf_proto *tp)
241 struct rsvp_head *data;
243 data = kzalloc(sizeof(struct rsvp_head), GFP_KERNEL);
252 rsvp_delete_filter(struct tcf_proto *tp, struct rsvp_filter *f)
254 tcf_unbind_filter(tp, &f->res);
255 tcf_exts_destroy(tp, &f->exts);
259 static void rsvp_destroy(struct tcf_proto *tp)
261 struct rsvp_head *data = xchg(&tp->root, NULL);
262 struct rsvp_session **sht;
270 for (h1=0; h1<256; h1++) {
271 struct rsvp_session *s;
273 while ((s = sht[h1]) != NULL) {
276 for (h2=0; h2<=16; h2++) {
277 struct rsvp_filter *f;
279 while ((f = s->ht[h2]) != NULL) {
281 rsvp_delete_filter(tp, f);
290 static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
292 struct rsvp_filter **fp, *f = (struct rsvp_filter*)arg;
293 unsigned h = f->handle;
294 struct rsvp_session **sp;
295 struct rsvp_session *s = f->sess;
298 for (fp = &s->ht[(h>>8)&0xFF]; *fp; fp = &(*fp)->next) {
303 rsvp_delete_filter(tp, f);
307 for (i=0; i<=16; i++)
311 /* OK, session has no flows */
312 for (sp = &((struct rsvp_head*)tp->root)->ht[h&0xFF];
313 *sp; sp = &(*sp)->next) {
330 static unsigned gen_handle(struct tcf_proto *tp, unsigned salt)
332 struct rsvp_head *data = tp->root;
337 if ((data->hgenerator += 0x10000) == 0)
338 data->hgenerator = 0x10000;
339 h = data->hgenerator|salt;
340 if (rsvp_get(tp, h) == 0)
346 static int tunnel_bts(struct rsvp_head *data)
348 int n = data->tgenerator>>5;
349 u32 b = 1<<(data->tgenerator&0x1F);
357 static void tunnel_recycle(struct rsvp_head *data)
359 struct rsvp_session **sht = data->ht;
363 memset(tmap, 0, sizeof(tmap));
365 for (h1=0; h1<256; h1++) {
366 struct rsvp_session *s;
367 for (s = sht[h1]; s; s = s->next) {
368 for (h2=0; h2<=16; h2++) {
369 struct rsvp_filter *f;
371 for (f = s->ht[h2]; f; f = f->next) {
372 if (f->tunnelhdr == 0)
374 data->tgenerator = f->res.classid;
381 memcpy(data->tmap, tmap, sizeof(tmap));
384 static u32 gen_tunnel(struct rsvp_head *data)
388 for (k=0; k<2; k++) {
389 for (i=255; i>0; i--) {
390 if (++data->tgenerator == 0)
391 data->tgenerator = 1;
392 if (tunnel_bts(data))
393 return data->tgenerator;
395 tunnel_recycle(data);
400 static const struct nla_policy rsvp_policy[TCA_RSVP_MAX + 1] = {
401 [TCA_RSVP_CLASSID] = { .type = NLA_U32 },
402 [TCA_RSVP_DST] = { .type = NLA_BINARY,
403 .len = RSVP_DST_LEN * sizeof(u32) },
404 [TCA_RSVP_SRC] = { .type = NLA_BINARY,
405 .len = RSVP_DST_LEN * sizeof(u32) },
406 [TCA_RSVP_PINFO] = { .len = sizeof(struct tc_rsvp_pinfo) },
409 static int rsvp_change(struct tcf_proto *tp, unsigned long base,
414 struct rsvp_head *data = tp->root;
415 struct rsvp_filter *f, **fp;
416 struct rsvp_session *s, **sp;
417 struct tc_rsvp_pinfo *pinfo = NULL;
418 struct nlattr *opt = tca[TCA_OPTIONS-1];
419 struct nlattr *tb[TCA_RSVP_MAX + 1];
426 return handle ? -EINVAL : 0;
428 err = nla_parse_nested(tb, TCA_RSVP_MAX, opt, rsvp_policy);
432 err = tcf_exts_validate(tp, tb, tca[TCA_RATE-1], &e, &rsvp_ext_map);
436 if ((f = (struct rsvp_filter*)*arg) != NULL) {
437 /* Node exists: adjust only classid */
439 if (f->handle != handle && handle)
441 if (tb[TCA_RSVP_CLASSID-1]) {
442 f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID-1]);
443 tcf_bind_filter(tp, &f->res, base);
446 tcf_exts_change(tp, &f->exts, &e);
450 /* Now more serious part... */
454 if (tb[TCA_RSVP_DST-1] == NULL)
458 f = kzalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
463 if (tb[TCA_RSVP_SRC-1]) {
464 memcpy(f->src, nla_data(tb[TCA_RSVP_SRC-1]), sizeof(f->src));
465 h2 = hash_src(f->src);
467 if (tb[TCA_RSVP_PINFO-1]) {
468 pinfo = nla_data(tb[TCA_RSVP_PINFO-1]);
470 f->tunnelhdr = pinfo->tunnelhdr;
472 if (tb[TCA_RSVP_CLASSID-1])
473 f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID-1]);
475 dst = nla_data(tb[TCA_RSVP_DST-1]);
476 h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
479 if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
484 if (f->res.classid > 255)
488 if (f->res.classid == 0 &&
489 (f->res.classid = gen_tunnel(data)) == 0)
493 for (sp = &data->ht[h1]; (s=*sp) != NULL; sp = &s->next) {
494 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
495 pinfo && pinfo->protocol == s->protocol &&
496 memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0
497 #if RSVP_DST_LEN == 4
498 && dst[0] == s->dst[0]
499 && dst[1] == s->dst[1]
500 && dst[2] == s->dst[2]
502 && pinfo->tunnelid == s->tunnelid) {
505 /* OK, we found appropriate session */
510 if (f->tunnelhdr == 0)
511 tcf_bind_filter(tp, &f->res, base);
513 tcf_exts_change(tp, &f->exts, &e);
515 for (fp = &s->ht[h2]; *fp; fp = &(*fp)->next)
516 if (((*fp)->spi.mask&f->spi.mask) != f->spi.mask)
522 *arg = (unsigned long)f;
527 /* No session found. Create new one. */
530 s = kzalloc(sizeof(struct rsvp_session), GFP_KERNEL);
533 memcpy(s->dst, dst, sizeof(s->dst));
537 s->protocol = pinfo->protocol;
538 s->tunnelid = pinfo->tunnelid;
540 for (sp = &data->ht[h1]; *sp; sp = &(*sp)->next) {
541 if (((*sp)->dpi.mask&s->dpi.mask) != s->dpi.mask)
553 tcf_exts_destroy(tp, &e);
557 static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
559 struct rsvp_head *head = tp->root;
565 for (h = 0; h < 256; h++) {
566 struct rsvp_session *s;
568 for (s = head->ht[h]; s; s = s->next) {
569 for (h1 = 0; h1 <= 16; h1++) {
570 struct rsvp_filter *f;
572 for (f = s->ht[h1]; f; f = f->next) {
573 if (arg->count < arg->skip) {
577 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
588 static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
589 struct sk_buff *skb, struct tcmsg *t)
591 struct rsvp_filter *f = (struct rsvp_filter*)fh;
592 struct rsvp_session *s;
593 unsigned char *b = skb_tail_pointer(skb);
595 struct tc_rsvp_pinfo pinfo;
601 t->tcm_handle = f->handle;
603 nest = nla_nest_start(skb, TCA_OPTIONS);
605 goto nla_put_failure;
607 NLA_PUT(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst);
610 pinfo.protocol = s->protocol;
611 pinfo.tunnelid = s->tunnelid;
612 pinfo.tunnelhdr = f->tunnelhdr;
614 NLA_PUT(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo);
616 NLA_PUT_U32(skb, TCA_RSVP_CLASSID, f->res.classid);
617 if (((f->handle>>8)&0xFF) != 16)
618 NLA_PUT(skb, TCA_RSVP_SRC, sizeof(f->src), f->src);
620 if (tcf_exts_dump(skb, &f->exts, &rsvp_ext_map) < 0)
621 goto nla_put_failure;
623 nla_nest_end(skb, nest);
625 if (tcf_exts_dump_stats(skb, &f->exts, &rsvp_ext_map) < 0)
626 goto nla_put_failure;
634 static struct tcf_proto_ops RSVP_OPS = {
637 .classify = rsvp_classify,
639 .destroy = rsvp_destroy,
642 .change = rsvp_change,
643 .delete = rsvp_delete,
646 .owner = THIS_MODULE,
649 static int __init init_rsvp(void)
651 return register_tcf_proto_ops(&RSVP_OPS);
654 static void __exit exit_rsvp(void)
656 unregister_tcf_proto_ops(&RSVP_OPS);
659 module_init(init_rsvp)
660 module_exit(exit_rsvp)