projects / deliverable / linux.git / blob
? search:


1c64a09753c448969b3c1cbec418f03a909b8e95
[deliverable/linux.git] / net / sched / cls_rsvp.h
1 /*
2 * net/sched/cls_rsvp.h Template file for RSVPv[46] classifiers.
3 *
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.
8 *
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
10 */
11
12 /*
13 Comparing to general packet classification problem,
14 RSVP needs only sevaral relatively simple rules:
15
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.
21
22 IMPLEMENTATION.
23
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).
28
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).
34
35
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.
38
39
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.
44
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.
48
49
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.
57
58
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)
63
64
65 Well, as result, despite its simplicity, we get a pretty
66 powerful classification engine. */
67
68
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;
75 };
76
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;
86 };
87
88
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;
94
95 struct tcf_result res;
96 struct tcf_exts exts;
97
98 u32 handle;
99 struct rsvp_session *sess;
100 struct rcu_head rcu;
101 };
102
103 static inline unsigned int hash_dst(__be32 *dst, u8 protocol, u8 tunnelid)
104 {
105 unsigned int h = (__force __u32)dst[RSVP_DST_LEN - 1];
106
107 h ^= h>>16;
108 h ^= h>>8;
109 return (h ^ protocol ^ tunnelid) & 0xFF;
110 }
111
112 static inline unsigned int hash_src(__be32 *src)
113 {
114 unsigned int h = (__force __u32)src[RSVP_DST_LEN-1];
115
116 h ^= h>>16;
117 h ^= h>>8;
118 h ^= h>>4;
119 return h & 0xF;
120 }
121
122 #define RSVP_APPLY_RESULT() \
123 { \
124 int r = tcf_exts_exec(skb, &f->exts, res); \
125 if (r < 0) \
126 continue; \
127 else if (r > 0) \
128 return r; \
129 }
130
131 static int rsvp_classify(struct sk_buff *skb, const struct tcf_proto *tp,
132 struct tcf_result *res)
133 {
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;
144
145 if (!pskb_network_may_pull(skb, sizeof(*nhptr)))
146 return -1;
147 nhptr = ipv6_hdr(skb);
148 #else
149 struct iphdr *nhptr;
150
151 if (!pskb_network_may_pull(skb, sizeof(*nhptr)))
152 return -1;
153 nhptr = ip_hdr(skb);
154 #endif
155
156 restart:
157
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
171
172 h1 = hash_dst(dst, protocol, tunnelid);
173 h2 = hash_src(src);
174
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) {
187
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
193 &&
194 src[0] == f->src[0] &&
195 src[1] == f->src[1] &&
196 src[2] == f->src[2]
197 #endif
198 ) {
199 *res = f->res;
200 RSVP_APPLY_RESULT();
201
202 matched:
203 if (f->tunnelhdr == 0)
204 return 0;
205
206 tunnelid = f->res.classid;
207 nhptr = (void *)(xprt + f->tunnelhdr - sizeof(*nhptr));
208 goto restart;
209 }
210 }
211
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;
218 }
219 return -1;
220 }
221 }
222 return -1;
223 }
224
225 static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
226 {
227 struct rsvp_head *head = rtnl_dereference(tp->root);
228 struct rsvp_session *s;
229 struct rsvp_filter *f;
230 unsigned int h1 = handle & 0xFF;
231 unsigned int h2 = (handle >> 8) & 0xFF;
232
233 if (h2 > 16)
234 return 0;
235
236 for (s = rtnl_dereference(head->ht[h1]); s;
237 s = rtnl_dereference(s->next)) {
238 for (f = rtnl_dereference(s->ht[h2]); f;
239 f = rtnl_dereference(f->next)) {
240 if (f->handle == handle)
241 return (unsigned long)f;
242 }
243 }
244 return 0;
245 }
246
247 static void rsvp_put(struct tcf_proto *tp, unsigned long f)
248 {
249 }
250
251 static int rsvp_init(struct tcf_proto *tp)
252 {
253 struct rsvp_head *data;
254
255 data = kzalloc(sizeof(struct rsvp_head), GFP_KERNEL);
256 if (data) {
257 rcu_assign_pointer(tp->root, data);
258 return 0;
259 }
260 return -ENOBUFS;
261 }
262
263 static void
264 rsvp_delete_filter(struct tcf_proto *tp, struct rsvp_filter *f)
265 {
266 tcf_unbind_filter(tp, &f->res);
267 tcf_exts_destroy(&f->exts);
268 kfree_rcu(f, rcu);
269 }
270
271 static void rsvp_destroy(struct tcf_proto *tp)
272 {
273 struct rsvp_head *data = rtnl_dereference(tp->root);
274 int h1, h2;
275
276 if (data == NULL)
277 return;
278
279 RCU_INIT_POINTER(tp->root, NULL);
280
281 for (h1 = 0; h1 < 256; h1++) {
282 struct rsvp_session *s;
283
284 while ((s = rtnl_dereference(data->ht[h1])) != NULL) {
285 RCU_INIT_POINTER(data->ht[h1], s->next);
286
287 for (h2 = 0; h2 <= 16; h2++) {
288 struct rsvp_filter *f;
289
290 while ((f = rtnl_dereference(s->ht[h2])) != NULL) {
291 rcu_assign_pointer(s->ht[h2], f->next);
292 rsvp_delete_filter(tp, f);
293 }
294 }
295 kfree_rcu(s, rcu);
296 }
297 }
298 kfree_rcu(data, rcu);
299 }
300
301 static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
302 {
303 struct rsvp_head *head = rtnl_dereference(tp->root);
304 struct rsvp_filter *nfp, *f = (struct rsvp_filter *)arg;
305 struct rsvp_filter __rcu **fp;
306 unsigned int h = f->handle;
307 struct rsvp_session __rcu **sp;
308 struct rsvp_session *nsp, *s = f->sess;
309 int i;
310
311 fp = &s->ht[(h >> 8) & 0xFF];
312 for (nfp = rtnl_dereference(*fp); nfp;
313 fp = &nfp->next, nfp = rtnl_dereference(*fp)) {
314 if (nfp == f) {
315 RCU_INIT_POINTER(*fp, f->next);
316 rsvp_delete_filter(tp, f);
317
318 /* Strip tree */
319
320 for (i = 0; i <= 16; i++)
321 if (s->ht[i])
322 return 0;
323
324 /* OK, session has no flows */
325 sp = &head->ht[h & 0xFF];
326 for (nsp = rtnl_dereference(*sp); nsp;
327 sp = &nsp->next, nsp = rtnl_dereference(*sp)) {
328 if (nsp == s) {
329 RCU_INIT_POINTER(*sp, s->next);
330 kfree_rcu(s, rcu);
331 return 0;
332 }
333 }
334
335 return 0;
336 }
337 }
338 return 0;
339 }
340
341 static unsigned int gen_handle(struct tcf_proto *tp, unsigned salt)
342 {
343 struct rsvp_head *data = rtnl_dereference(tp->root);
344 int i = 0xFFFF;
345
346 while (i-- > 0) {
347 u32 h;
348
349 if ((data->hgenerator += 0x10000) == 0)
350 data->hgenerator = 0x10000;
351 h = data->hgenerator|salt;
352 if (rsvp_get(tp, h) == 0)
353 return h;
354 }
355 return 0;
356 }
357
358 static int tunnel_bts(struct rsvp_head *data)
359 {
360 int n = data->tgenerator >> 5;
361 u32 b = 1 << (data->tgenerator & 0x1F);
362
363 if (data->tmap[n] & b)
364 return 0;
365 data->tmap[n] |= b;
366 return 1;
367 }
368
369 static void tunnel_recycle(struct rsvp_head *data)
370 {
371 struct rsvp_session __rcu **sht = data->ht;
372 u32 tmap[256/32];
373 int h1, h2;
374
375 memset(tmap, 0, sizeof(tmap));
376
377 for (h1 = 0; h1 < 256; h1++) {
378 struct rsvp_session *s;
379 for (s = rtnl_dereference(sht[h1]); s;
380 s = rtnl_dereference(s->next)) {
381 for (h2 = 0; h2 <= 16; h2++) {
382 struct rsvp_filter *f;
383
384 for (f = rtnl_dereference(s->ht[h2]); f;
385 f = rtnl_dereference(f->next)) {
386 if (f->tunnelhdr == 0)
387 continue;
388 data->tgenerator = f->res.classid;
389 tunnel_bts(data);
390 }
391 }
392 }
393 }
394
395 memcpy(data->tmap, tmap, sizeof(tmap));
396 }
397
398 static u32 gen_tunnel(struct rsvp_head *data)
399 {
400 int i, k;
401
402 for (k = 0; k < 2; k++) {
403 for (i = 255; i > 0; i--) {
404 if (++data->tgenerator == 0)
405 data->tgenerator = 1;
406 if (tunnel_bts(data))
407 return data->tgenerator;
408 }
409 tunnel_recycle(data);
410 }
411 return 0;
412 }
413
414 static const struct nla_policy rsvp_policy[TCA_RSVP_MAX + 1] = {
415 [TCA_RSVP_CLASSID] = { .type = NLA_U32 },
416 [TCA_RSVP_DST] = { .type = NLA_BINARY,
417 .len = RSVP_DST_LEN * sizeof(u32) },
418 [TCA_RSVP_SRC] = { .type = NLA_BINARY,
419 .len = RSVP_DST_LEN * sizeof(u32) },
420 [TCA_RSVP_PINFO] = { .len = sizeof(struct tc_rsvp_pinfo) },
421 };
422
423 static int rsvp_change(struct net *net, struct sk_buff *in_skb,
424 struct tcf_proto *tp, unsigned long base,
425 u32 handle,
426 struct nlattr **tca,
427 unsigned long *arg, bool ovr)
428 {
429 struct rsvp_head *data = rtnl_dereference(tp->root);
430 struct rsvp_filter *f, *nfp;
431 struct rsvp_filter __rcu **fp;
432 struct rsvp_session *nsp, *s;
433 struct rsvp_session __rcu **sp;
434 struct tc_rsvp_pinfo *pinfo = NULL;
435 struct nlattr *opt = tca[TCA_OPTIONS];
436 struct nlattr *tb[TCA_RSVP_MAX + 1];
437 struct tcf_exts e;
438 unsigned int h1, h2;
439 __be32 *dst;
440 int err;
441
442 if (opt == NULL)
443 return handle ? -EINVAL : 0;
444
445 err = nla_parse_nested(tb, TCA_RSVP_MAX, opt, rsvp_policy);
446 if (err < 0)
447 return err;
448
449 tcf_exts_init(&e, TCA_RSVP_ACT, TCA_RSVP_POLICE);
450 err = tcf_exts_validate(net, tp, tb, tca[TCA_RATE], &e, ovr);
451 if (err < 0)
452 return err;
453
454 f = (struct rsvp_filter *)*arg;
455 if (f) {
456 /* Node exists: adjust only classid */
457
458 if (f->handle != handle && handle)
459 goto errout2;
460 if (tb[TCA_RSVP_CLASSID]) {
461 f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID]);
462 tcf_bind_filter(tp, &f->res, base);
463 }
464
465 tcf_exts_change(tp, &f->exts, &e);
466 return 0;
467 }
468
469 /* Now more serious part... */
470 err = -EINVAL;
471 if (handle)
472 goto errout2;
473 if (tb[TCA_RSVP_DST] == NULL)
474 goto errout2;
475
476 err = -ENOBUFS;
477 f = kzalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
478 if (f == NULL)
479 goto errout2;
480
481 tcf_exts_init(&f->exts, TCA_RSVP_ACT, TCA_RSVP_POLICE);
482 h2 = 16;
483 if (tb[TCA_RSVP_SRC]) {
484 memcpy(f->src, nla_data(tb[TCA_RSVP_SRC]), sizeof(f->src));
485 h2 = hash_src(f->src);
486 }
487 if (tb[TCA_RSVP_PINFO]) {
488 pinfo = nla_data(tb[TCA_RSVP_PINFO]);
489 f->spi = pinfo->spi;
490 f->tunnelhdr = pinfo->tunnelhdr;
491 }
492 if (tb[TCA_RSVP_CLASSID])
493 f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID]);
494
495 dst = nla_data(tb[TCA_RSVP_DST]);
496 h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
497
498 err = -ENOMEM;
499 if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
500 goto errout;
501
502 if (f->tunnelhdr) {
503 err = -EINVAL;
504 if (f->res.classid > 255)
505 goto errout;
506
507 err = -ENOMEM;
508 if (f->res.classid == 0 &&
509 (f->res.classid = gen_tunnel(data)) == 0)
510 goto errout;
511 }
512
513 for (sp = &data->ht[h1];
514 (s = rtnl_dereference(*sp)) != NULL;
515 sp = &s->next) {
516 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
517 pinfo && pinfo->protocol == s->protocol &&
518 memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0 &&
519 #if RSVP_DST_LEN == 4
520 dst[0] == s->dst[0] &&
521 dst[1] == s->dst[1] &&
522 dst[2] == s->dst[2] &&
523 #endif
524 pinfo->tunnelid == s->tunnelid) {
525
526 insert:
527 /* OK, we found appropriate session */
528
529 fp = &s->ht[h2];
530
531 f->sess = s;
532 if (f->tunnelhdr == 0)
533 tcf_bind_filter(tp, &f->res, base);
534
535 tcf_exts_change(tp, &f->exts, &e);
536
537 fp = &s->ht[h2];
538 for (nfp = rtnl_dereference(*fp); nfp;
539 fp = &nfp->next, nfp = rtnl_dereference(*fp)) {
540 __u32 mask = nfp->spi.mask & f->spi.mask;
541
542 if (mask != f->spi.mask)
543 break;
544 }
545 RCU_INIT_POINTER(f->next, nfp);
546 rcu_assign_pointer(*fp, f);
547
548 *arg = (unsigned long)f;
549 return 0;
550 }
551 }
552
553 /* No session found. Create new one. */
554
555 err = -ENOBUFS;
556 s = kzalloc(sizeof(struct rsvp_session), GFP_KERNEL);
557 if (s == NULL)
558 goto errout;
559 memcpy(s->dst, dst, sizeof(s->dst));
560
561 if (pinfo) {
562 s->dpi = pinfo->dpi;
563 s->protocol = pinfo->protocol;
564 s->tunnelid = pinfo->tunnelid;
565 }
566 sp = &data->ht[h1];
567 for (nsp = rtnl_dereference(*sp); nsp;
568 sp = &nsp->next, nsp = rtnl_dereference(*sp)) {
569 if ((nsp->dpi.mask & s->dpi.mask) != s->dpi.mask)
570 break;
571 }
572 RCU_INIT_POINTER(s->next, nsp);
573 rcu_assign_pointer(*sp, s);
574
575 goto insert;
576
577 errout:
578 kfree(f);
579 errout2:
580 tcf_exts_destroy(&e);
581 return err;
582 }
583
584 static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
585 {
586 struct rsvp_head *head = rtnl_dereference(tp->root);
587 unsigned int h, h1;
588
589 if (arg->stop)
590 return;
591
592 for (h = 0; h < 256; h++) {
593 struct rsvp_session *s;
594
595 for (s = rtnl_dereference(head->ht[h]); s;
596 s = rtnl_dereference(s->next)) {
597 for (h1 = 0; h1 <= 16; h1++) {
598 struct rsvp_filter *f;
599
600 for (f = rtnl_dereference(s->ht[h1]); f;
601 f = rtnl_dereference(f->next)) {
602 if (arg->count < arg->skip) {
603 arg->count++;
604 continue;
605 }
606 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
607 arg->stop = 1;
608 return;
609 }
610 arg->count++;
611 }
612 }
613 }
614 }
615 }
616
617 static int rsvp_dump(struct net *net, struct tcf_proto *tp, unsigned long fh,
618 struct sk_buff *skb, struct tcmsg *t)
619 {
620 struct rsvp_filter *f = (struct rsvp_filter *)fh;
621 struct rsvp_session *s;
622 unsigned char *b = skb_tail_pointer(skb);
623 struct nlattr *nest;
624 struct tc_rsvp_pinfo pinfo;
625
626 if (f == NULL)
627 return skb->len;
628 s = f->sess;
629
630 t->tcm_handle = f->handle;
631
632 nest = nla_nest_start(skb, TCA_OPTIONS);
633 if (nest == NULL)
634 goto nla_put_failure;
635
636 if (nla_put(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst))
637 goto nla_put_failure;
638 pinfo.dpi = s->dpi;
639 pinfo.spi = f->spi;
640 pinfo.protocol = s->protocol;
641 pinfo.tunnelid = s->tunnelid;
642 pinfo.tunnelhdr = f->tunnelhdr;
643 pinfo.pad = 0;
644 if (nla_put(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo))
645 goto nla_put_failure;
646 if (f->res.classid &&
647 nla_put_u32(skb, TCA_RSVP_CLASSID, f->res.classid))
648 goto nla_put_failure;
649 if (((f->handle >> 8) & 0xFF) != 16 &&
650 nla_put(skb, TCA_RSVP_SRC, sizeof(f->src), f->src))
651 goto nla_put_failure;
652
653 if (tcf_exts_dump(skb, &f->exts) < 0)
654 goto nla_put_failure;
655
656 nla_nest_end(skb, nest);
657
658 if (tcf_exts_dump_stats(skb, &f->exts) < 0)
659 goto nla_put_failure;
660 return skb->len;
661
662 nla_put_failure:
663 nlmsg_trim(skb, b);
664 return -1;
665 }
666
667 static struct tcf_proto_ops RSVP_OPS __read_mostly = {
668 .kind = RSVP_ID,
669 .classify = rsvp_classify,
670 .init = rsvp_init,
671 .destroy = rsvp_destroy,
672 .get = rsvp_get,
673 .put = rsvp_put,
674 .change = rsvp_change,
675 .delete = rsvp_delete,
676 .walk = rsvp_walk,
677 .dump = rsvp_dump,
678 .owner = THIS_MODULE,
679 };
680
681 static int __init init_rsvp(void)
682 {
683 return register_tcf_proto_ops(&RSVP_OPS);
684 }
685
686 static void __exit exit_rsvp(void)
687 {
688 unregister_tcf_proto_ops(&RSVP_OPS);
689 }
690
691 module_init(init_rsvp)
692 module_exit(exit_rsvp)
Linux kernel - Deliverables
This page took 0.055502 seconds and 4 git commands to generate.