blob: ae97238c57ad8150b525d2ab42890e2f20079c6f [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * net/sched/cls_route.c ROUTE4 classifier.
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#include <linux/module.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070013#include <linux/types.h>
14#include <linux/kernel.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070015#include <linux/string.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070016#include <linux/errno.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070017#include <linux/skbuff.h>
Patrick McHardy0ba48052007-07-02 22:49:07 -070018#include <net/dst.h>
19#include <net/route.h>
20#include <net/netlink.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070021#include <net/act_api.h>
22#include <net/pkt_cls.h>
23
24/*
25 1. For now we assume that route tags < 256.
26 It allows to use direct table lookups, instead of hash tables.
27 2. For now we assume that "from TAG" and "fromdev DEV" statements
28 are mutually exclusive.
29 3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
30 */
31
32struct route4_fastmap
33{
34 struct route4_filter *filter;
35 u32 id;
36 int iif;
37};
38
39struct route4_head
40{
41 struct route4_fastmap fastmap[16];
42 struct route4_bucket *table[256+1];
43};
44
45struct route4_bucket
46{
47 /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
48 struct route4_filter *ht[16+16+1];
49};
50
51struct route4_filter
52{
53 struct route4_filter *next;
54 u32 id;
55 int iif;
56
57 struct tcf_result res;
58 struct tcf_exts exts;
59 u32 handle;
60 struct route4_bucket *bkt;
61};
62
63#define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
64
65static struct tcf_ext_map route_ext_map = {
66 .police = TCA_ROUTE4_POLICE,
67 .action = TCA_ROUTE4_ACT
68};
69
70static __inline__ int route4_fastmap_hash(u32 id, int iif)
71{
72 return id&0xF;
73}
74
75static inline
76void route4_reset_fastmap(struct net_device *dev, struct route4_head *head, u32 id)
77{
Patrick McHardyfd44de72007-04-16 17:07:08 -070078 qdisc_lock_tree(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -070079 memset(head->fastmap, 0, sizeof(head->fastmap));
Patrick McHardyfd44de72007-04-16 17:07:08 -070080 qdisc_unlock_tree(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -070081}
82
Dave Jonesb6f99a22007-03-22 12:27:49 -070083static inline void
Linus Torvalds1da177e2005-04-16 15:20:36 -070084route4_set_fastmap(struct route4_head *head, u32 id, int iif,
85 struct route4_filter *f)
86{
87 int h = route4_fastmap_hash(id, iif);
88 head->fastmap[h].id = id;
89 head->fastmap[h].iif = iif;
90 head->fastmap[h].filter = f;
91}
92
93static __inline__ int route4_hash_to(u32 id)
94{
95 return id&0xFF;
96}
97
98static __inline__ int route4_hash_from(u32 id)
99{
100 return (id>>16)&0xF;
101}
102
103static __inline__ int route4_hash_iif(int iif)
104{
105 return 16 + ((iif>>16)&0xF);
106}
107
108static __inline__ int route4_hash_wild(void)
109{
110 return 32;
111}
112
113#define ROUTE4_APPLY_RESULT() \
114{ \
115 *res = f->res; \
116 if (tcf_exts_is_available(&f->exts)) { \
117 int r = tcf_exts_exec(skb, &f->exts, res); \
118 if (r < 0) { \
119 dont_cache = 1; \
120 continue; \
121 } \
122 return r; \
123 } else if (!dont_cache) \
124 route4_set_fastmap(head, id, iif, f); \
125 return 0; \
126}
127
128static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp,
129 struct tcf_result *res)
130{
131 struct route4_head *head = (struct route4_head*)tp->root;
132 struct dst_entry *dst;
133 struct route4_bucket *b;
134 struct route4_filter *f;
135 u32 id, h;
136 int iif, dont_cache = 0;
137
138 if ((dst = skb->dst) == NULL)
139 goto failure;
140
141 id = dst->tclassid;
142 if (head == NULL)
143 goto old_method;
144
145 iif = ((struct rtable*)dst)->fl.iif;
146
147 h = route4_fastmap_hash(id, iif);
148 if (id == head->fastmap[h].id &&
149 iif == head->fastmap[h].iif &&
150 (f = head->fastmap[h].filter) != NULL) {
151 if (f == ROUTE4_FAILURE)
152 goto failure;
153
154 *res = f->res;
155 return 0;
156 }
157
158 h = route4_hash_to(id);
159
160restart:
161 if ((b = head->table[h]) != NULL) {
162 for (f = b->ht[route4_hash_from(id)]; f; f = f->next)
163 if (f->id == id)
164 ROUTE4_APPLY_RESULT();
165
166 for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)
167 if (f->iif == iif)
168 ROUTE4_APPLY_RESULT();
169
170 for (f = b->ht[route4_hash_wild()]; f; f = f->next)
171 ROUTE4_APPLY_RESULT();
172
173 }
174 if (h < 256) {
175 h = 256;
176 id &= ~0xFFFF;
177 goto restart;
178 }
179
180 if (!dont_cache)
181 route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
182failure:
183 return -1;
184
185old_method:
186 if (id && (TC_H_MAJ(id) == 0 ||
187 !(TC_H_MAJ(id^tp->q->handle)))) {
188 res->classid = id;
189 res->class = 0;
190 return 0;
191 }
192 return -1;
193}
194
195static inline u32 to_hash(u32 id)
196{
197 u32 h = id&0xFF;
198 if (id&0x8000)
199 h += 256;
200 return h;
201}
202
203static inline u32 from_hash(u32 id)
204{
205 id &= 0xFFFF;
206 if (id == 0xFFFF)
207 return 32;
208 if (!(id & 0x8000)) {
209 if (id > 255)
210 return 256;
211 return id&0xF;
212 }
213 return 16 + (id&0xF);
214}
215
216static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
217{
218 struct route4_head *head = (struct route4_head*)tp->root;
219 struct route4_bucket *b;
220 struct route4_filter *f;
221 unsigned h1, h2;
222
223 if (!head)
224 return 0;
225
226 h1 = to_hash(handle);
227 if (h1 > 256)
228 return 0;
229
230 h2 = from_hash(handle>>16);
231 if (h2 > 32)
232 return 0;
233
234 if ((b = head->table[h1]) != NULL) {
235 for (f = b->ht[h2]; f; f = f->next)
236 if (f->handle == handle)
237 return (unsigned long)f;
238 }
239 return 0;
240}
241
242static void route4_put(struct tcf_proto *tp, unsigned long f)
243{
244}
245
246static int route4_init(struct tcf_proto *tp)
247{
248 return 0;
249}
250
251static inline void
252route4_delete_filter(struct tcf_proto *tp, struct route4_filter *f)
253{
254 tcf_unbind_filter(tp, &f->res);
255 tcf_exts_destroy(tp, &f->exts);
256 kfree(f);
257}
258
259static void route4_destroy(struct tcf_proto *tp)
260{
261 struct route4_head *head = xchg(&tp->root, NULL);
262 int h1, h2;
263
264 if (head == NULL)
265 return;
266
267 for (h1=0; h1<=256; h1++) {
268 struct route4_bucket *b;
269
270 if ((b = head->table[h1]) != NULL) {
271 for (h2=0; h2<=32; h2++) {
272 struct route4_filter *f;
273
274 while ((f = b->ht[h2]) != NULL) {
275 b->ht[h2] = f->next;
276 route4_delete_filter(tp, f);
277 }
278 }
279 kfree(b);
280 }
281 }
282 kfree(head);
283}
284
285static int route4_delete(struct tcf_proto *tp, unsigned long arg)
286{
287 struct route4_head *head = (struct route4_head*)tp->root;
288 struct route4_filter **fp, *f = (struct route4_filter*)arg;
289 unsigned h = 0;
290 struct route4_bucket *b;
291 int i;
292
293 if (!head || !f)
294 return -EINVAL;
295
296 h = f->handle;
297 b = f->bkt;
298
299 for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {
300 if (*fp == f) {
301 tcf_tree_lock(tp);
302 *fp = f->next;
303 tcf_tree_unlock(tp);
304
305 route4_reset_fastmap(tp->q->dev, head, f->id);
306 route4_delete_filter(tp, f);
307
308 /* Strip tree */
309
310 for (i=0; i<=32; i++)
311 if (b->ht[i])
312 return 0;
313
314 /* OK, session has no flows */
315 tcf_tree_lock(tp);
316 head->table[to_hash(h)] = NULL;
317 tcf_tree_unlock(tp);
318
319 kfree(b);
320 return 0;
321 }
322 }
323 return 0;
324}
325
326static int route4_set_parms(struct tcf_proto *tp, unsigned long base,
327 struct route4_filter *f, u32 handle, struct route4_head *head,
Patrick McHardyadd93b62008-01-22 22:11:33 -0800328 struct nlattr **tb, struct nlattr *est, int new)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700329{
330 int err;
331 u32 id = 0, to = 0, nhandle = 0x8000;
332 struct route4_filter *fp;
333 unsigned int h1;
334 struct route4_bucket *b;
335 struct tcf_exts e;
336
337 err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map);
338 if (err < 0)
339 return err;
340
341 err = -EINVAL;
Patrick McHardyadd93b62008-01-22 22:11:33 -0800342 if (tb[TCA_ROUTE4_CLASSID])
343 if (nla_len(tb[TCA_ROUTE4_CLASSID]) < sizeof(u32))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344 goto errout;
345
Patrick McHardyadd93b62008-01-22 22:11:33 -0800346 if (tb[TCA_ROUTE4_TO]) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700347 if (new && handle & 0x8000)
348 goto errout;
Patrick McHardyadd93b62008-01-22 22:11:33 -0800349 if (nla_len(tb[TCA_ROUTE4_TO]) < sizeof(u32))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350 goto errout;
Patrick McHardy1587bac2008-01-23 20:35:03 -0800351 to = nla_get_u32(tb[TCA_ROUTE4_TO]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700352 if (to > 0xFF)
353 goto errout;
354 nhandle = to;
355 }
356
Patrick McHardyadd93b62008-01-22 22:11:33 -0800357 if (tb[TCA_ROUTE4_FROM]) {
358 if (tb[TCA_ROUTE4_IIF])
Linus Torvalds1da177e2005-04-16 15:20:36 -0700359 goto errout;
Patrick McHardyadd93b62008-01-22 22:11:33 -0800360 if (nla_len(tb[TCA_ROUTE4_FROM]) < sizeof(u32))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700361 goto errout;
Patrick McHardy1587bac2008-01-23 20:35:03 -0800362 id = nla_get_u32(tb[TCA_ROUTE4_FROM]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700363 if (id > 0xFF)
364 goto errout;
365 nhandle |= id << 16;
Patrick McHardyadd93b62008-01-22 22:11:33 -0800366 } else if (tb[TCA_ROUTE4_IIF]) {
367 if (nla_len(tb[TCA_ROUTE4_IIF]) < sizeof(u32))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700368 goto errout;
Patrick McHardy1587bac2008-01-23 20:35:03 -0800369 id = nla_get_u32(tb[TCA_ROUTE4_IIF]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700370 if (id > 0x7FFF)
371 goto errout;
372 nhandle |= (id | 0x8000) << 16;
373 } else
374 nhandle |= 0xFFFF << 16;
375
376 if (handle && new) {
377 nhandle |= handle & 0x7F00;
378 if (nhandle != handle)
379 goto errout;
380 }
381
382 h1 = to_hash(nhandle);
383 if ((b = head->table[h1]) == NULL) {
384 err = -ENOBUFS;
Panagiotis Issaris0da974f2006-07-21 14:51:30 -0700385 b = kzalloc(sizeof(struct route4_bucket), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700386 if (b == NULL)
387 goto errout;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388
389 tcf_tree_lock(tp);
390 head->table[h1] = b;
391 tcf_tree_unlock(tp);
392 } else {
393 unsigned int h2 = from_hash(nhandle >> 16);
394 err = -EEXIST;
395 for (fp = b->ht[h2]; fp; fp = fp->next)
396 if (fp->handle == f->handle)
397 goto errout;
398 }
399
400 tcf_tree_lock(tp);
Patrick McHardyadd93b62008-01-22 22:11:33 -0800401 if (tb[TCA_ROUTE4_TO])
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402 f->id = to;
403
Patrick McHardyadd93b62008-01-22 22:11:33 -0800404 if (tb[TCA_ROUTE4_FROM])
Linus Torvalds1da177e2005-04-16 15:20:36 -0700405 f->id = to | id<<16;
Patrick McHardyadd93b62008-01-22 22:11:33 -0800406 else if (tb[TCA_ROUTE4_IIF])
Linus Torvalds1da177e2005-04-16 15:20:36 -0700407 f->iif = id;
408
409 f->handle = nhandle;
410 f->bkt = b;
411 tcf_tree_unlock(tp);
412
Patrick McHardyadd93b62008-01-22 22:11:33 -0800413 if (tb[TCA_ROUTE4_CLASSID]) {
Patrick McHardy1587bac2008-01-23 20:35:03 -0800414 f->res.classid = nla_get_u32(tb[TCA_ROUTE4_CLASSID]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700415 tcf_bind_filter(tp, &f->res, base);
416 }
417
418 tcf_exts_change(tp, &f->exts, &e);
419
420 return 0;
421errout:
422 tcf_exts_destroy(tp, &e);
423 return err;
424}
425
426static int route4_change(struct tcf_proto *tp, unsigned long base,
427 u32 handle,
Patrick McHardyadd93b62008-01-22 22:11:33 -0800428 struct nlattr **tca,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700429 unsigned long *arg)
430{
431 struct route4_head *head = tp->root;
432 struct route4_filter *f, *f1, **fp;
433 struct route4_bucket *b;
Patrick McHardyadd93b62008-01-22 22:11:33 -0800434 struct nlattr *opt = tca[TCA_OPTIONS];
435 struct nlattr *tb[TCA_ROUTE4_MAX + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700436 unsigned int h, th;
437 u32 old_handle = 0;
438 int err;
439
440 if (opt == NULL)
441 return handle ? -EINVAL : 0;
442
Patrick McHardycee63722008-01-23 20:33:32 -0800443 err = nla_parse_nested(tb, TCA_ROUTE4_MAX, opt, NULL);
444 if (err < 0)
445 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700446
447 if ((f = (struct route4_filter*)*arg) != NULL) {
448 if (f->handle != handle && handle)
449 return -EINVAL;
450
451 if (f->bkt)
452 old_handle = f->handle;
453
454 err = route4_set_parms(tp, base, f, handle, head, tb,
Patrick McHardyadd93b62008-01-22 22:11:33 -0800455 tca[TCA_RATE], 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700456 if (err < 0)
457 return err;
458
459 goto reinsert;
460 }
461
462 err = -ENOBUFS;
463 if (head == NULL) {
Panagiotis Issaris0da974f2006-07-21 14:51:30 -0700464 head = kzalloc(sizeof(struct route4_head), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465 if (head == NULL)
466 goto errout;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467
468 tcf_tree_lock(tp);
469 tp->root = head;
470 tcf_tree_unlock(tp);
471 }
472
Panagiotis Issaris0da974f2006-07-21 14:51:30 -0700473 f = kzalloc(sizeof(struct route4_filter), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700474 if (f == NULL)
475 goto errout;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700476
477 err = route4_set_parms(tp, base, f, handle, head, tb,
Patrick McHardyadd93b62008-01-22 22:11:33 -0800478 tca[TCA_RATE], 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700479 if (err < 0)
480 goto errout;
481
482reinsert:
483 h = from_hash(f->handle >> 16);
484 for (fp = &f->bkt->ht[h]; (f1=*fp) != NULL; fp = &f1->next)
485 if (f->handle < f1->handle)
486 break;
487
488 f->next = f1;
489 tcf_tree_lock(tp);
490 *fp = f;
491
492 if (old_handle && f->handle != old_handle) {
493 th = to_hash(old_handle);
494 h = from_hash(old_handle >> 16);
495 if ((b = head->table[th]) != NULL) {
496 for (fp = &b->ht[h]; *fp; fp = &(*fp)->next) {
497 if (*fp == f) {
498 *fp = f->next;
499 break;
500 }
501 }
502 }
503 }
504 tcf_tree_unlock(tp);
505
506 route4_reset_fastmap(tp->q->dev, head, f->id);
507 *arg = (unsigned long)f;
508 return 0;
509
510errout:
Jesper Juhla51482b2005-11-08 09:41:34 -0800511 kfree(f);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512 return err;
513}
514
515static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
516{
517 struct route4_head *head = tp->root;
518 unsigned h, h1;
519
520 if (head == NULL)
521 arg->stop = 1;
522
523 if (arg->stop)
524 return;
525
526 for (h = 0; h <= 256; h++) {
527 struct route4_bucket *b = head->table[h];
528
529 if (b) {
530 for (h1 = 0; h1 <= 32; h1++) {
531 struct route4_filter *f;
532
533 for (f = b->ht[h1]; f; f = f->next) {
534 if (arg->count < arg->skip) {
535 arg->count++;
536 continue;
537 }
538 if (arg->fn(tp, (unsigned long)f, arg) < 0) {
539 arg->stop = 1;
540 return;
541 }
542 arg->count++;
543 }
544 }
545 }
546 }
547}
548
549static int route4_dump(struct tcf_proto *tp, unsigned long fh,
550 struct sk_buff *skb, struct tcmsg *t)
551{
552 struct route4_filter *f = (struct route4_filter*)fh;
Arnaldo Carvalho de Melo27a884d2007-04-19 20:29:13 -0700553 unsigned char *b = skb_tail_pointer(skb);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -0800554 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700555 u32 id;
556
557 if (f == NULL)
558 return skb->len;
559
560 t->tcm_handle = f->handle;
561
Patrick McHardy4b3550ef2008-01-23 20:34:11 -0800562 nest = nla_nest_start(skb, TCA_OPTIONS);
563 if (nest == NULL)
564 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700565
566 if (!(f->handle&0x8000)) {
567 id = f->id&0xFF;
Patrick McHardy24beeab2008-01-23 20:34:48 -0800568 NLA_PUT_U32(skb, TCA_ROUTE4_TO, id);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700569 }
570 if (f->handle&0x80000000) {
571 if ((f->handle>>16) != 0xFFFF)
Patrick McHardy24beeab2008-01-23 20:34:48 -0800572 NLA_PUT_U32(skb, TCA_ROUTE4_IIF, f->iif);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700573 } else {
574 id = f->id>>16;
Patrick McHardy24beeab2008-01-23 20:34:48 -0800575 NLA_PUT_U32(skb, TCA_ROUTE4_FROM, id);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700576 }
577 if (f->res.classid)
Patrick McHardy24beeab2008-01-23 20:34:48 -0800578 NLA_PUT_U32(skb, TCA_ROUTE4_CLASSID, f->res.classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700579
580 if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
Patrick McHardyadd93b62008-01-22 22:11:33 -0800581 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700582
Patrick McHardy4b3550ef2008-01-23 20:34:11 -0800583 nla_nest_end(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700584
585 if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0)
Patrick McHardyadd93b62008-01-22 22:11:33 -0800586 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700587
588 return skb->len;
589
Patrick McHardyadd93b62008-01-22 22:11:33 -0800590nla_put_failure:
Arnaldo Carvalho de Melodc5fc572007-03-25 23:06:12 -0700591 nlmsg_trim(skb, b);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700592 return -1;
593}
594
Patrick McHardy2eb9d752008-01-22 22:10:42 -0800595static struct tcf_proto_ops cls_route4_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700596 .kind = "route",
597 .classify = route4_classify,
598 .init = route4_init,
599 .destroy = route4_destroy,
600 .get = route4_get,
601 .put = route4_put,
602 .change = route4_change,
603 .delete = route4_delete,
604 .walk = route4_walk,
605 .dump = route4_dump,
606 .owner = THIS_MODULE,
607};
608
609static int __init init_route4(void)
610{
611 return register_tcf_proto_ops(&cls_route4_ops);
612}
613
614static void __exit exit_route4(void)
615{
616 unregister_tcf_proto_ops(&cls_route4_ops);
617}
618
619module_init(init_route4)
620module_exit(exit_route4)
621MODULE_LICENSE("GPL");