mtd: dc21285: use raw spinlock functions for nw_gpio_lock
[linux/fpc-iii.git] / net / sched / cls_rsvp.h
blob02fa82792dab8334d1dc14408f7ed42a4db0c141
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 bool rsvp_destroy(struct tcf_proto *tp, bool force)
296 struct rsvp_head *data = rtnl_dereference(tp->root);
297 int h1, h2;
299 if (data == NULL)
300 return true;
302 if (!force) {
303 for (h1 = 0; h1 < 256; h1++) {
304 if (rcu_access_pointer(data->ht[h1]))
305 return false;
309 RCU_INIT_POINTER(tp->root, NULL);
311 for (h1 = 0; h1 < 256; h1++) {
312 struct rsvp_session *s;
314 while ((s = rtnl_dereference(data->ht[h1])) != NULL) {
315 RCU_INIT_POINTER(data->ht[h1], s->next);
317 for (h2 = 0; h2 <= 16; h2++) {
318 struct rsvp_filter *f;
320 while ((f = rtnl_dereference(s->ht[h2])) != NULL) {
321 rcu_assign_pointer(s->ht[h2], f->next);
322 rsvp_delete_filter(tp, f);
325 kfree_rcu(s, rcu);
328 kfree_rcu(data, rcu);
329 return true;
332 static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
334 struct rsvp_head *head = rtnl_dereference(tp->root);
335 struct rsvp_filter *nfp, *f = (struct rsvp_filter *)arg;
336 struct rsvp_filter __rcu **fp;
337 unsigned int h = f->handle;
338 struct rsvp_session __rcu **sp;
339 struct rsvp_session *nsp, *s = f->sess;
340 int i;
342 fp = &s->ht[(h >> 8) & 0xFF];
343 for (nfp = rtnl_dereference(*fp); nfp;
344 fp = &nfp->next, nfp = rtnl_dereference(*fp)) {
345 if (nfp == f) {
346 RCU_INIT_POINTER(*fp, f->next);
347 rsvp_delete_filter(tp, f);
349 /* Strip tree */
351 for (i = 0; i <= 16; i++)
352 if (s->ht[i])
353 return 0;
355 /* OK, session has no flows */
356 sp = &head->ht[h & 0xFF];
357 for (nsp = rtnl_dereference(*sp); nsp;
358 sp = &nsp->next, nsp = rtnl_dereference(*sp)) {
359 if (nsp == s) {
360 RCU_INIT_POINTER(*sp, s->next);
361 kfree_rcu(s, rcu);
362 return 0;
366 return 0;
369 return 0;
372 static unsigned int gen_handle(struct tcf_proto *tp, unsigned salt)
374 struct rsvp_head *data = rtnl_dereference(tp->root);
375 int i = 0xFFFF;
377 while (i-- > 0) {
378 u32 h;
380 if ((data->hgenerator += 0x10000) == 0)
381 data->hgenerator = 0x10000;
382 h = data->hgenerator|salt;
383 if (rsvp_get(tp, h) == 0)
384 return h;
386 return 0;
389 static int tunnel_bts(struct rsvp_head *data)
391 int n = data->tgenerator >> 5;
392 u32 b = 1 << (data->tgenerator & 0x1F);
394 if (data->tmap[n] & b)
395 return 0;
396 data->tmap[n] |= b;
397 return 1;
400 static void tunnel_recycle(struct rsvp_head *data)
402 struct rsvp_session __rcu **sht = data->ht;
403 u32 tmap[256/32];
404 int h1, h2;
406 memset(tmap, 0, sizeof(tmap));
408 for (h1 = 0; h1 < 256; h1++) {
409 struct rsvp_session *s;
410 for (s = rtnl_dereference(sht[h1]); s;
411 s = rtnl_dereference(s->next)) {
412 for (h2 = 0; h2 <= 16; h2++) {
413 struct rsvp_filter *f;
415 for (f = rtnl_dereference(s->ht[h2]); f;
416 f = rtnl_dereference(f->next)) {
417 if (f->tunnelhdr == 0)
418 continue;
419 data->tgenerator = f->res.classid;
420 tunnel_bts(data);
426 memcpy(data->tmap, tmap, sizeof(tmap));
429 static u32 gen_tunnel(struct rsvp_head *data)
431 int i, k;
433 for (k = 0; k < 2; k++) {
434 for (i = 255; i > 0; i--) {
435 if (++data->tgenerator == 0)
436 data->tgenerator = 1;
437 if (tunnel_bts(data))
438 return data->tgenerator;
440 tunnel_recycle(data);
442 return 0;
445 static const struct nla_policy rsvp_policy[TCA_RSVP_MAX + 1] = {
446 [TCA_RSVP_CLASSID] = { .type = NLA_U32 },
447 [TCA_RSVP_DST] = { .type = NLA_BINARY,
448 .len = RSVP_DST_LEN * sizeof(u32) },
449 [TCA_RSVP_SRC] = { .type = NLA_BINARY,
450 .len = RSVP_DST_LEN * sizeof(u32) },
451 [TCA_RSVP_PINFO] = { .len = sizeof(struct tc_rsvp_pinfo) },
454 static int rsvp_change(struct net *net, struct sk_buff *in_skb,
455 struct tcf_proto *tp, unsigned long base,
456 u32 handle,
457 struct nlattr **tca,
458 unsigned long *arg, bool ovr)
460 struct rsvp_head *data = rtnl_dereference(tp->root);
461 struct rsvp_filter *f, *nfp;
462 struct rsvp_filter __rcu **fp;
463 struct rsvp_session *nsp, *s;
464 struct rsvp_session __rcu **sp;
465 struct tc_rsvp_pinfo *pinfo = NULL;
466 struct nlattr *opt = tca[TCA_OPTIONS];
467 struct nlattr *tb[TCA_RSVP_MAX + 1];
468 struct tcf_exts e;
469 unsigned int h1, h2;
470 __be32 *dst;
471 int err;
473 if (opt == NULL)
474 return handle ? -EINVAL : 0;
476 err = nla_parse_nested(tb, TCA_RSVP_MAX, opt, rsvp_policy);
477 if (err < 0)
478 return err;
480 tcf_exts_init(&e, TCA_RSVP_ACT, TCA_RSVP_POLICE);
481 err = tcf_exts_validate(net, tp, tb, tca[TCA_RATE], &e, ovr);
482 if (err < 0)
483 return err;
485 f = (struct rsvp_filter *)*arg;
486 if (f) {
487 /* Node exists: adjust only classid */
488 struct rsvp_filter *n;
490 if (f->handle != handle && handle)
491 goto errout2;
493 n = kmemdup(f, sizeof(*f), GFP_KERNEL);
494 if (!n) {
495 err = -ENOMEM;
496 goto errout2;
499 tcf_exts_init(&n->exts, TCA_RSVP_ACT, TCA_RSVP_POLICE);
501 if (tb[TCA_RSVP_CLASSID]) {
502 n->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID]);
503 tcf_bind_filter(tp, &n->res, base);
506 tcf_exts_change(tp, &n->exts, &e);
507 rsvp_replace(tp, n, handle);
508 return 0;
511 /* Now more serious part... */
512 err = -EINVAL;
513 if (handle)
514 goto errout2;
515 if (tb[TCA_RSVP_DST] == NULL)
516 goto errout2;
518 err = -ENOBUFS;
519 f = kzalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
520 if (f == NULL)
521 goto errout2;
523 tcf_exts_init(&f->exts, TCA_RSVP_ACT, TCA_RSVP_POLICE);
524 h2 = 16;
525 if (tb[TCA_RSVP_SRC]) {
526 memcpy(f->src, nla_data(tb[TCA_RSVP_SRC]), sizeof(f->src));
527 h2 = hash_src(f->src);
529 if (tb[TCA_RSVP_PINFO]) {
530 pinfo = nla_data(tb[TCA_RSVP_PINFO]);
531 f->spi = pinfo->spi;
532 f->tunnelhdr = pinfo->tunnelhdr;
534 if (tb[TCA_RSVP_CLASSID])
535 f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID]);
537 dst = nla_data(tb[TCA_RSVP_DST]);
538 h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
540 err = -ENOMEM;
541 if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
542 goto errout;
544 if (f->tunnelhdr) {
545 err = -EINVAL;
546 if (f->res.classid > 255)
547 goto errout;
549 err = -ENOMEM;
550 if (f->res.classid == 0 &&
551 (f->res.classid = gen_tunnel(data)) == 0)
552 goto errout;
555 for (sp = &data->ht[h1];
556 (s = rtnl_dereference(*sp)) != NULL;
557 sp = &s->next) {
558 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
559 pinfo && pinfo->protocol == s->protocol &&
560 memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0 &&
561 #if RSVP_DST_LEN == 4
562 dst[0] == s->dst[0] &&
563 dst[1] == s->dst[1] &&
564 dst[2] == s->dst[2] &&
565 #endif
566 pinfo->tunnelid == s->tunnelid) {
568 insert:
569 /* OK, we found appropriate session */
571 fp = &s->ht[h2];
573 f->sess = s;
574 if (f->tunnelhdr == 0)
575 tcf_bind_filter(tp, &f->res, base);
577 tcf_exts_change(tp, &f->exts, &e);
579 fp = &s->ht[h2];
580 for (nfp = rtnl_dereference(*fp); nfp;
581 fp = &nfp->next, nfp = rtnl_dereference(*fp)) {
582 __u32 mask = nfp->spi.mask & f->spi.mask;
584 if (mask != f->spi.mask)
585 break;
587 RCU_INIT_POINTER(f->next, nfp);
588 rcu_assign_pointer(*fp, f);
590 *arg = (unsigned long)f;
591 return 0;
595 /* No session found. Create new one. */
597 err = -ENOBUFS;
598 s = kzalloc(sizeof(struct rsvp_session), GFP_KERNEL);
599 if (s == NULL)
600 goto errout;
601 memcpy(s->dst, dst, sizeof(s->dst));
603 if (pinfo) {
604 s->dpi = pinfo->dpi;
605 s->protocol = pinfo->protocol;
606 s->tunnelid = pinfo->tunnelid;
608 sp = &data->ht[h1];
609 for (nsp = rtnl_dereference(*sp); nsp;
610 sp = &nsp->next, nsp = rtnl_dereference(*sp)) {
611 if ((nsp->dpi.mask & s->dpi.mask) != s->dpi.mask)
612 break;
614 RCU_INIT_POINTER(s->next, nsp);
615 rcu_assign_pointer(*sp, s);
617 goto insert;
619 errout:
620 kfree(f);
621 errout2:
622 tcf_exts_destroy(&e);
623 return err;
626 static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
628 struct rsvp_head *head = rtnl_dereference(tp->root);
629 unsigned int h, h1;
631 if (arg->stop)
632 return;
634 for (h = 0; h < 256; h++) {
635 struct rsvp_session *s;
637 for (s = rtnl_dereference(head->ht[h]); s;
638 s = rtnl_dereference(s->next)) {
639 for (h1 = 0; h1 <= 16; h1++) {
640 struct rsvp_filter *f;
642 for (f = rtnl_dereference(s->ht[h1]); f;
643 f = rtnl_dereference(f->next)) {
644 if (arg->count < arg->skip) {
645 arg->count++;
646 continue;
648 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
649 arg->stop = 1;
650 return;
652 arg->count++;
659 static int rsvp_dump(struct net *net, struct tcf_proto *tp, unsigned long fh,
660 struct sk_buff *skb, struct tcmsg *t)
662 struct rsvp_filter *f = (struct rsvp_filter *)fh;
663 struct rsvp_session *s;
664 struct nlattr *nest;
665 struct tc_rsvp_pinfo pinfo;
667 if (f == NULL)
668 return skb->len;
669 s = f->sess;
671 t->tcm_handle = f->handle;
673 nest = nla_nest_start(skb, TCA_OPTIONS);
674 if (nest == NULL)
675 goto nla_put_failure;
677 if (nla_put(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst))
678 goto nla_put_failure;
679 pinfo.dpi = s->dpi;
680 pinfo.spi = f->spi;
681 pinfo.protocol = s->protocol;
682 pinfo.tunnelid = s->tunnelid;
683 pinfo.tunnelhdr = f->tunnelhdr;
684 pinfo.pad = 0;
685 if (nla_put(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo))
686 goto nla_put_failure;
687 if (f->res.classid &&
688 nla_put_u32(skb, TCA_RSVP_CLASSID, f->res.classid))
689 goto nla_put_failure;
690 if (((f->handle >> 8) & 0xFF) != 16 &&
691 nla_put(skb, TCA_RSVP_SRC, sizeof(f->src), f->src))
692 goto nla_put_failure;
694 if (tcf_exts_dump(skb, &f->exts) < 0)
695 goto nla_put_failure;
697 nla_nest_end(skb, nest);
699 if (tcf_exts_dump_stats(skb, &f->exts) < 0)
700 goto nla_put_failure;
701 return skb->len;
703 nla_put_failure:
704 nla_nest_cancel(skb, nest);
705 return -1;
708 static struct tcf_proto_ops RSVP_OPS __read_mostly = {
709 .kind = RSVP_ID,
710 .classify = rsvp_classify,
711 .init = rsvp_init,
712 .destroy = rsvp_destroy,
713 .get = rsvp_get,
714 .change = rsvp_change,
715 .delete = rsvp_delete,
716 .walk = rsvp_walk,
717 .dump = rsvp_dump,
718 .owner = THIS_MODULE,
721 static int __init init_rsvp(void)
723 return register_tcf_proto_ops(&RSVP_OPS);
726 static void __exit exit_rsvp(void)
728 unregister_tcf_proto_ops(&RSVP_OPS);
731 module_init(init_rsvp)
732 module_exit(exit_rsvp)