blob: 572f06be3b02a181447c1e125056a833687ef017 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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#include <linux/config.h>
69
70struct rsvp_head
71{
72 u32 tmap[256/32];
73 u32 hgenerator;
74 u8 tgenerator;
75 struct rsvp_session *ht[256];
76};
77
78struct rsvp_session
79{
80 struct rsvp_session *next;
81 u32 dst[RSVP_DST_LEN];
82 struct tc_rsvp_gpi dpi;
83 u8 protocol;
84 u8 tunnelid;
85 /* 16 (src,sport) hash slots, and one wildcard source slot */
86 struct rsvp_filter *ht[16+1];
87};
88
89
90struct rsvp_filter
91{
92 struct rsvp_filter *next;
93 u32 src[RSVP_DST_LEN];
94 struct tc_rsvp_gpi spi;
95 u8 tunnelhdr;
96
97 struct tcf_result res;
98 struct tcf_exts exts;
99
100 u32 handle;
101 struct rsvp_session *sess;
102};
103
104static __inline__ unsigned hash_dst(u32 *dst, u8 protocol, u8 tunnelid)
105{
106 unsigned h = dst[RSVP_DST_LEN-1];
107 h ^= h>>16;
108 h ^= h>>8;
109 return (h ^ protocol ^ tunnelid) & 0xFF;
110}
111
112static __inline__ unsigned hash_src(u32 *src)
113{
114 unsigned h = src[RSVP_DST_LEN-1];
115 h ^= h>>16;
116 h ^= h>>8;
117 h ^= h>>4;
118 return h & 0xF;
119}
120
121static struct tcf_ext_map rsvp_ext_map = {
122 .police = TCA_RSVP_POLICE,
123 .action = TCA_RSVP_ACT
124};
125
126#define RSVP_APPLY_RESULT() \
127{ \
128 int r = tcf_exts_exec(skb, &f->exts, res); \
129 if (r < 0) \
130 continue; \
131 else if (r > 0) \
132 return r; \
133}
134
135static int rsvp_classify(struct sk_buff *skb, struct tcf_proto *tp,
136 struct tcf_result *res)
137{
138 struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
139 struct rsvp_session *s;
140 struct rsvp_filter *f;
141 unsigned h1, h2;
142 u32 *dst, *src;
143 u8 protocol;
144 u8 tunnelid = 0;
145 u8 *xprt;
146#if RSVP_DST_LEN == 4
147 struct ipv6hdr *nhptr = skb->nh.ipv6h;
148#else
149 struct iphdr *nhptr = skb->nh.iph;
150#endif
151
152restart:
153
154#if RSVP_DST_LEN == 4
155 src = &nhptr->saddr.s6_addr32[0];
156 dst = &nhptr->daddr.s6_addr32[0];
157 protocol = nhptr->nexthdr;
158 xprt = ((u8*)nhptr) + sizeof(struct ipv6hdr);
159#else
160 src = &nhptr->saddr;
161 dst = &nhptr->daddr;
162 protocol = nhptr->protocol;
163 xprt = ((u8*)nhptr) + (nhptr->ihl<<2);
164 if (nhptr->frag_off&__constant_htons(IP_MF|IP_OFFSET))
165 return -1;
166#endif
167
168 h1 = hash_dst(dst, protocol, tunnelid);
169 h2 = hash_src(src);
170
171 for (s = sht[h1]; s; s = s->next) {
172 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
173 protocol == s->protocol &&
174 !(s->dpi.mask & (*(u32*)(xprt+s->dpi.offset)^s->dpi.key))
175#if RSVP_DST_LEN == 4
176 && dst[0] == s->dst[0]
177 && dst[1] == s->dst[1]
178 && dst[2] == s->dst[2]
179#endif
180 && tunnelid == s->tunnelid) {
181
182 for (f = s->ht[h2]; f; f = f->next) {
183 if (src[RSVP_DST_LEN-1] == f->src[RSVP_DST_LEN-1] &&
184 !(f->spi.mask & (*(u32*)(xprt+f->spi.offset)^f->spi.key))
185#if RSVP_DST_LEN == 4
186 && src[0] == f->src[0]
187 && src[1] == f->src[1]
188 && src[2] == f->src[2]
189#endif
190 ) {
191 *res = f->res;
192 RSVP_APPLY_RESULT();
193
194matched:
195 if (f->tunnelhdr == 0)
196 return 0;
197
198 tunnelid = f->res.classid;
199 nhptr = (void*)(xprt + f->tunnelhdr - sizeof(*nhptr));
200 goto restart;
201 }
202 }
203
204 /* And wildcard bucket... */
205 for (f = s->ht[16]; f; f = f->next) {
206 *res = f->res;
207 RSVP_APPLY_RESULT();
208 goto matched;
209 }
210 return -1;
211 }
212 }
213 return -1;
214}
215
216static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
217{
218 struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
219 struct rsvp_session *s;
220 struct rsvp_filter *f;
221 unsigned h1 = handle&0xFF;
222 unsigned h2 = (handle>>8)&0xFF;
223
224 if (h2 > 16)
225 return 0;
226
227 for (s = sht[h1]; s; s = s->next) {
228 for (f = s->ht[h2]; f; f = f->next) {
229 if (f->handle == handle)
230 return (unsigned long)f;
231 }
232 }
233 return 0;
234}
235
236static void rsvp_put(struct tcf_proto *tp, unsigned long f)
237{
238}
239
240static int rsvp_init(struct tcf_proto *tp)
241{
242 struct rsvp_head *data;
243
244 data = kmalloc(sizeof(struct rsvp_head), GFP_KERNEL);
245 if (data) {
246 memset(data, 0, sizeof(struct rsvp_head));
247 tp->root = data;
248 return 0;
249 }
250 return -ENOBUFS;
251}
252
253static inline void
254rsvp_delete_filter(struct tcf_proto *tp, struct rsvp_filter *f)
255{
256 tcf_unbind_filter(tp, &f->res);
257 tcf_exts_destroy(tp, &f->exts);
258 kfree(f);
259}
260
261static void rsvp_destroy(struct tcf_proto *tp)
262{
263 struct rsvp_head *data = xchg(&tp->root, NULL);
264 struct rsvp_session **sht;
265 int h1, h2;
266
267 if (data == NULL)
268 return;
269
270 sht = data->ht;
271
272 for (h1=0; h1<256; h1++) {
273 struct rsvp_session *s;
274
275 while ((s = sht[h1]) != NULL) {
276 sht[h1] = s->next;
277
278 for (h2=0; h2<=16; h2++) {
279 struct rsvp_filter *f;
280
281 while ((f = s->ht[h2]) != NULL) {
282 s->ht[h2] = f->next;
283 rsvp_delete_filter(tp, f);
284 }
285 }
286 kfree(s);
287 }
288 }
289 kfree(data);
290}
291
292static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
293{
294 struct rsvp_filter **fp, *f = (struct rsvp_filter*)arg;
295 unsigned h = f->handle;
296 struct rsvp_session **sp;
297 struct rsvp_session *s = f->sess;
298 int i;
299
300 for (fp = &s->ht[(h>>8)&0xFF]; *fp; fp = &(*fp)->next) {
301 if (*fp == f) {
302 tcf_tree_lock(tp);
303 *fp = f->next;
304 tcf_tree_unlock(tp);
305 rsvp_delete_filter(tp, f);
306
307 /* Strip tree */
308
309 for (i=0; i<=16; i++)
310 if (s->ht[i])
311 return 0;
312
313 /* OK, session has no flows */
314 for (sp = &((struct rsvp_head*)tp->root)->ht[h&0xFF];
315 *sp; sp = &(*sp)->next) {
316 if (*sp == s) {
317 tcf_tree_lock(tp);
318 *sp = s->next;
319 tcf_tree_unlock(tp);
320
321 kfree(s);
322 return 0;
323 }
324 }
325
326 return 0;
327 }
328 }
329 return 0;
330}
331
332static unsigned gen_handle(struct tcf_proto *tp, unsigned salt)
333{
334 struct rsvp_head *data = tp->root;
335 int i = 0xFFFF;
336
337 while (i-- > 0) {
338 u32 h;
339 if ((data->hgenerator += 0x10000) == 0)
340 data->hgenerator = 0x10000;
341 h = data->hgenerator|salt;
342 if (rsvp_get(tp, h) == 0)
343 return h;
344 }
345 return 0;
346}
347
348static int tunnel_bts(struct rsvp_head *data)
349{
350 int n = data->tgenerator>>5;
351 u32 b = 1<<(data->tgenerator&0x1F);
352
353 if (data->tmap[n]&b)
354 return 0;
355 data->tmap[n] |= b;
356 return 1;
357}
358
359static void tunnel_recycle(struct rsvp_head *data)
360{
361 struct rsvp_session **sht = data->ht;
362 u32 tmap[256/32];
363 int h1, h2;
364
365 memset(tmap, 0, sizeof(tmap));
366
367 for (h1=0; h1<256; h1++) {
368 struct rsvp_session *s;
369 for (s = sht[h1]; s; s = s->next) {
370 for (h2=0; h2<=16; h2++) {
371 struct rsvp_filter *f;
372
373 for (f = s->ht[h2]; f; f = f->next) {
374 if (f->tunnelhdr == 0)
375 continue;
376 data->tgenerator = f->res.classid;
377 tunnel_bts(data);
378 }
379 }
380 }
381 }
382
383 memcpy(data->tmap, tmap, sizeof(tmap));
384}
385
386static u32 gen_tunnel(struct rsvp_head *data)
387{
388 int i, k;
389
390 for (k=0; k<2; k++) {
391 for (i=255; i>0; i--) {
392 if (++data->tgenerator == 0)
393 data->tgenerator = 1;
394 if (tunnel_bts(data))
395 return data->tgenerator;
396 }
397 tunnel_recycle(data);
398 }
399 return 0;
400}
401
402static int rsvp_change(struct tcf_proto *tp, unsigned long base,
403 u32 handle,
404 struct rtattr **tca,
405 unsigned long *arg)
406{
407 struct rsvp_head *data = tp->root;
408 struct rsvp_filter *f, **fp;
409 struct rsvp_session *s, **sp;
410 struct tc_rsvp_pinfo *pinfo = NULL;
411 struct rtattr *opt = tca[TCA_OPTIONS-1];
412 struct rtattr *tb[TCA_RSVP_MAX];
413 struct tcf_exts e;
414 unsigned h1, h2;
415 u32 *dst;
416 int err;
417
418 if (opt == NULL)
419 return handle ? -EINVAL : 0;
420
421 if (rtattr_parse_nested(tb, TCA_RSVP_MAX, opt) < 0)
422 return -EINVAL;
423
424 err = tcf_exts_validate(tp, tb, tca[TCA_RATE-1], &e, &rsvp_ext_map);
425 if (err < 0)
426 return err;
427
428 if ((f = (struct rsvp_filter*)*arg) != NULL) {
429 /* Node exists: adjust only classid */
430
431 if (f->handle != handle && handle)
432 goto errout2;
433 if (tb[TCA_RSVP_CLASSID-1]) {
434 f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
435 tcf_bind_filter(tp, &f->res, base);
436 }
437
438 tcf_exts_change(tp, &f->exts, &e);
439 return 0;
440 }
441
442 /* Now more serious part... */
443 err = -EINVAL;
444 if (handle)
445 goto errout2;
446 if (tb[TCA_RSVP_DST-1] == NULL)
447 goto errout2;
448
449 err = -ENOBUFS;
450 f = kmalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
451 if (f == NULL)
452 goto errout2;
453
454 memset(f, 0, sizeof(*f));
455 h2 = 16;
456 if (tb[TCA_RSVP_SRC-1]) {
457 err = -EINVAL;
458 if (RTA_PAYLOAD(tb[TCA_RSVP_SRC-1]) != sizeof(f->src))
459 goto errout;
460 memcpy(f->src, RTA_DATA(tb[TCA_RSVP_SRC-1]), sizeof(f->src));
461 h2 = hash_src(f->src);
462 }
463 if (tb[TCA_RSVP_PINFO-1]) {
464 err = -EINVAL;
465 if (RTA_PAYLOAD(tb[TCA_RSVP_PINFO-1]) < sizeof(struct tc_rsvp_pinfo))
466 goto errout;
467 pinfo = RTA_DATA(tb[TCA_RSVP_PINFO-1]);
468 f->spi = pinfo->spi;
469 f->tunnelhdr = pinfo->tunnelhdr;
470 }
471 if (tb[TCA_RSVP_CLASSID-1]) {
472 err = -EINVAL;
473 if (RTA_PAYLOAD(tb[TCA_RSVP_CLASSID-1]) != 4)
474 goto errout;
475 f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
476 }
477
478 err = -EINVAL;
479 if (RTA_PAYLOAD(tb[TCA_RSVP_DST-1]) != sizeof(f->src))
480 goto errout;
481 dst = RTA_DATA(tb[TCA_RSVP_DST-1]);
482 h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
483
484 err = -ENOMEM;
485 if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
486 goto errout;
487
488 if (f->tunnelhdr) {
489 err = -EINVAL;
490 if (f->res.classid > 255)
491 goto errout;
492
493 err = -ENOMEM;
494 if (f->res.classid == 0 &&
495 (f->res.classid = gen_tunnel(data)) == 0)
496 goto errout;
497 }
498
499 for (sp = &data->ht[h1]; (s=*sp) != NULL; sp = &s->next) {
500 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
501 pinfo && pinfo->protocol == s->protocol &&
502 memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0
503#if RSVP_DST_LEN == 4
504 && dst[0] == s->dst[0]
505 && dst[1] == s->dst[1]
506 && dst[2] == s->dst[2]
507#endif
508 && pinfo->tunnelid == s->tunnelid) {
509
510insert:
511 /* OK, we found appropriate session */
512
513 fp = &s->ht[h2];
514
515 f->sess = s;
516 if (f->tunnelhdr == 0)
517 tcf_bind_filter(tp, &f->res, base);
518
519 tcf_exts_change(tp, &f->exts, &e);
520
521 for (fp = &s->ht[h2]; *fp; fp = &(*fp)->next)
522 if (((*fp)->spi.mask&f->spi.mask) != f->spi.mask)
523 break;
524 f->next = *fp;
525 wmb();
526 *fp = f;
527
528 *arg = (unsigned long)f;
529 return 0;
530 }
531 }
532
533 /* No session found. Create new one. */
534
535 err = -ENOBUFS;
536 s = kmalloc(sizeof(struct rsvp_session), GFP_KERNEL);
537 if (s == NULL)
538 goto errout;
539 memset(s, 0, sizeof(*s));
540 memcpy(s->dst, dst, sizeof(s->dst));
541
542 if (pinfo) {
543 s->dpi = pinfo->dpi;
544 s->protocol = pinfo->protocol;
545 s->tunnelid = pinfo->tunnelid;
546 }
547 for (sp = &data->ht[h1]; *sp; sp = &(*sp)->next) {
548 if (((*sp)->dpi.mask&s->dpi.mask) != s->dpi.mask)
549 break;
550 }
551 s->next = *sp;
552 wmb();
553 *sp = s;
554
555 goto insert;
556
557errout:
Jesper Juhla51482b2005-11-08 09:41:34 -0800558 kfree(f);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559errout2:
560 tcf_exts_destroy(tp, &e);
561 return err;
562}
563
564static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
565{
566 struct rsvp_head *head = tp->root;
567 unsigned h, h1;
568
569 if (arg->stop)
570 return;
571
572 for (h = 0; h < 256; h++) {
573 struct rsvp_session *s;
574
575 for (s = head->ht[h]; s; s = s->next) {
576 for (h1 = 0; h1 <= 16; h1++) {
577 struct rsvp_filter *f;
578
579 for (f = s->ht[h1]; f; f = f->next) {
580 if (arg->count < arg->skip) {
581 arg->count++;
582 continue;
583 }
584 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
585 arg->stop = 1;
586 return;
587 }
588 arg->count++;
589 }
590 }
591 }
592 }
593}
594
595static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
596 struct sk_buff *skb, struct tcmsg *t)
597{
598 struct rsvp_filter *f = (struct rsvp_filter*)fh;
599 struct rsvp_session *s;
600 unsigned char *b = skb->tail;
601 struct rtattr *rta;
602 struct tc_rsvp_pinfo pinfo;
603
604 if (f == NULL)
605 return skb->len;
606 s = f->sess;
607
608 t->tcm_handle = f->handle;
609
610
611 rta = (struct rtattr*)b;
612 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
613
614 RTA_PUT(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst);
615 pinfo.dpi = s->dpi;
616 pinfo.spi = f->spi;
617 pinfo.protocol = s->protocol;
618 pinfo.tunnelid = s->tunnelid;
619 pinfo.tunnelhdr = f->tunnelhdr;
Patrick McHardy8a470772005-06-28 12:56:45 -0700620 pinfo.pad = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621 RTA_PUT(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo);
622 if (f->res.classid)
623 RTA_PUT(skb, TCA_RSVP_CLASSID, 4, &f->res.classid);
624 if (((f->handle>>8)&0xFF) != 16)
625 RTA_PUT(skb, TCA_RSVP_SRC, sizeof(f->src), f->src);
626
627 if (tcf_exts_dump(skb, &f->exts, &rsvp_ext_map) < 0)
628 goto rtattr_failure;
629
630 rta->rta_len = skb->tail - b;
631
632 if (tcf_exts_dump_stats(skb, &f->exts, &rsvp_ext_map) < 0)
633 goto rtattr_failure;
634 return skb->len;
635
636rtattr_failure:
637 skb_trim(skb, b - skb->data);
638 return -1;
639}
640
641static struct tcf_proto_ops RSVP_OPS = {
642 .next = NULL,
643 .kind = RSVP_ID,
644 .classify = rsvp_classify,
645 .init = rsvp_init,
646 .destroy = rsvp_destroy,
647 .get = rsvp_get,
648 .put = rsvp_put,
649 .change = rsvp_change,
650 .delete = rsvp_delete,
651 .walk = rsvp_walk,
652 .dump = rsvp_dump,
653 .owner = THIS_MODULE,
654};
655
656static int __init init_rsvp(void)
657{
658 return register_tcf_proto_ops(&RSVP_OPS);
659}
660
661static void __exit exit_rsvp(void)
662{
663 unregister_tcf_proto_ops(&RSVP_OPS);
664}
665
666module_init(init_rsvp)
667module_exit(exit_rsvp)