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.
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
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. */
68 #include <linux/config.h>
75 struct rsvp_session *ht[256];
80 struct rsvp_session *next;
81 u32 dst[RSVP_DST_LEN];
82 struct tc_rsvp_gpi dpi;
85 /* 16 (src,sport) hash slots, and one wildcard source slot */
86 struct rsvp_filter *ht[16+1];
92 struct rsvp_filter *next;
93 u32 src[RSVP_DST_LEN];
94 struct tc_rsvp_gpi spi;
97 struct tcf_result res;
98 #ifdef CONFIG_NET_CLS_POLICE
99 struct tcf_police *police;
103 struct rsvp_session *sess;
106 static __inline__ unsigned hash_dst(u32 *dst, u8 protocol, u8 tunnelid)
108 unsigned h = dst[RSVP_DST_LEN-1];
111 return (h ^ protocol ^ tunnelid) & 0xFF;
114 static __inline__ unsigned hash_src(u32 *src)
116 unsigned h = src[RSVP_DST_LEN-1];
123 #ifdef CONFIG_NET_CLS_POLICE
124 #define RSVP_POLICE() \
126 int pol_res = tcf_police(skb, f->police); \
127 if (pol_res < 0) continue; \
128 if (pol_res) return pol_res; \
131 #define RSVP_POLICE()
135 static int rsvp_classify(struct sk_buff *skb, struct tcf_proto *tp,
136 struct tcf_result *res)
138 struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
139 struct rsvp_session *s;
140 struct rsvp_filter *f;
146 #if RSVP_DST_LEN == 4
147 struct ipv6hdr *nhptr = skb->nh.ipv6h;
149 struct iphdr *nhptr = skb->nh.iph;
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);
162 protocol = nhptr->protocol;
163 xprt = ((u8*)nhptr) + (nhptr->ihl<<2);
164 if (nhptr->frag_off&__constant_htons(IP_MF|IP_OFFSET))
168 h1 = hash_dst(dst, protocol, tunnelid);
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]
180 && tunnelid == s->tunnelid) {
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]
196 if (f->tunnelhdr == 0)
199 tunnelid = f->res.classid;
200 nhptr = (void*)(xprt + f->tunnelhdr - sizeof(*nhptr));
205 /* And wildcard bucket... */
206 for (f = s->ht[16]; f; f = f->next) {
217 static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
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;
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;
237 static void rsvp_put(struct tcf_proto *tp, unsigned long f)
241 static int rsvp_init(struct tcf_proto *tp)
243 struct rsvp_head *data;
246 data = kmalloc(sizeof(struct rsvp_head), GFP_KERNEL);
248 memset(data, 0, sizeof(struct rsvp_head));
256 static void rsvp_destroy(struct tcf_proto *tp)
258 struct rsvp_head *data = xchg(&tp->root, NULL);
259 struct rsvp_session **sht;
267 for (h1=0; h1<256; h1++) {
268 struct rsvp_session *s;
270 while ((s = sht[h1]) != NULL) {
273 for (h2=0; h2<=16; h2++) {
274 struct rsvp_filter *f;
276 while ((f = s->ht[h2]) != NULL) {
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);
295 static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
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;
303 for (fp = &s->ht[(h>>8)&0xFF]; *fp; fp = &(*fp)->next) {
312 if ((cl = cls_set_class(tp, &f->res.class, 0)) != 0)
313 tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
315 #ifdef CONFIG_NET_CLS_POLICE
316 tcf_police_release(f->police);
323 for (i=0; i<=16; i++)
327 /* OK, session has no flows */
328 for (sp = &((struct rsvp_head*)tp->root)->ht[h&0xFF];
329 *sp; sp = &(*sp)->next) {
346 static unsigned gen_handle(struct tcf_proto *tp, unsigned salt)
348 struct rsvp_head *data = tp->root;
353 if ((data->hgenerator += 0x10000) == 0)
354 data->hgenerator = 0x10000;
355 h = data->hgenerator|salt;
356 if (rsvp_get(tp, h) == 0)
362 static int tunnel_bts(struct rsvp_head *data)
364 int n = data->tgenerator>>5;
365 u32 b = 1<<(data->tgenerator&0x1F);
373 static void tunnel_recycle(struct rsvp_head *data)
375 struct rsvp_session **sht = data->ht;
379 memset(tmap, 0, sizeof(tmap));
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;
387 for (f = s->ht[h2]; f; f = f->next) {
388 if (f->tunnelhdr == 0)
390 data->tgenerator = f->res.classid;
397 memcpy(data->tmap, tmap, sizeof(tmap));
400 static u32 gen_tunnel(struct rsvp_head *data)
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;
411 tunnel_recycle(data);
416 static int rsvp_change(struct tcf_proto *tp, unsigned long base,
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];
432 return handle ? -EINVAL : 0;
434 if (rtattr_parse(tb, TCA_RSVP_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)
437 if ((f = (struct rsvp_filter*)*arg) != NULL) {
438 /* Node exists: adjust only classid */
440 if (f->handle != handle && handle)
442 if (tb[TCA_RSVP_CLASSID-1]) {
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));
448 tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
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]);
455 police = xchg(&f->police, police);
458 tcf_police_release(police);
464 /* Now more serious part... */
467 if (tb[TCA_RSVP_DST-1] == NULL)
470 f = kmalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
474 memset(f, 0, sizeof(*f));
476 if (tb[TCA_RSVP_SRC-1]) {
478 if (RTA_PAYLOAD(tb[TCA_RSVP_SRC-1]) != sizeof(f->src))
480 memcpy(f->src, RTA_DATA(tb[TCA_RSVP_SRC-1]), sizeof(f->src));
481 h2 = hash_src(f->src);
483 if (tb[TCA_RSVP_PINFO-1]) {
485 if (RTA_PAYLOAD(tb[TCA_RSVP_PINFO-1]) < sizeof(struct tc_rsvp_pinfo))
487 pinfo = RTA_DATA(tb[TCA_RSVP_PINFO-1]);
489 f->tunnelhdr = pinfo->tunnelhdr;
491 if (tb[TCA_RSVP_CLASSID-1]) {
493 if (RTA_PAYLOAD(tb[TCA_RSVP_CLASSID-1]) != 4)
495 f->res.classid = *(u32*)RTA_DATA(tb[TCA_RSVP_CLASSID-1]);
499 if (RTA_PAYLOAD(tb[TCA_RSVP_DST-1]) != sizeof(f->src))
501 dst = RTA_DATA(tb[TCA_RSVP_DST-1]);
502 h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
505 if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
510 if (f->res.classid > 255)
514 if (f->res.classid == 0 &&
515 (f->res.classid = gen_tunnel(data)) == 0)
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]
528 && pinfo->tunnelid == s->tunnelid) {
531 /* OK, we found appropriate session */
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]);
543 for (fp = &s->ht[h2]; *fp; fp = &(*fp)->next)
544 if (((*fp)->spi.mask&f->spi.mask) != f->spi.mask)
550 *arg = (unsigned long)f;
555 /* No session found. Create new one. */
558 s = kmalloc(sizeof(struct rsvp_session), GFP_KERNEL);
561 memset(s, 0, sizeof(*s));
562 memcpy(s->dst, dst, sizeof(s->dst));
566 s->protocol = pinfo->protocol;
567 s->tunnelid = pinfo->tunnelid;
569 for (sp = &data->ht[h1]; *sp; sp = &(*sp)->next) {
570 if (((*sp)->dpi.mask&s->dpi.mask) != s->dpi.mask)
585 static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
587 struct rsvp_head *head = tp->root;
593 for (h = 0; h < 256; h++) {
594 struct rsvp_session *s;
596 for (s = head->ht[h]; s; s = s->next) {
597 for (h1 = 0; h1 <= 16; h1++) {
598 struct rsvp_filter *f;
600 for (f = s->ht[h1]; f; f = f->next) {
601 if (arg->count < arg->skip) {
605 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
616 static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
617 struct sk_buff *skb, struct tcmsg *t)
619 struct rsvp_filter *f = (struct rsvp_filter*)fh;
620 struct rsvp_session *s;
621 unsigned char *b = skb->tail;
623 struct tc_rsvp_pinfo pinfo;
629 t->tcm_handle = f->handle;
632 rta = (struct rtattr*)b;
633 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
635 RTA_PUT(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst);
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);
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
648 struct rtattr * p_rta = (struct rtattr*)skb->tail;
650 RTA_PUT(skb, TCA_RSVP_POLICE, 0, NULL);
652 if (tcf_police_dump(skb, f->police) < 0)
655 p_rta->rta_len = skb->tail - (u8*)p_rta;
659 rta->rta_len = skb->tail - b;
660 #ifdef CONFIG_NET_CLS_POLICE
662 if (qdisc_copy_stats(skb, &f->police->stats))
669 skb_trim(skb, b - skb->data);
673 struct tcf_proto_ops RSVP_OPS = {
689 int init_module(void)
691 return register_tcf_proto_ops(&RSVP_OPS);
694 void cleanup_module(void)
696 unregister_tcf_proto_ops(&RSVP_OPS);