update atp870u driver to 0.78 from D-Link source
[linux-2.4.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 #include <linux/config.h>
69
70 struct rsvp_head
71 {
72         u32                     tmap[256/32];
73         u32                     hgenerator;
74         u8                      tgenerator;
75         struct rsvp_session     *ht[256];
76 };
77
78 struct 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
90 struct 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 #ifdef CONFIG_NET_CLS_POLICE
99         struct tcf_police       *police;
100 #endif
101
102         u32                     handle;
103         struct rsvp_session     *sess;
104 };
105
106 static __inline__ unsigned hash_dst(u32 *dst, u8 protocol, u8 tunnelid)
107 {
108         unsigned h = dst[RSVP_DST_LEN-1];
109         h ^= h>>16;
110         h ^= h>>8;
111         return (h ^ protocol ^ tunnelid) & 0xFF;
112 }
113
114 static __inline__ unsigned hash_src(u32 *src)
115 {
116         unsigned h = src[RSVP_DST_LEN-1];
117         h ^= h>>16;
118         h ^= h>>8;
119         h ^= h>>4;
120         return h & 0xF;
121 }
122
123 #ifdef CONFIG_NET_CLS_POLICE
124 #define RSVP_POLICE() \
125 if (f->police) { \
126         int pol_res = tcf_police(skb, f->police); \
127         if (pol_res < 0) continue; \
128         if (pol_res) return pol_res; \
129 }
130 #else
131 #define RSVP_POLICE()
132 #endif
133
134
135 static 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
152 restart:
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
193                                         RSVP_POLICE();
194
195 matched:
196                                         if (f->tunnelhdr == 0)
197                                                 return 0;
198
199                                         tunnelid = f->res.classid;
200                                         nhptr = (void*)(xprt + f->tunnelhdr - sizeof(*nhptr));
201                                         goto restart;
202                                 }
203                         }
204
205                         /* And wildcard bucket... */
206                         for (f = s->ht[16]; f; f = f->next) {
207                                 *res = f->res;
208                                 RSVP_POLICE();
209                                 goto matched;
210                         }
211                         return -1;
212                 }
213         }
214         return -1;
215 }
216
217 static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
218 {
219         struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
220         struct rsvp_session *s;
221         struct rsvp_filter *f;
222         unsigned h1 = handle&0xFF;
223         unsigned h2 = (handle>>8)&0xFF;
224
225         if (h2 > 16)
226                 return 0;
227
228         for (s = sht[h1]; s; s = s->next) {
229                 for (f = s->ht[h2]; f; f = f->next) {
230                         if (f->handle == handle)
231                                 return (unsigned long)f;
232                 }
233         }
234         return 0;
235 }
236
237 static void rsvp_put(struct tcf_proto *tp, unsigned long f)
238 {
239 }
240
241 static int rsvp_init(struct tcf_proto *tp)
242 {
243         struct rsvp_head *data;
244
245         MOD_INC_USE_COUNT;
246         data = kmalloc(sizeof(struct rsvp_head), GFP_KERNEL);
247         if (data) {
248                 memset(data, 0, sizeof(struct rsvp_head));
249                 tp->root = data;
250                 return 0;
251         }
252         MOD_DEC_USE_COUNT;
253         return -ENOBUFS;
254 }
255
256 static void rsvp_destroy(struct tcf_proto *tp)
257 {
258         struct rsvp_head *data = xchg(&tp->root, NULL);
259         struct rsvp_session **sht;
260         int h1, h2;
261
262         if (data == NULL)
263                 return;
264
265         sht = data->ht;
266
267         for (h1=0; h1<256; h1++) {
268                 struct rsvp_session *s;
269
270                 while ((s = sht[h1]) != NULL) {
271                         sht[h1] = s->next;
272
273                         for (h2=0; h2<=16; h2++) {
274                                 struct rsvp_filter *f;
275
276                                 while ((f = s->ht[h2]) != NULL) {
277                                         unsigned long cl;
278
279                                         s->ht[h2] = f->next;
280                                         if ((cl = __cls_set_class(&f->res.class, 0)) != 0)
281                                                 tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
282 #ifdef CONFIG_NET_CLS_POLICE
283                                         tcf_police_release(f->police);
284 #endif
285                                         kfree(f);
286                                 }
287                         }
288                         kfree(s);
289                 }
290         }
291         kfree(data);
292         MOD_DEC_USE_COUNT;
293 }
294
295 static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
296 {
297         struct rsvp_filter **fp, *f = (struct rsvp_filter*)arg;
298         unsigned h = f->handle;
299         struct rsvp_session **sp;
300         struct rsvp_session *s = f->sess;
301         int i;
302
303         for (fp = &s->ht[(h>>8)&0xFF]; *fp; fp = &(*fp)->next) {
304                 if (*fp == f) {
305                         unsigned long cl;
306
307
308                         tcf_tree_lock(tp);
309                         *fp = f->next;
310                         tcf_tree_unlock(tp);
311
312                         if ((cl = cls_set_class(tp, &f->res.class, 0)) != 0)
313                                 tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
314
315 #ifdef CONFIG_NET_CLS_POLICE
316                         tcf_police_release(f->police);
317 #endif
318
319                         kfree(f);
320
321                         /* Strip tree */
322
323                         for (i=0; i<=16; i++)
324                                 if (s->ht[i])
325                                         return 0;
326
327                         /* OK, session has no flows */
328                         for (sp = &((struct rsvp_head*)tp->root)->ht[h&0xFF];
329                              *sp; sp = &(*sp)->next) {
330                                 if (*sp == s) {
331                                         tcf_tree_lock(tp);
332                                         *sp = s->next;
333                                         tcf_tree_unlock(tp);
334
335                                         kfree(s);
336                                         return 0;
337                                 }
338                         }
339
340                         return 0;
341                 }
342         }
343         return 0;
344 }
345
346 static unsigned gen_handle(struct tcf_proto *tp, unsigned salt)
347 {
348         struct rsvp_head *data = tp->root;
349         int i = 0xFFFF;
350
351         while (i-- > 0) {
352                 u32 h;
353                 if ((data->hgenerator += 0x10000) == 0)
354                         data->hgenerator = 0x10000;
355                 h = data->hgenerator|salt;
356                 if (rsvp_get(tp, h) == 0)
357                         return h;
358         }
359         return 0;
360 }
361
362 static int tunnel_bts(struct rsvp_head *data)
363 {
364         int n = data->tgenerator>>5;
365         u32 b = 1<<(data->tgenerator&0x1F);
366         
367         if (data->tmap[n]&b)
368                 return 0;
369         data->tmap[n] |= b;
370         return 1;
371 }
372
373 static void tunnel_recycle(struct rsvp_head *data)
374 {
375         struct rsvp_session **sht = data->ht;
376         u32 tmap[256/32];
377         int h1, h2;
378
379         memset(tmap, 0, sizeof(tmap));
380
381         for (h1=0; h1<256; h1++) {
382                 struct rsvp_session *s;
383                 for (s = sht[h1]; s; s = s->next) {
384                         for (h2=0; h2<=16; h2++) {
385                                 struct rsvp_filter *f;
386
387                                 for (f = s->ht[h2]; f; f = f->next) {
388                                         if (f->tunnelhdr == 0)
389                                                 continue;
390                                         data->tgenerator = f->res.classid;
391                                         tunnel_bts(data);
392                                 }
393                         }
394                 }
395         }
396
397         memcpy(data->tmap, tmap, sizeof(tmap));
398 }
399
400 static u32 gen_tunnel(struct rsvp_head *data)
401 {
402         int i, k;
403
404         for (k=0; k<2; k++) {
405                 for (i=255; i>0; i--) {
406                         if (++data->tgenerator == 0)
407                                 data->tgenerator = 1;
408                         if (tunnel_bts(data))
409                                 return data->tgenerator;
410                 }
411                 tunnel_recycle(data);
412         }
413         return 0;
414 }
415
416 static int rsvp_change(struct tcf_proto *tp, unsigned long base,
417                        u32 handle,
418                        struct rtattr **tca,
419                        unsigned long *arg)
420 {
421         struct rsvp_head *data = tp->root;
422         struct rsvp_filter *f, **fp;
423         struct rsvp_session *s, **sp;
424         struct tc_rsvp_pinfo *pinfo = NULL;
425         struct rtattr *opt = tca[TCA_OPTIONS-1];
426         struct rtattr *tb[TCA_RSVP_MAX];
427         unsigned h1, h2;
428         u32 *dst;
429         int err;
430
431         if (opt == NULL)
432                 return handle ? -EINVAL : 0;
433
434         if (rtattr_parse(tb, TCA_RSVP_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)
435                 return -EINVAL;
436
437         if ((f = (struct rsvp_filter*)*arg) != NULL) {
438                 /* Node exists: adjust only classid */
439
440                 if (f->handle != handle && handle)
441                         return -EINVAL;
442                 if (tb[TCA_RSVP_CLASSID-1]) {
443                         unsigned long cl;
444
445                         f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
446                         cl = cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
447                         if (cl)
448                                 tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
449                 }
450 #ifdef CONFIG_NET_CLS_POLICE
451                 if (tb[TCA_RSVP_POLICE-1]) {
452                         struct tcf_police *police = tcf_police_locate(tb[TCA_RSVP_POLICE-1], tca[TCA_RATE-1]);
453
454                         tcf_tree_lock(tp);
455                         police = xchg(&f->police, police);
456                         tcf_tree_unlock(tp);
457
458                         tcf_police_release(police);
459                 }
460 #endif
461                 return 0;
462         }
463
464         /* Now more serious part... */
465         if (handle)
466                 return -EINVAL;
467         if (tb[TCA_RSVP_DST-1] == NULL)
468                 return -EINVAL;
469
470         f = kmalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
471         if (f == NULL)
472                 return -ENOBUFS;
473
474         memset(f, 0, sizeof(*f));
475         h2 = 16;
476         if (tb[TCA_RSVP_SRC-1]) {
477                 err = -EINVAL;
478                 if (RTA_PAYLOAD(tb[TCA_RSVP_SRC-1]) != sizeof(f->src))
479                         goto errout;
480                 memcpy(f->src, RTA_DATA(tb[TCA_RSVP_SRC-1]), sizeof(f->src));
481                 h2 = hash_src(f->src);
482         }
483         if (tb[TCA_RSVP_PINFO-1]) {
484                 err = -EINVAL;
485                 if (RTA_PAYLOAD(tb[TCA_RSVP_PINFO-1]) < sizeof(struct tc_rsvp_pinfo))
486                         goto errout;
487                 pinfo = RTA_DATA(tb[TCA_RSVP_PINFO-1]);
488                 f->spi = pinfo->spi;
489                 f->tunnelhdr = pinfo->tunnelhdr;
490         }
491         if (tb[TCA_RSVP_CLASSID-1]) {
492                 err = -EINVAL;
493                 if (RTA_PAYLOAD(tb[TCA_RSVP_CLASSID-1]) != 4)
494                         goto errout;
495                 f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
496         }
497
498         err = -EINVAL;
499         if (RTA_PAYLOAD(tb[TCA_RSVP_DST-1]) != sizeof(f->src))
500                 goto errout;
501         dst = RTA_DATA(tb[TCA_RSVP_DST-1]);
502         h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
503
504         err = -ENOMEM;
505         if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
506                 goto errout;
507
508         if (f->tunnelhdr) {
509                 err = -EINVAL;
510                 if (f->res.classid > 255)
511                         goto errout;
512
513                 err = -ENOMEM;
514                 if (f->res.classid == 0 &&
515                     (f->res.classid = gen_tunnel(data)) == 0)
516                         goto errout;
517         }
518
519         for (sp = &data->ht[h1]; (s=*sp) != NULL; sp = &s->next) {
520                 if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
521                     pinfo && pinfo->protocol == s->protocol &&
522                     memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0
523 #if RSVP_DST_LEN == 4
524                     && dst[0] == s->dst[0]
525                     && dst[1] == s->dst[1]
526                     && dst[2] == s->dst[2]
527 #endif
528                     && pinfo->tunnelid == s->tunnelid) {
529
530 insert:
531                         /* OK, we found appropriate session */
532
533                         fp = &s->ht[h2];
534
535                         f->sess = s;
536                         if (f->tunnelhdr == 0)
537                                 cls_set_class(tp, &f->res.class, tp->q->ops->cl_ops->bind_tcf(tp->q, base, f->res.classid));
538 #ifdef CONFIG_NET_CLS_POLICE
539                         if (tb[TCA_RSVP_POLICE-1])
540                                 f->police = tcf_police_locate(tb[TCA_RSVP_POLICE-1], tca[TCA_RATE-1]);
541 #endif
542
543                         for (fp = &s->ht[h2]; *fp; fp = &(*fp)->next)
544                                 if (((*fp)->spi.mask&f->spi.mask) != f->spi.mask)
545                                         break;
546                         f->next = *fp;
547                         wmb();
548                         *fp = f;
549
550                         *arg = (unsigned long)f;
551                         return 0;
552                 }
553         }
554
555         /* No session found. Create new one. */
556
557         err = -ENOBUFS;
558         s = kmalloc(sizeof(struct rsvp_session), GFP_KERNEL);
559         if (s == NULL)
560                 goto errout;
561         memset(s, 0, sizeof(*s));
562         memcpy(s->dst, dst, sizeof(s->dst));
563
564         if (pinfo) {
565                 s->dpi = pinfo->dpi;
566                 s->protocol = pinfo->protocol;
567                 s->tunnelid = pinfo->tunnelid;
568         }
569         for (sp = &data->ht[h1]; *sp; sp = &(*sp)->next) {
570                 if (((*sp)->dpi.mask&s->dpi.mask) != s->dpi.mask)
571                         break;
572         }
573         s->next = *sp;
574         wmb();
575         *sp = s;
576         
577         goto insert;
578
579 errout:
580         if (f)
581                 kfree(f);
582         return err;
583 }
584
585 static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
586 {
587         struct rsvp_head *head = tp->root;
588         unsigned h, h1;
589
590         if (arg->stop)
591                 return;
592
593         for (h = 0; h < 256; h++) {
594                 struct rsvp_session *s;
595
596                 for (s = head->ht[h]; s; s = s->next) {
597                         for (h1 = 0; h1 <= 16; h1++) {
598                                 struct rsvp_filter *f;
599
600                                 for (f = s->ht[h1]; f; f = f->next) {
601                                         if (arg->count < arg->skip) {
602                                                 arg->count++;
603                                                 continue;
604                                         }
605                                         if (arg->fn(tp, (unsigned long)f, arg) < 0) {
606                                                 arg->stop = 1;
607                                                 return;
608                                         }
609                                         arg->count++;
610                                 }
611                         }
612                 }
613         }
614 }
615
616 static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
617                      struct sk_buff *skb, struct tcmsg *t)
618 {
619         struct rsvp_filter *f = (struct rsvp_filter*)fh;
620         struct rsvp_session *s;
621         unsigned char    *b = skb->tail;
622         struct rtattr *rta;
623         struct tc_rsvp_pinfo pinfo;
624
625         if (f == NULL)
626                 return skb->len;
627         s = f->sess;
628
629         t->tcm_handle = f->handle;
630
631
632         rta = (struct rtattr*)b;
633         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
634
635         RTA_PUT(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst);
636         pinfo.dpi = s->dpi;
637         pinfo.spi = f->spi;
638         pinfo.protocol = s->protocol;
639         pinfo.tunnelid = s->tunnelid;
640         pinfo.tunnelhdr = f->tunnelhdr;
641         RTA_PUT(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo);
642         if (f->res.classid)
643                 RTA_PUT(skb, TCA_RSVP_CLASSID, 4, &f->res.classid);
644         if (((f->handle>>8)&0xFF) != 16)
645                 RTA_PUT(skb, TCA_RSVP_SRC, sizeof(f->src), f->src);
646 #ifdef CONFIG_NET_CLS_POLICE
647         if (f->police) {
648                 struct rtattr * p_rta = (struct rtattr*)skb->tail;
649
650                 RTA_PUT(skb, TCA_RSVP_POLICE, 0, NULL);
651
652                 if (tcf_police_dump(skb, f->police) < 0)
653                         goto rtattr_failure;
654
655                 p_rta->rta_len = skb->tail - (u8*)p_rta;
656         }
657 #endif
658
659         rta->rta_len = skb->tail - b;
660 #ifdef CONFIG_NET_CLS_POLICE
661         if (f->police) {
662                 if (qdisc_copy_stats(skb, &f->police->stats))
663                         goto rtattr_failure;
664         }
665 #endif
666         return skb->len;
667
668 rtattr_failure:
669         skb_trim(skb, b - skb->data);
670         return -1;
671 }
672
673 struct tcf_proto_ops RSVP_OPS = {
674         NULL,
675         RSVP_ID,
676         rsvp_classify,
677         rsvp_init,
678         rsvp_destroy,
679
680         rsvp_get,
681         rsvp_put,
682         rsvp_change,
683         rsvp_delete,
684         rsvp_walk,
685         rsvp_dump
686 };
687
688 #ifdef MODULE
689 int init_module(void)
690 {
691         return register_tcf_proto_ops(&RSVP_OPS);
692 }
693
694 void cleanup_module(void) 
695 {
696         unregister_tcf_proto_ops(&RSVP_OPS);
697 }
698 #endif