ARM: pmu: add support for interrupt-affinity property
[linux/fpc-iii.git] / net / sched / cls_rsvp.h
blobedd8ade3fbc1f4358b4275940e6f62b3d814b3dd
1 /*
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.
22 IMPLEMENTATION.
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
43 should be wildcard.
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. */
69 struct rsvp_head {
70 u32 tmap[256/32];
71 u32 hgenerator;
72 u8 tgenerator;
73 struct rsvp_session __rcu *ht[256];
74 struct rcu_head rcu;
77 struct rsvp_session {
78 struct rsvp_session __rcu *next;
79 __be32 dst[RSVP_DST_LEN];
80 struct tc_rsvp_gpi dpi;
81 u8 protocol;
82 u8 tunnelid;
83 /* 16 (src,sport) hash slots, and one wildcard source slot */
84 struct rsvp_filter __rcu *ht[16 + 1];
85 struct rcu_head rcu;
89 struct rsvp_filter {
90 struct rsvp_filter __rcu *next;
91 __be32 src[RSVP_DST_LEN];
92 struct tc_rsvp_gpi spi;
93 u8 tunnelhdr;
95 struct tcf_result res;
96 struct tcf_exts exts;
98 u32 handle;
99 struct rsvp_session *sess;
100 struct rcu_head rcu;
103 static inline unsigned int hash_dst(__be32 *dst, u8 protocol, u8 tunnelid)
105 unsigned int h = (__force __u32)dst[RSVP_DST_LEN - 1];
107 h ^= h>>16;
108 h ^= h>>8;
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];
116 h ^= h>>16;
117 h ^= h>>8;
118 h ^= h>>4;
119 return h & 0xF;
122 #define RSVP_APPLY_RESULT() \
124 int r = tcf_exts_exec(skb, &f->exts, res); \
125 if (r < 0) \
126 continue; \
127 else if (r > 0) \
128 return r; \
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;
137 unsigned int h1, h2;
138 __be32 *dst, *src;
139 u8 protocol;
140 u8 tunnelid = 0;
141 u8 *xprt;
142 #if RSVP_DST_LEN == 4
143 struct ipv6hdr *nhptr;
145 if (!pskb_network_may_pull(skb, sizeof(*nhptr)))
146 return -1;
147 nhptr = ipv6_hdr(skb);
148 #else
149 struct iphdr *nhptr;
151 if (!pskb_network_may_pull(skb, sizeof(*nhptr)))
152 return -1;
153 nhptr = ip_hdr(skb);
154 #endif
156 restart:
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);
163 #else
164 src = &nhptr->saddr;
165 dst = &nhptr->daddr;
166 protocol = nhptr->protocol;
167 xprt = ((u8 *)nhptr) + (nhptr->ihl<<2);
168 if (ip_is_fragment(nhptr))
169 return -1;
170 #endif
172 h1 = hash_dst(dst, protocol, tunnelid);
173 h2 = hash_src(src);
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 &&
179 !(s->dpi.mask &
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] &&
185 #endif
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] &&
196 src[2] == f->src[2]
197 #endif
199 *res = f->res;
200 RSVP_APPLY_RESULT();
202 matched:
203 if (f->tunnelhdr == 0)
204 return 0;
206 tunnelid = f->res.classid;
207 nhptr = (void *)(xprt + f->tunnelhdr - sizeof(*nhptr));
208 goto restart;
212 /* And wildcard bucket... */
213 for (f = rcu_dereference_bh(s->ht[16]); f;
214 f = rcu_dereference_bh(f->next)) {
215 *res = f->res;
216 RSVP_APPLY_RESULT();
217 goto matched;
219 return -1;
222 return -1;
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);
241 return;
246 /* Something went wrong if we are trying to replace a non-existant
247 * node. Mind as well halt instead of silently failing.
249 BUG_ON(1);
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;
260 if (h2 > 16)
261 return 0;
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;
271 return 0;
274 static int rsvp_init(struct tcf_proto *tp)
276 struct rsvp_head *data;
278 data = kzalloc(sizeof(struct rsvp_head), GFP_KERNEL);
279 if (data) {
280 rcu_assign_pointer(tp->root, data);
281 return 0;
283 return -ENOBUFS;
286 static void
287 rsvp_delete_filter(struct tcf_proto *tp, struct rsvp_filter *f)
289 tcf_unbind_filter(tp, &f->res);
290 tcf_exts_destroy(&f->exts);
291 kfree_rcu(f, rcu);
294 static void rsvp_destroy(struct tcf_proto *tp)
296 struct rsvp_head *data = rtnl_dereference(tp->root);
297 int h1, h2;
299 if (data == NULL)
300 return;
302 RCU_INIT_POINTER(tp->root, NULL);
304 for (h1 = 0; h1 < 256; h1++) {
305 struct rsvp_session *s;
307 while ((s = rtnl_dereference(data->ht[h1])) != NULL) {
308 RCU_INIT_POINTER(data->ht[h1], s->next);
310 for (h2 = 0; h2 <= 16; h2++) {
311 struct rsvp_filter *f;
313 while ((f = rtnl_dereference(s->ht[h2])) != NULL) {
314 rcu_assign_pointer(s->ht[h2], f->next);
315 rsvp_delete_filter(tp, f);
318 kfree_rcu(s, rcu);
321 kfree_rcu(data, rcu);
324 static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
326 struct rsvp_head *head = rtnl_dereference(tp->root);
327 struct rsvp_filter *nfp, *f = (struct rsvp_filter *)arg;
328 struct rsvp_filter __rcu **fp;
329 unsigned int h = f->handle;
330 struct rsvp_session __rcu **sp;
331 struct rsvp_session *nsp, *s = f->sess;
332 int i;
334 fp = &s->ht[(h >> 8) & 0xFF];
335 for (nfp = rtnl_dereference(*fp); nfp;
336 fp = &nfp->next, nfp = rtnl_dereference(*fp)) {
337 if (nfp == f) {
338 RCU_INIT_POINTER(*fp, f->next);
339 rsvp_delete_filter(tp, f);
341 /* Strip tree */
343 for (i = 0; i <= 16; i++)
344 if (s->ht[i])
345 return 0;
347 /* OK, session has no flows */
348 sp = &head->ht[h & 0xFF];
349 for (nsp = rtnl_dereference(*sp); nsp;
350 sp = &nsp->next, nsp = rtnl_dereference(*sp)) {
351 if (nsp == s) {
352 RCU_INIT_POINTER(*sp, s->next);
353 kfree_rcu(s, rcu);
354 return 0;
358 return 0;
361 return 0;
364 static unsigned int gen_handle(struct tcf_proto *tp, unsigned salt)
366 struct rsvp_head *data = rtnl_dereference(tp->root);
367 int i = 0xFFFF;
369 while (i-- > 0) {
370 u32 h;
372 if ((data->hgenerator += 0x10000) == 0)
373 data->hgenerator = 0x10000;
374 h = data->hgenerator|salt;
375 if (rsvp_get(tp, h) == 0)
376 return h;
378 return 0;
381 static int tunnel_bts(struct rsvp_head *data)
383 int n = data->tgenerator >> 5;
384 u32 b = 1 << (data->tgenerator & 0x1F);
386 if (data->tmap[n] & b)
387 return 0;
388 data->tmap[n] |= b;
389 return 1;
392 static void tunnel_recycle(struct rsvp_head *data)
394 struct rsvp_session __rcu **sht = data->ht;
395 u32 tmap[256/32];
396 int h1, h2;
398 memset(tmap, 0, sizeof(tmap));
400 for (h1 = 0; h1 < 256; h1++) {
401 struct rsvp_session *s;
402 for (s = rtnl_dereference(sht[h1]); s;
403 s = rtnl_dereference(s->next)) {
404 for (h2 = 0; h2 <= 16; h2++) {
405 struct rsvp_filter *f;
407 for (f = rtnl_dereference(s->ht[h2]); f;
408 f = rtnl_dereference(f->next)) {
409 if (f->tunnelhdr == 0)
410 continue;
411 data->tgenerator = f->res.classid;
412 tunnel_bts(data);
418 memcpy(data->tmap, tmap, sizeof(tmap));
421 static u32 gen_tunnel(struct rsvp_head *data)
423 int i, k;
425 for (k = 0; k < 2; k++) {
426 for (i = 255; i > 0; i--) {
427 if (++data->tgenerator == 0)
428 data->tgenerator = 1;
429 if (tunnel_bts(data))
430 return data->tgenerator;
432 tunnel_recycle(data);
434 return 0;
437 static const struct nla_policy rsvp_policy[TCA_RSVP_MAX + 1] = {
438 [TCA_RSVP_CLASSID] = { .type = NLA_U32 },
439 [TCA_RSVP_DST] = { .type = NLA_BINARY,
440 .len = RSVP_DST_LEN * sizeof(u32) },
441 [TCA_RSVP_SRC] = { .type = NLA_BINARY,
442 .len = RSVP_DST_LEN * sizeof(u32) },
443 [TCA_RSVP_PINFO] = { .len = sizeof(struct tc_rsvp_pinfo) },
446 static int rsvp_change(struct net *net, struct sk_buff *in_skb,
447 struct tcf_proto *tp, unsigned long base,
448 u32 handle,
449 struct nlattr **tca,
450 unsigned long *arg, bool ovr)
452 struct rsvp_head *data = rtnl_dereference(tp->root);
453 struct rsvp_filter *f, *nfp;
454 struct rsvp_filter __rcu **fp;
455 struct rsvp_session *nsp, *s;
456 struct rsvp_session __rcu **sp;
457 struct tc_rsvp_pinfo *pinfo = NULL;
458 struct nlattr *opt = tca[TCA_OPTIONS];
459 struct nlattr *tb[TCA_RSVP_MAX + 1];
460 struct tcf_exts e;
461 unsigned int h1, h2;
462 __be32 *dst;
463 int err;
465 if (opt == NULL)
466 return handle ? -EINVAL : 0;
468 err = nla_parse_nested(tb, TCA_RSVP_MAX, opt, rsvp_policy);
469 if (err < 0)
470 return err;
472 tcf_exts_init(&e, TCA_RSVP_ACT, TCA_RSVP_POLICE);
473 err = tcf_exts_validate(net, tp, tb, tca[TCA_RATE], &e, ovr);
474 if (err < 0)
475 return err;
477 f = (struct rsvp_filter *)*arg;
478 if (f) {
479 /* Node exists: adjust only classid */
480 struct rsvp_filter *n;
482 if (f->handle != handle && handle)
483 goto errout2;
485 n = kmemdup(f, sizeof(*f), GFP_KERNEL);
486 if (!n) {
487 err = -ENOMEM;
488 goto errout2;
491 tcf_exts_init(&n->exts, TCA_RSVP_ACT, TCA_RSVP_POLICE);
493 if (tb[TCA_RSVP_CLASSID]) {
494 n->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID]);
495 tcf_bind_filter(tp, &n->res, base);
498 tcf_exts_change(tp, &n->exts, &e);
499 rsvp_replace(tp, n, handle);
500 return 0;
503 /* Now more serious part... */
504 err = -EINVAL;
505 if (handle)
506 goto errout2;
507 if (tb[TCA_RSVP_DST] == NULL)
508 goto errout2;
510 err = -ENOBUFS;
511 f = kzalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
512 if (f == NULL)
513 goto errout2;
515 tcf_exts_init(&f->exts, TCA_RSVP_ACT, TCA_RSVP_POLICE);
516 h2 = 16;
517 if (tb[TCA_RSVP_SRC]) {
518 memcpy(f->src, nla_data(tb[TCA_RSVP_SRC]), sizeof(f->src));
519 h2 = hash_src(f->src);
521 if (tb[TCA_RSVP_PINFO]) {
522 pinfo = nla_data(tb[TCA_RSVP_PINFO]);
523 f->spi = pinfo->spi;
524 f->tunnelhdr = pinfo->tunnelhdr;
526 if (tb[TCA_RSVP_CLASSID])
527 f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID]);
529 dst = nla_data(tb[TCA_RSVP_DST]);
530 h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
532 err = -ENOMEM;
533 if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
534 goto errout;
536 if (f->tunnelhdr) {
537 err = -EINVAL;
538 if (f->res.classid > 255)
539 goto errout;
541 err = -ENOMEM;
542 if (f->res.classid == 0 &&
543 (f->res.classid = gen_tunnel(data)) == 0)
544 goto errout;
547 for (sp = &data->ht[h1];
548 (s = rtnl_dereference(*sp)) != NULL;
549 sp = &s->next) {
550 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
551 pinfo && pinfo->protocol == s->protocol &&
552 memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0 &&
553 #if RSVP_DST_LEN == 4
554 dst[0] == s->dst[0] &&
555 dst[1] == s->dst[1] &&
556 dst[2] == s->dst[2] &&
557 #endif
558 pinfo->tunnelid == s->tunnelid) {
560 insert:
561 /* OK, we found appropriate session */
563 fp = &s->ht[h2];
565 f->sess = s;
566 if (f->tunnelhdr == 0)
567 tcf_bind_filter(tp, &f->res, base);
569 tcf_exts_change(tp, &f->exts, &e);
571 fp = &s->ht[h2];
572 for (nfp = rtnl_dereference(*fp); nfp;
573 fp = &nfp->next, nfp = rtnl_dereference(*fp)) {
574 __u32 mask = nfp->spi.mask & f->spi.mask;
576 if (mask != f->spi.mask)
577 break;
579 RCU_INIT_POINTER(f->next, nfp);
580 rcu_assign_pointer(*fp, f);
582 *arg = (unsigned long)f;
583 return 0;
587 /* No session found. Create new one. */
589 err = -ENOBUFS;
590 s = kzalloc(sizeof(struct rsvp_session), GFP_KERNEL);
591 if (s == NULL)
592 goto errout;
593 memcpy(s->dst, dst, sizeof(s->dst));
595 if (pinfo) {
596 s->dpi = pinfo->dpi;
597 s->protocol = pinfo->protocol;
598 s->tunnelid = pinfo->tunnelid;
600 sp = &data->ht[h1];
601 for (nsp = rtnl_dereference(*sp); nsp;
602 sp = &nsp->next, nsp = rtnl_dereference(*sp)) {
603 if ((nsp->dpi.mask & s->dpi.mask) != s->dpi.mask)
604 break;
606 RCU_INIT_POINTER(s->next, nsp);
607 rcu_assign_pointer(*sp, s);
609 goto insert;
611 errout:
612 kfree(f);
613 errout2:
614 tcf_exts_destroy(&e);
615 return err;
618 static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
620 struct rsvp_head *head = rtnl_dereference(tp->root);
621 unsigned int h, h1;
623 if (arg->stop)
624 return;
626 for (h = 0; h < 256; h++) {
627 struct rsvp_session *s;
629 for (s = rtnl_dereference(head->ht[h]); s;
630 s = rtnl_dereference(s->next)) {
631 for (h1 = 0; h1 <= 16; h1++) {
632 struct rsvp_filter *f;
634 for (f = rtnl_dereference(s->ht[h1]); f;
635 f = rtnl_dereference(f->next)) {
636 if (arg->count < arg->skip) {
637 arg->count++;
638 continue;
640 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
641 arg->stop = 1;
642 return;
644 arg->count++;
651 static int rsvp_dump(struct net *net, struct tcf_proto *tp, unsigned long fh,
652 struct sk_buff *skb, struct tcmsg *t)
654 struct rsvp_filter *f = (struct rsvp_filter *)fh;
655 struct rsvp_session *s;
656 struct nlattr *nest;
657 struct tc_rsvp_pinfo pinfo;
659 if (f == NULL)
660 return skb->len;
661 s = f->sess;
663 t->tcm_handle = f->handle;
665 nest = nla_nest_start(skb, TCA_OPTIONS);
666 if (nest == NULL)
667 goto nla_put_failure;
669 if (nla_put(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst))
670 goto nla_put_failure;
671 pinfo.dpi = s->dpi;
672 pinfo.spi = f->spi;
673 pinfo.protocol = s->protocol;
674 pinfo.tunnelid = s->tunnelid;
675 pinfo.tunnelhdr = f->tunnelhdr;
676 pinfo.pad = 0;
677 if (nla_put(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo))
678 goto nla_put_failure;
679 if (f->res.classid &&
680 nla_put_u32(skb, TCA_RSVP_CLASSID, f->res.classid))
681 goto nla_put_failure;
682 if (((f->handle >> 8) & 0xFF) != 16 &&
683 nla_put(skb, TCA_RSVP_SRC, sizeof(f->src), f->src))
684 goto nla_put_failure;
686 if (tcf_exts_dump(skb, &f->exts) < 0)
687 goto nla_put_failure;
689 nla_nest_end(skb, nest);
691 if (tcf_exts_dump_stats(skb, &f->exts) < 0)
692 goto nla_put_failure;
693 return skb->len;
695 nla_put_failure:
696 nla_nest_cancel(skb, nest);
697 return -1;
700 static struct tcf_proto_ops RSVP_OPS __read_mostly = {
701 .kind = RSVP_ID,
702 .classify = rsvp_classify,
703 .init = rsvp_init,
704 .destroy = rsvp_destroy,
705 .get = rsvp_get,
706 .change = rsvp_change,
707 .delete = rsvp_delete,
708 .walk = rsvp_walk,
709 .dump = rsvp_dump,
710 .owner = THIS_MODULE,
713 static int __init init_rsvp(void)
715 return register_tcf_proto_ops(&RSVP_OPS);
718 static void __exit exit_rsvp(void)
720 unregister_tcf_proto_ops(&RSVP_OPS);
723 module_init(init_rsvp)
724 module_exit(exit_rsvp)