cls_route.c (f43dc23d5ea91fca257be02138a255f02d98e806) cls_route.c (cc7ec456f82da7f89a5b376e613b3ac4311b3e9a)
1/*
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 unchanged lines hidden (view full) ---

18#include <linux/skbuff.h>
19#include <net/dst.h>
20#include <net/route.h>
21#include <net/netlink.h>
22#include <net/act_api.h>
23#include <net/pkt_cls.h>
24
25/*
1/*
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 unchanged lines hidden (view full) ---

18#include <linux/skbuff.h>
19#include <net/dst.h>
20#include <net/route.h>
21#include <net/netlink.h>
22#include <net/act_api.h>
23#include <net/pkt_cls.h>
24
25/*
26 1. For now we assume that route tags < 256.
27 It allows to use direct table lookups, instead of hash tables.
28 2. For now we assume that "from TAG" and "fromdev DEV" statements
29 are mutually exclusive.
30 3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
26 * 1. For now we assume that route tags < 256.
27 * It allows to use direct table lookups, instead of hash tables.
28 * 2. For now we assume that "from TAG" and "fromdev DEV" statements
29 * are mutually exclusive.
30 * 3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
31 */
32
31 */
32
33struct route4_fastmap
34{
33struct route4_fastmap {
35 struct route4_filter *filter;
36 u32 id;
37 int iif;
38};
39
34 struct route4_filter *filter;
35 u32 id;
36 int iif;
37};
38
40struct route4_head
41{
39struct route4_head {
42 struct route4_fastmap fastmap[16];
40 struct route4_fastmap fastmap[16];
43 struct route4_bucket *table[256+1];
41 struct route4_bucket *table[256 + 1];
44};
45
42};
43
46struct route4_bucket
47{
44struct route4_bucket {
48 /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
45 /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
49 struct route4_filter *ht[16+16+1];
46 struct route4_filter *ht[16 + 16 + 1];
50};
51
47};
48
52struct route4_filter
53{
49struct route4_filter {
54 struct route4_filter *next;
55 u32 id;
56 int iif;
57
58 struct tcf_result res;
59 struct tcf_exts exts;
60 u32 handle;
61 struct route4_bucket *bkt;
62};
63
50 struct route4_filter *next;
51 u32 id;
52 int iif;
53
54 struct tcf_result res;
55 struct tcf_exts exts;
56 u32 handle;
57 struct route4_bucket *bkt;
58};
59
64#define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
60#define ROUTE4_FAILURE ((struct route4_filter *)(-1L))
65
66static const struct tcf_ext_map route_ext_map = {
67 .police = TCA_ROUTE4_POLICE,
68 .action = TCA_ROUTE4_ACT
69};
70
61
62static const struct tcf_ext_map route_ext_map = {
63 .police = TCA_ROUTE4_POLICE,
64 .action = TCA_ROUTE4_ACT
65};
66
71static __inline__ int route4_fastmap_hash(u32 id, int iif)
67static inline int route4_fastmap_hash(u32 id, int iif)
72{
68{
73 return id&0xF;
69 return id & 0xF;
74}
75
70}
71
76static inline
77void route4_reset_fastmap(struct Qdisc *q, struct route4_head *head, u32 id)
72static void
73route4_reset_fastmap(struct Qdisc *q, struct route4_head *head, u32 id)
78{
79 spinlock_t *root_lock = qdisc_root_sleeping_lock(q);
80
81 spin_lock_bh(root_lock);
82 memset(head->fastmap, 0, sizeof(head->fastmap));
83 spin_unlock_bh(root_lock);
84}
85
74{
75 spinlock_t *root_lock = qdisc_root_sleeping_lock(q);
76
77 spin_lock_bh(root_lock);
78 memset(head->fastmap, 0, sizeof(head->fastmap));
79 spin_unlock_bh(root_lock);
80}
81
86static inline void
82static void
87route4_set_fastmap(struct route4_head *head, u32 id, int iif,
88 struct route4_filter *f)
89{
90 int h = route4_fastmap_hash(id, iif);
83route4_set_fastmap(struct route4_head *head, u32 id, int iif,
84 struct route4_filter *f)
85{
86 int h = route4_fastmap_hash(id, iif);
87
91 head->fastmap[h].id = id;
92 head->fastmap[h].iif = iif;
93 head->fastmap[h].filter = f;
94}
95
88 head->fastmap[h].id = id;
89 head->fastmap[h].iif = iif;
90 head->fastmap[h].filter = f;
91}
92
96static __inline__ int route4_hash_to(u32 id)
93static inline int route4_hash_to(u32 id)
97{
94{
98 return id&0xFF;
95 return id & 0xFF;
99}
100
96}
97
101static __inline__ int route4_hash_from(u32 id)
98static inline int route4_hash_from(u32 id)
102{
99{
103 return (id>>16)&0xF;
100 return (id >> 16) & 0xF;
104}
105
101}
102
106static __inline__ int route4_hash_iif(int iif)
103static inline int route4_hash_iif(int iif)
107{
104{
108 return 16 + ((iif>>16)&0xF);
105 return 16 + ((iif >> 16) & 0xF);
109}
110
106}
107
111static __inline__ int route4_hash_wild(void)
108static inline int route4_hash_wild(void)
112{
113 return 32;
114}
115
116#define ROUTE4_APPLY_RESULT() \
117{ \
118 *res = f->res; \
119 if (tcf_exts_is_available(&f->exts)) { \

--- 6 unchanged lines hidden (view full) ---

126 } else if (!dont_cache) \
127 route4_set_fastmap(head, id, iif, f); \
128 return 0; \
129}
130
131static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp,
132 struct tcf_result *res)
133{
109{
110 return 32;
111}
112
113#define ROUTE4_APPLY_RESULT() \
114{ \
115 *res = f->res; \
116 if (tcf_exts_is_available(&f->exts)) { \

--- 6 unchanged lines hidden (view full) ---

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{
134 struct route4_head *head = (struct route4_head*)tp->root;
131 struct route4_head *head = (struct route4_head *)tp->root;
135 struct dst_entry *dst;
136 struct route4_bucket *b;
137 struct route4_filter *f;
138 u32 id, h;
139 int iif, dont_cache = 0;
140
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
141 if ((dst = skb_dst(skb)) == NULL)
138 dst = skb_dst(skb);
139 if (!dst)
142 goto failure;
143
144 id = dst->tclassid;
145 if (head == NULL)
146 goto old_method;
147
140 goto failure;
141
142 id = dst->tclassid;
143 if (head == NULL)
144 goto old_method;
145
148 iif = ((struct rtable*)dst)->fl.iif;
146 iif = ((struct rtable *)dst)->fl.iif;
149
150 h = route4_fastmap_hash(id, iif);
151 if (id == head->fastmap[h].id &&
152 iif == head->fastmap[h].iif &&
153 (f = head->fastmap[h].filter) != NULL) {
154 if (f == ROUTE4_FAILURE)
155 goto failure;
156
157 *res = f->res;
158 return 0;
159 }
160
161 h = route4_hash_to(id);
162
163restart:
147
148 h = route4_fastmap_hash(id, iif);
149 if (id == head->fastmap[h].id &&
150 iif == head->fastmap[h].iif &&
151 (f = head->fastmap[h].filter) != NULL) {
152 if (f == ROUTE4_FAILURE)
153 goto failure;
154
155 *res = f->res;
156 return 0;
157 }
158
159 h = route4_hash_to(id);
160
161restart:
164 if ((b = head->table[h]) != NULL) {
162 b = head->table[h];
163 if (b) {
165 for (f = b->ht[route4_hash_from(id)]; f; f = f->next)
166 if (f->id == id)
167 ROUTE4_APPLY_RESULT();
168
169 for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)
170 if (f->iif == iif)
171 ROUTE4_APPLY_RESULT();
172

--- 19 unchanged lines hidden (view full) ---

192 res->class = 0;
193 return 0;
194 }
195 return -1;
196}
197
198static inline u32 to_hash(u32 id)
199{
164 for (f = b->ht[route4_hash_from(id)]; f; f = f->next)
165 if (f->id == id)
166 ROUTE4_APPLY_RESULT();
167
168 for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)
169 if (f->iif == iif)
170 ROUTE4_APPLY_RESULT();
171

--- 19 unchanged lines hidden (view full) ---

191 res->class = 0;
192 return 0;
193 }
194 return -1;
195}
196
197static inline u32 to_hash(u32 id)
198{
200 u32 h = id&0xFF;
201 if (id&0x8000)
199 u32 h = id & 0xFF;
200
201 if (id & 0x8000)
202 h += 256;
203 return h;
204}
205
206static inline u32 from_hash(u32 id)
207{
208 id &= 0xFFFF;
209 if (id == 0xFFFF)
210 return 32;
211 if (!(id & 0x8000)) {
212 if (id > 255)
213 return 256;
202 h += 256;
203 return h;
204}
205
206static inline u32 from_hash(u32 id)
207{
208 id &= 0xFFFF;
209 if (id == 0xFFFF)
210 return 32;
211 if (!(id & 0x8000)) {
212 if (id > 255)
213 return 256;
214 return id&0xF;
214 return id & 0xF;
215 }
215 }
216 return 16 + (id&0xF);
216 return 16 + (id & 0xF);
217}
218
219static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
220{
217}
218
219static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
220{
221 struct route4_head *head = (struct route4_head*)tp->root;
221 struct route4_head *head = (struct route4_head *)tp->root;
222 struct route4_bucket *b;
223 struct route4_filter *f;
222 struct route4_bucket *b;
223 struct route4_filter *f;
224 unsigned h1, h2;
224 unsigned int h1, h2;
225
226 if (!head)
227 return 0;
228
229 h1 = to_hash(handle);
230 if (h1 > 256)
231 return 0;
232
225
226 if (!head)
227 return 0;
228
229 h1 = to_hash(handle);
230 if (h1 > 256)
231 return 0;
232
233 h2 = from_hash(handle>>16);
233 h2 = from_hash(handle >> 16);
234 if (h2 > 32)
235 return 0;
236
234 if (h2 > 32)
235 return 0;
236
237 if ((b = head->table[h1]) != NULL) {
237 b = head->table[h1];
238 if (b) {
238 for (f = b->ht[h2]; f; f = f->next)
239 if (f->handle == handle)
240 return (unsigned long)f;
241 }
242 return 0;
243}
244
245static void route4_put(struct tcf_proto *tp, unsigned long f)
246{
247}
248
249static int route4_init(struct tcf_proto *tp)
250{
251 return 0;
252}
253
239 for (f = b->ht[h2]; f; f = f->next)
240 if (f->handle == handle)
241 return (unsigned long)f;
242 }
243 return 0;
244}
245
246static void route4_put(struct tcf_proto *tp, unsigned long f)
247{
248}
249
250static int route4_init(struct tcf_proto *tp)
251{
252 return 0;
253}
254
254static inline void
255static void
255route4_delete_filter(struct tcf_proto *tp, struct route4_filter *f)
256{
257 tcf_unbind_filter(tp, &f->res);
258 tcf_exts_destroy(tp, &f->exts);
259 kfree(f);
260}
261
262static void route4_destroy(struct tcf_proto *tp)
263{
264 struct route4_head *head = tp->root;
265 int h1, h2;
266
267 if (head == NULL)
268 return;
269
256route4_delete_filter(struct tcf_proto *tp, struct route4_filter *f)
257{
258 tcf_unbind_filter(tp, &f->res);
259 tcf_exts_destroy(tp, &f->exts);
260 kfree(f);
261}
262
263static void route4_destroy(struct tcf_proto *tp)
264{
265 struct route4_head *head = tp->root;
266 int h1, h2;
267
268 if (head == NULL)
269 return;
270
270 for (h1=0; h1<=256; h1++) {
271 for (h1 = 0; h1 <= 256; h1++) {
271 struct route4_bucket *b;
272
272 struct route4_bucket *b;
273
273 if ((b = head->table[h1]) != NULL) {
274 for (h2=0; h2<=32; h2++) {
274 b = head->table[h1];
275 if (b) {
276 for (h2 = 0; h2 <= 32; h2++) {
275 struct route4_filter *f;
276
277 while ((f = b->ht[h2]) != NULL) {
278 b->ht[h2] = f->next;
279 route4_delete_filter(tp, f);
280 }
281 }
282 kfree(b);
283 }
284 }
285 kfree(head);
286}
287
288static int route4_delete(struct tcf_proto *tp, unsigned long arg)
289{
277 struct route4_filter *f;
278
279 while ((f = b->ht[h2]) != NULL) {
280 b->ht[h2] = f->next;
281 route4_delete_filter(tp, f);
282 }
283 }
284 kfree(b);
285 }
286 }
287 kfree(head);
288}
289
290static int route4_delete(struct tcf_proto *tp, unsigned long arg)
291{
290 struct route4_head *head = (struct route4_head*)tp->root;
291 struct route4_filter **fp, *f = (struct route4_filter*)arg;
292 unsigned h = 0;
292 struct route4_head *head = (struct route4_head *)tp->root;
293 struct route4_filter **fp, *f = (struct route4_filter *)arg;
294 unsigned int h = 0;
293 struct route4_bucket *b;
294 int i;
295
296 if (!head || !f)
297 return -EINVAL;
298
299 h = f->handle;
300 b = f->bkt;
301
295 struct route4_bucket *b;
296 int i;
297
298 if (!head || !f)
299 return -EINVAL;
300
301 h = f->handle;
302 b = f->bkt;
303
302 for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {
304 for (fp = &b->ht[from_hash(h >> 16)]; *fp; fp = &(*fp)->next) {
303 if (*fp == f) {
304 tcf_tree_lock(tp);
305 *fp = f->next;
306 tcf_tree_unlock(tp);
307
308 route4_reset_fastmap(tp->q, head, f->id);
309 route4_delete_filter(tp, f);
310
311 /* Strip tree */
312
305 if (*fp == f) {
306 tcf_tree_lock(tp);
307 *fp = f->next;
308 tcf_tree_unlock(tp);
309
310 route4_reset_fastmap(tp->q, head, f->id);
311 route4_delete_filter(tp, f);
312
313 /* Strip tree */
314
313 for (i=0; i<=32; i++)
315 for (i = 0; i <= 32; i++)
314 if (b->ht[i])
315 return 0;
316
317 /* OK, session has no flows */
318 tcf_tree_lock(tp);
319 head->table[to_hash(h)] = NULL;
320 tcf_tree_unlock(tp);
321

--- 53 unchanged lines hidden (view full) ---

375
376 if (handle && new) {
377 nhandle |= handle & 0x7F00;
378 if (nhandle != handle)
379 goto errout;
380 }
381
382 h1 = to_hash(nhandle);
316 if (b->ht[i])
317 return 0;
318
319 /* OK, session has no flows */
320 tcf_tree_lock(tp);
321 head->table[to_hash(h)] = NULL;
322 tcf_tree_unlock(tp);
323

--- 53 unchanged lines hidden (view full) ---

377
378 if (handle && new) {
379 nhandle |= handle & 0x7F00;
380 if (nhandle != handle)
381 goto errout;
382 }
383
384 h1 = to_hash(nhandle);
383 if ((b = head->table[h1]) == NULL) {
385 b = head->table[h1];
386 if (!b) {
384 err = -ENOBUFS;
385 b = kzalloc(sizeof(struct route4_bucket), GFP_KERNEL);
386 if (b == NULL)
387 goto errout;
388
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);
387 err = -ENOBUFS;
388 b = kzalloc(sizeof(struct route4_bucket), GFP_KERNEL);
389 if (b == NULL)
390 goto errout;
391
392 tcf_tree_lock(tp);
393 head->table[h1] = b;
394 tcf_tree_unlock(tp);
395 } else {
396 unsigned int h2 = from_hash(nhandle >> 16);
397
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);
401 if (tb[TCA_ROUTE4_TO])

--- 37 unchanged lines hidden (view full) ---

439
440 if (opt == NULL)
441 return handle ? -EINVAL : 0;
442
443 err = nla_parse_nested(tb, TCA_ROUTE4_MAX, opt, route4_policy);
444 if (err < 0)
445 return err;
446
398 err = -EEXIST;
399 for (fp = b->ht[h2]; fp; fp = fp->next)
400 if (fp->handle == f->handle)
401 goto errout;
402 }
403
404 tcf_tree_lock(tp);
405 if (tb[TCA_ROUTE4_TO])

--- 37 unchanged lines hidden (view full) ---

443
444 if (opt == NULL)
445 return handle ? -EINVAL : 0;
446
447 err = nla_parse_nested(tb, TCA_ROUTE4_MAX, opt, route4_policy);
448 if (err < 0)
449 return err;
450
447 if ((f = (struct route4_filter*)*arg) != NULL) {
451 f = (struct route4_filter *)*arg;
452 if (f) {
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,
455 tca[TCA_RATE], 0);

--- 20 unchanged lines hidden (view full) ---

476
477 err = route4_set_parms(tp, base, f, handle, head, tb,
478 tca[TCA_RATE], 1);
479 if (err < 0)
480 goto errout;
481
482reinsert:
483 h = from_hash(f->handle >> 16);
453 if (f->handle != handle && handle)
454 return -EINVAL;
455
456 if (f->bkt)
457 old_handle = f->handle;
458
459 err = route4_set_parms(tp, base, f, handle, head, tb,
460 tca[TCA_RATE], 0);

--- 20 unchanged lines hidden (view full) ---

481
482 err = route4_set_parms(tp, base, f, handle, head, tb,
483 tca[TCA_RATE], 1);
484 if (err < 0)
485 goto errout;
486
487reinsert:
488 h = from_hash(f->handle >> 16);
484 for (fp = &f->bkt->ht[h]; (f1=*fp) != NULL; fp = &f1->next)
489 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);
490 if (f->handle < f1->handle)
491 break;
492
493 f->next = f1;
494 tcf_tree_lock(tp);
495 *fp = f;
496
497 if (old_handle && f->handle != old_handle) {
498 th = to_hash(old_handle);
499 h = from_hash(old_handle >> 16);
495 if ((b = head->table[th]) != NULL) {
500 b = head->table[th];
501 if (b) {
496 for (fp = &b->ht[h]; *fp; fp = &(*fp)->next) {
497 if (*fp == f) {
498 *fp = f->next;
499 break;
500 }
501 }
502 }
503 }

--- 6 unchanged lines hidden (view full) ---

510errout:
511 kfree(f);
512 return err;
513}
514
515static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
516{
517 struct route4_head *head = tp->root;
502 for (fp = &b->ht[h]; *fp; fp = &(*fp)->next) {
503 if (*fp == f) {
504 *fp = f->next;
505 break;
506 }
507 }
508 }
509 }

--- 6 unchanged lines hidden (view full) ---

516errout:
517 kfree(f);
518 return err;
519}
520
521static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
522{
523 struct route4_head *head = tp->root;
518 unsigned h, h1;
524 unsigned int 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++) {

--- 17 unchanged lines hidden (view full) ---

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{
525
526 if (head == NULL)
527 arg->stop = 1;
528
529 if (arg->stop)
530 return;
531
532 for (h = 0; h <= 256; h++) {

--- 17 unchanged lines hidden (view full) ---

550 }
551 }
552 }
553}
554
555static int route4_dump(struct tcf_proto *tp, unsigned long fh,
556 struct sk_buff *skb, struct tcmsg *t)
557{
552 struct route4_filter *f = (struct route4_filter*)fh;
558 struct route4_filter *f = (struct route4_filter *)fh;
553 unsigned char *b = skb_tail_pointer(skb);
554 struct nlattr *nest;
555 u32 id;
556
557 if (f == NULL)
558 return skb->len;
559
560 t->tcm_handle = f->handle;
561
562 nest = nla_nest_start(skb, TCA_OPTIONS);
563 if (nest == NULL)
564 goto nla_put_failure;
565
559 unsigned char *b = skb_tail_pointer(skb);
560 struct nlattr *nest;
561 u32 id;
562
563 if (f == NULL)
564 return skb->len;
565
566 t->tcm_handle = f->handle;
567
568 nest = nla_nest_start(skb, TCA_OPTIONS);
569 if (nest == NULL)
570 goto nla_put_failure;
571
566 if (!(f->handle&0x8000)) {
567 id = f->id&0xFF;
572 if (!(f->handle & 0x8000)) {
573 id = f->id & 0xFF;
568 NLA_PUT_U32(skb, TCA_ROUTE4_TO, id);
569 }
574 NLA_PUT_U32(skb, TCA_ROUTE4_TO, id);
575 }
570 if (f->handle&0x80000000) {
571 if ((f->handle>>16) != 0xFFFF)
576 if (f->handle & 0x80000000) {
577 if ((f->handle >> 16) != 0xFFFF)
572 NLA_PUT_U32(skb, TCA_ROUTE4_IIF, f->iif);
573 } else {
578 NLA_PUT_U32(skb, TCA_ROUTE4_IIF, f->iif);
579 } else {
574 id = f->id>>16;
580 id = f->id >> 16;
575 NLA_PUT_U32(skb, TCA_ROUTE4_FROM, id);
576 }
577 if (f->res.classid)
578 NLA_PUT_U32(skb, TCA_ROUTE4_CLASSID, f->res.classid);
579
580 if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
581 goto nla_put_failure;
582

--- 39 unchanged lines hidden --- 		581 NLA_PUT_U32(skb, TCA_ROUTE4_FROM, id);
582 }
583 if (f->res.classid)
584 NLA_PUT_U32(skb, TCA_ROUTE4_CLASSID, f->res.classid);
585
586 if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
587 goto nla_put_failure;
588

--- 39 unchanged lines hidden ---