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 *ht[256];
77 struct rsvp_session *next;
78 __be32 dst[RSVP_DST_LEN];
79 struct tc_rsvp_gpi dpi;
82 /* 16 (src,sport) hash slots, and one wildcard source slot */
83 struct rsvp_filter *ht[16 + 1];
88 struct rsvp_filter *next;
89 __be32 src[RSVP_DST_LEN];
90 struct tc_rsvp_gpi spi;
93 struct tcf_result res;
97 struct rsvp_session *sess;
100 static inline unsigned int hash_dst(__be32 *dst, u8 protocol, u8 tunnelid)
102 unsigned int h = (__force __u32)dst[RSVP_DST_LEN - 1];
106 return (h ^ protocol ^ tunnelid) & 0xFF;
109 static inline unsigned int hash_src(__be32 *src)
111 unsigned int h = (__force __u32)src[RSVP_DST_LEN-1];
119 static struct tcf_ext_map rsvp_ext_map = {
120 .police = TCA_RSVP_POLICE,
121 .action = TCA_RSVP_ACT
124 #define RSVP_APPLY_RESULT() \
126 int r = tcf_exts_exec(skb, &f->exts, res); \
133 static int rsvp_classify(struct sk_buff *skb, const struct tcf_proto *tp,
134 struct tcf_result *res)
136 struct rsvp_session **sht = ((struct rsvp_head *)tp->root)->ht;
137 struct rsvp_session *s;
138 struct rsvp_filter *f;
144 #if RSVP_DST_LEN == 4
145 struct ipv6hdr *nhptr;
147 if (!pskb_network_may_pull(skb, sizeof(*nhptr)))
149 nhptr = ipv6_hdr(skb);
153 if (!pskb_network_may_pull(skb, sizeof(*nhptr)))
160 #if RSVP_DST_LEN == 4
161 src = &nhptr->saddr.s6_addr32[0];
162 dst = &nhptr->daddr.s6_addr32[0];
163 protocol = nhptr->nexthdr;
164 xprt = ((u8 *)nhptr) + sizeof(struct ipv6hdr);
168 protocol = nhptr->protocol;
169 xprt = ((u8 *)nhptr) + (nhptr->ihl<<2);
170 if (ip_is_fragment(nhptr))
174 h1 = hash_dst(dst, protocol, tunnelid);
177 for (s = sht[h1]; s; s = s->next) {
178 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN - 1] &&
179 protocol == s->protocol &&
181 (*(u32 *)(xprt + s->dpi.offset) ^ s->dpi.key)) &&
182 #if RSVP_DST_LEN == 4
183 dst[0] == s->dst[0] &&
184 dst[1] == s->dst[1] &&
185 dst[2] == s->dst[2] &&
187 tunnelid == s->tunnelid) {
189 for (f = s->ht[h2]; f; f = 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 = s->ht[16]; f; f = f->next) {
224 static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
226 struct rsvp_session **sht = ((struct rsvp_head *)tp->root)->ht;
227 struct rsvp_session *s;
228 struct rsvp_filter *f;
229 unsigned int h1 = handle & 0xFF;
230 unsigned int h2 = (handle >> 8) & 0xFF;
235 for (s = sht[h1]; s; s = s->next) {
236 for (f = s->ht[h2]; f; f = f->next) {
237 if (f->handle == handle)
238 return (unsigned long)f;
244 static void rsvp_put(struct tcf_proto *tp, unsigned long f)
248 static int rsvp_init(struct tcf_proto *tp)
250 struct rsvp_head *data;
252 data = kzalloc(sizeof(struct rsvp_head), GFP_KERNEL);
261 rsvp_delete_filter(struct tcf_proto *tp, struct rsvp_filter *f)
263 tcf_unbind_filter(tp, &f->res);
264 tcf_exts_destroy(tp, &f->exts);
268 static void rsvp_destroy(struct tcf_proto *tp)
270 struct rsvp_head *data = xchg(&tp->root, NULL);
271 struct rsvp_session **sht;
279 for (h1 = 0; h1 < 256; h1++) {
280 struct rsvp_session *s;
282 while ((s = sht[h1]) != NULL) {
285 for (h2 = 0; h2 <= 16; h2++) {
286 struct rsvp_filter *f;
288 while ((f = s->ht[h2]) != NULL) {
290 rsvp_delete_filter(tp, f);
299 static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
301 struct rsvp_filter **fp, *f = (struct rsvp_filter *)arg;
302 unsigned int h = f->handle;
303 struct rsvp_session **sp;
304 struct rsvp_session *s = f->sess;
307 for (fp = &s->ht[(h >> 8) & 0xFF]; *fp; fp = &(*fp)->next) {
312 rsvp_delete_filter(tp, f);
316 for (i = 0; i <= 16; i++)
320 /* OK, session has no flows */
321 for (sp = &((struct rsvp_head *)tp->root)->ht[h & 0xFF];
322 *sp; sp = &(*sp)->next) {
339 static unsigned int gen_handle(struct tcf_proto *tp, unsigned salt)
341 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);
361 if (data->tmap[n] & b)
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 f = (struct rsvp_filter *)*arg;
448 /* Node exists: adjust only classid */
450 if (f->handle != handle && handle)
452 if (tb[TCA_RSVP_CLASSID-1]) {
453 f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID-1]);
454 tcf_bind_filter(tp, &f->res, base);
457 tcf_exts_change(tp, &f->exts, &e);
461 /* Now more serious part... */
465 if (tb[TCA_RSVP_DST-1] == NULL)
469 f = kzalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
474 if (tb[TCA_RSVP_SRC-1]) {
475 memcpy(f->src, nla_data(tb[TCA_RSVP_SRC-1]), sizeof(f->src));
476 h2 = hash_src(f->src);
478 if (tb[TCA_RSVP_PINFO-1]) {
479 pinfo = nla_data(tb[TCA_RSVP_PINFO-1]);
481 f->tunnelhdr = pinfo->tunnelhdr;
483 if (tb[TCA_RSVP_CLASSID-1])
484 f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID-1]);
486 dst = nla_data(tb[TCA_RSVP_DST-1]);
487 h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
490 if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
495 if (f->res.classid > 255)
499 if (f->res.classid == 0 &&
500 (f->res.classid = gen_tunnel(data)) == 0)
504 for (sp = &data->ht[h1]; (s = *sp) != NULL; sp = &s->next) {
505 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
506 pinfo && pinfo->protocol == s->protocol &&
507 memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0 &&
508 #if RSVP_DST_LEN == 4
509 dst[0] == s->dst[0] &&
510 dst[1] == s->dst[1] &&
511 dst[2] == s->dst[2] &&
513 pinfo->tunnelid == s->tunnelid) {
516 /* OK, we found appropriate session */
521 if (f->tunnelhdr == 0)
522 tcf_bind_filter(tp, &f->res, base);
524 tcf_exts_change(tp, &f->exts, &e);
526 for (fp = &s->ht[h2]; *fp; fp = &(*fp)->next)
527 if (((*fp)->spi.mask & f->spi.mask) != f->spi.mask)
533 *arg = (unsigned long)f;
538 /* No session found. Create new one. */
541 s = kzalloc(sizeof(struct rsvp_session), GFP_KERNEL);
544 memcpy(s->dst, dst, sizeof(s->dst));
548 s->protocol = pinfo->protocol;
549 s->tunnelid = pinfo->tunnelid;
551 for (sp = &data->ht[h1]; *sp; sp = &(*sp)->next) {
552 if (((*sp)->dpi.mask&s->dpi.mask) != s->dpi.mask)
564 tcf_exts_destroy(tp, &e);
568 static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
570 struct rsvp_head *head = tp->root;
576 for (h = 0; h < 256; h++) {
577 struct rsvp_session *s;
579 for (s = head->ht[h]; s; s = s->next) {
580 for (h1 = 0; h1 <= 16; h1++) {
581 struct rsvp_filter *f;
583 for (f = s->ht[h1]; f; f = f->next) {
584 if (arg->count < arg->skip) {
588 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
599 static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
600 struct sk_buff *skb, struct tcmsg *t)
602 struct rsvp_filter *f = (struct rsvp_filter *)fh;
603 struct rsvp_session *s;
604 unsigned char *b = skb_tail_pointer(skb);
606 struct tc_rsvp_pinfo pinfo;
612 t->tcm_handle = f->handle;
614 nest = nla_nest_start(skb, TCA_OPTIONS);
616 goto nla_put_failure;
618 NLA_PUT(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst);
621 pinfo.protocol = s->protocol;
622 pinfo.tunnelid = s->tunnelid;
623 pinfo.tunnelhdr = f->tunnelhdr;
625 NLA_PUT(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo);
627 NLA_PUT_U32(skb, TCA_RSVP_CLASSID, f->res.classid);
628 if (((f->handle >> 8) & 0xFF) != 16)
629 NLA_PUT(skb, TCA_RSVP_SRC, sizeof(f->src), f->src);
631 if (tcf_exts_dump(skb, &f->exts, &rsvp_ext_map) < 0)
632 goto nla_put_failure;
634 nla_nest_end(skb, nest);
636 if (tcf_exts_dump_stats(skb, &f->exts, &rsvp_ext_map) < 0)
637 goto nla_put_failure;
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)