1 /*
2 * net/sched/cls_tcindex.c Packet classifier for skb->tc_index
3 *
4 * Written 1998,1999 by Werner Almesberger, EPFL ICA
5 */
6
7 #include <linux/config.h>
8 #include <linux/module.h>
9 #include <linux/types.h>
10 #include <linux/kernel.h>
11 #include <linux/skbuff.h>
12 #include <linux/errno.h>
13 #include <linux/netdevice.h>
14 #include <net/ip.h>
15 #include <net/pkt_sched.h>
16 #include <net/route.h>
17
18
19 /*
20 * Not quite sure if we need all the xchgs Alexey uses when accessing things.
21 * Can always add them later ... :)
22 */
23
24 /*
25 * Passing parameters to the root seems to be done more awkwardly than really
26 * necessary. At least, u32 doesn't seem to use such dirty hacks. To be
27 * verified. FIXME.
28 */
29
30 #define PERFECT_HASH_THRESHOLD 64 /* use perfect hash if not bigger */
31 #define DEFAULT_HASH_SIZE 64 /* optimized for diffserv */
32
33
34 #if 1 /* control */
35 #define DPRINTK(format,args...) printk(KERN_DEBUG format,##args)
36 #else
37 #define DPRINTK(format,args...)
38 #endif
39
40 #if 0 /* data */
41 #define D2PRINTK(format,args...) printk(KERN_DEBUG format,##args)
42 #else
43 #define D2PRINTK(format,args...)
44 #endif
45
46
47 #define PRIV(tp) ((struct tcindex_data *) (tp)->root)
48
49
50 struct tcindex_filter_result {
51 struct tcf_police *police;
52 struct tcf_result res;
53 };
54
55 struct tcindex_filter {
56 __u16 key;
57 struct tcindex_filter_result result;
58 struct tcindex_filter *next;
59 };
60
61
62 struct tcindex_data {
63 struct tcindex_filter_result *perfect; /* perfect hash; NULL if none */
64 struct tcindex_filter **h; /* imperfect hash; only used if !perfect;
65 NULL if unused */
66 __u16 mask; /* AND key with mask */
67 int shift; /* shift ANDed key to the right */
68 int hash; /* hash table size; 0 if undefined */
69 int alloc_hash; /* allocated size */
70 int fall_through; /* 0: only classify if explicit match */
71 };
72
73
74 static struct tcindex_filter_result *lookup(struct tcindex_data *p,__u16 key)
75 {
76 struct tcindex_filter *f;
77
78 if (p->perfect)
79 return p->perfect[key].res.classid ? p->perfect+key : NULL;
80 if (!p->h)
81 return NULL;
82 for (f = p->h[key % p->hash]; f; f = f->next) {
83 if (f->key == key)
84 return &f->result;
85 }
86 return NULL;
87 }
88
89
90 static int tcindex_classify(struct sk_buff *skb, struct tcf_proto *tp,
91 struct tcf_result *res)
92 {
93 struct tcindex_data *p = PRIV(tp);
94 struct tcindex_filter_result *f;
95
96 D2PRINTK("tcindex_classify(skb %p,tp %p,res %p),p %p\n",skb,tp,res,p);
97
98 f = lookup(p,(skb->tc_index & p->mask) >> p->shift);
99 if (!f) {
100 if (!p->fall_through)
101 return -1;
102 res->classid = TC_H_MAKE(TC_H_MAJ(tp->q->handle),
103 (skb->tc_index& p->mask) >> p->shift);
104 res->class = 0;
105 D2PRINTK("alg 0x%x\n",res->classid);
106 return 0;
107 }
108 *res = f->res;
109 D2PRINTK("map 0x%x\n",res->classid);
110 #ifdef CONFIG_NET_CLS_POLICE
111 if (f->police) {
112 int result;
113
114 result = tcf_police(skb,f->police);
115 D2PRINTK("police %d\n",res);
116 return result;
117 }
118 #endif
119 return 0;
120 }
121
122
123 static unsigned long tcindex_get(struct tcf_proto *tp, u32 handle)
124 {
125 DPRINTK("tcindex_get(tp %p,handle 0x%08x)\n",tp,handle);
126 return (unsigned long) lookup(PRIV(tp),handle);
127 }
128
129
130 static void tcindex_put(struct tcf_proto *tp, unsigned long f)
131 {
132 DPRINTK("tcindex_put(tp %p,f 0x%lx)\n",tp,f);
133 }
134
135
136 static int tcindex_init(struct tcf_proto *tp)
137 {
138 struct tcindex_data *p;
139
140 DPRINTK("tcindex_init(tp %p)\n",tp);
141 MOD_INC_USE_COUNT;
142 p = kmalloc(sizeof(struct tcindex_data),GFP_KERNEL);
143 if (!p) {
144 MOD_DEC_USE_COUNT;
145 return -ENOMEM;
146 }
147 tp->root = p;
148 p->perfect = NULL;
149 p->h = NULL;
150 p->hash = 0;
151 p->mask = 0xffff;
152 p->shift = 0;
153 p->fall_through = 1;
154 return 0;
155 }
156
157
158 static int tcindex_delete(struct tcf_proto *tp, unsigned long arg)
159 {
160 struct tcindex_data *p = PRIV(tp);
161 struct tcindex_filter_result *r = (struct tcindex_filter_result *) arg;
162 struct tcindex_filter *f = NULL;
163 unsigned long cl;
164
165 DPRINTK("tcindex_delete(tp %p,arg 0x%lx),p %p,f %p\n",tp,arg,p,f);
166 if (p->perfect) {
167 if (!r->res.classid)
168 return -ENOENT;
169 } else {
170 int i;
171 struct tcindex_filter **walk = NULL;
172
173 for (i = 0; i < p->hash; i++)
174 for (walk = p->h+i; *walk; walk = &(*walk)->next)
175 if (&(*walk)->result == r)
176 goto found;
177 return -ENOENT;
178
179 found:
180 f = *walk;
181 tcf_tree_lock(tp);
182 *walk = f->next;
183 tcf_tree_unlock(tp);
184 }
185 cl = __cls_set_class(&r->res.class,0);
186 if (cl)
187 tp->q->ops->cl_ops->unbind_tcf(tp->q,cl);
188 #ifdef CONFIG_NET_CLS_POLICE
189 tcf_police_release(r->police);
190 #endif
191 if (f)
192 kfree(f);
193 return 0;
194 }
195
196
197 /*
198 * There are no parameters for tcindex_init, so we overload tcindex_change
199 */
200
201
202 static int tcindex_change(struct tcf_proto *tp,unsigned long base,u32 handle,
203 struct rtattr **tca,unsigned long *arg)
204 {
205 struct tcindex_filter_result new_filter_result = {
206 NULL, /* no policing */
207 { 0,0 }, /* no classification */
208 };
209 struct rtattr *opt = tca[TCA_OPTIONS-1];
210 struct rtattr *tb[TCA_TCINDEX_MAX];
211 struct tcindex_data *p = PRIV(tp);
212 struct tcindex_filter *f;
213 struct tcindex_filter_result *r = (struct tcindex_filter_result *) *arg;
214 struct tcindex_filter **walk;
215 int hash;
216 __u16 mask;
217
218 DPRINTK("tcindex_change(tp %p,handle 0x%08x,tca %p,arg %p),opt %p,"
219 "p %p,r %p\n",tp,handle,tca,arg,opt,p,r);
220 if (arg)
221 DPRINTK("*arg = 0x%lx\n",*arg);
222 if (!opt)
223 return 0;
224 if (rtattr_parse(tb,TCA_TCINDEX_MAX,RTA_DATA(opt),RTA_PAYLOAD(opt)) < 0)
225 return -EINVAL;
226 if (!tb[TCA_TCINDEX_HASH-1]) {
227 hash = p->hash;
228 } else {
229 if (RTA_PAYLOAD(tb[TCA_TCINDEX_HASH-1]) < sizeof(int))
230 return -EINVAL;
231 hash = *(int *) RTA_DATA(tb[TCA_TCINDEX_HASH-1]);
232 }
233 if (!tb[TCA_TCINDEX_MASK-1]) {
234 mask = p->mask;
235 } else {
236 if (RTA_PAYLOAD(tb[TCA_TCINDEX_MASK-1]) < sizeof(__u16))
237 return -EINVAL;
238 mask = *(__u16 *) RTA_DATA(tb[TCA_TCINDEX_MASK-1]);
239 }
240 if (p->perfect && hash <= mask)
241 return -EBUSY;
242 if ((p->perfect || p->h) && hash > p->alloc_hash)
243 return -EBUSY;
244 p->hash = hash;
245 p->mask = mask;
246 if (tb[TCA_TCINDEX_SHIFT-1]) {
247 if (RTA_PAYLOAD(tb[TCA_TCINDEX_SHIFT-1]) < sizeof(__u16))
248 return -EINVAL;
249 p->shift = *(int *) RTA_DATA(tb[TCA_TCINDEX_SHIFT-1]);
250 }
251 if (tb[TCA_TCINDEX_FALL_THROUGH-1]) {
252 if (RTA_PAYLOAD(tb[TCA_TCINDEX_FALL_THROUGH-1]) < sizeof(int))
253 return -EINVAL;
254 p->fall_through =
255 *(int *) RTA_DATA(tb[TCA_TCINDEX_FALL_THROUGH-1]);
256 }
257 DPRINTK("classid/police %p/%p\n",tb[TCA_TCINDEX_CLASSID-1],
258 tb[TCA_TCINDEX_POLICE-1]);
259 if (!tb[TCA_TCINDEX_CLASSID-1] && !tb[TCA_TCINDEX_POLICE-1])
260 return 0;
261 if (!p->hash) {
262 if (p->mask < PERFECT_HASH_THRESHOLD) {
263 p->hash = p->mask+1;
264 } else {
265 p->hash = DEFAULT_HASH_SIZE;
266 }
267 }
268 if (!p->perfect && !p->h) {
269 p->alloc_hash = p->hash;
270 DPRINTK("hash %d mask %d\n",p->hash,p->mask);
271 if (p->hash > p->mask) {
272 p->perfect = kmalloc(p->hash*
273 sizeof(struct tcindex_filter_result),GFP_KERNEL);
274 if (!p->perfect)
275 return -ENOMEM;
276 memset(p->perfect, 0,
277 p->hash * sizeof(struct tcindex_filter_result));
278 } else {
279 p->h = kmalloc(p->hash*sizeof(struct tcindex_filter *),
280 GFP_KERNEL);
281 if (!p->h)
282 return -ENOMEM;
283 memset(p->h, 0, p->hash*sizeof(struct tcindex_filter *));
284 }
285 }
286 if (handle > p->mask)
287 return -EINVAL;
288 if (p->perfect) {
289 r = p->perfect+handle;
290 } else {
291 r = lookup(p,handle);
292 DPRINTK("r=%p\n",r);
293 if (!r)
294 r = &new_filter_result;
295 }
296 DPRINTK("r=%p\n",r);
297 if (tb[TCA_TCINDEX_CLASSID-1]) {
298 unsigned long cl = cls_set_class(tp,&r->res.class,0);
299
300 if (cl)
301 tp->q->ops->cl_ops->unbind_tcf(tp->q,cl);
302 r->res.classid = *(__u32 *) RTA_DATA(tb[TCA_TCINDEX_CLASSID-1]);
303 r->res.class = tp->q->ops->cl_ops->bind_tcf(tp->q,base,
304 r->res.classid);
305 if (!r->res.class) {
306 r->res.classid = 0;
307 return -ENOENT;
308 }
309 }
310 #ifdef CONFIG_NET_CLS_POLICE
311 if (!tb[TCA_TCINDEX_POLICE-1]) {
312 r->police = NULL;
313 } else {
314 struct tcf_police *police =
315 tcf_police_locate(tb[TCA_TCINDEX_POLICE-1],NULL);
316
317 tcf_tree_lock(tp);
318 police = xchg(&r->police,police);
319 tcf_tree_unlock(tp);
320 tcf_police_release(police);
321 }
322 #endif
323 if (r != &new_filter_result)
324 return 0;
325 f = kmalloc(sizeof(struct tcindex_filter),GFP_KERNEL);
326 if (!f)
327 return -ENOMEM;
328 f->key = handle;
329 f->result = new_filter_result;
330 f->next = NULL;
331 for (walk = p->h+(handle % p->hash); *walk; walk = &(*walk)->next)
332 /* nothing */;
333 wmb();
334 *walk = f;
335 return 0;
336 }
337
338
339 static void tcindex_walk(struct tcf_proto *tp, struct tcf_walker *walker)
340 {
341 struct tcindex_data *p = PRIV(tp);
342 struct tcindex_filter *f;
343 int i;
344
345 DPRINTK("tcindex_walk(tp %p,walker %p),p %p\n",tp,walker,p);
346 if (p->perfect) {
347 for (i = 0; i < p->hash; i++) {
348 if (!p->perfect[i].res.classid)
349 continue;
350 if (walker->count >= walker->skip) {
351 if (walker->fn(tp,
352 (unsigned long) (p->perfect+i), walker)
353 < 0) {
354 walker->stop = 1;
355 return;
356 }
357 }
358 walker->count++;
359 }
360 }
361 if (!p->h)
362 return;
363 for (i = 0; i < p->hash; i++) {
364 for (f = p->h[i]; f; f = f->next) {
365 if (walker->count >= walker->skip) {
366 if (walker->fn(tp,(unsigned long) &f->result,
367 walker) < 0) {
368 walker->stop = 1;
369 return;
370 }
371 }
372 walker->count++;
373 }
374 }
375 }
376
377
378 static int tcindex_destroy_element(struct tcf_proto *tp,
379 unsigned long arg, struct tcf_walker *walker)
380 {
381 return tcindex_delete(tp,arg);
382 }
383
384
385 static void tcindex_destroy(struct tcf_proto *tp)
386 {
387 struct tcindex_data *p = PRIV(tp);
388 struct tcf_walker walker;
389
390 DPRINTK("tcindex_destroy(tp %p),p %p\n",tp,p);
391 walker.count = 0;
392 walker.skip = 0;
393 walker.fn = &tcindex_destroy_element;
394 tcindex_walk(tp,&walker);
395 if (p->perfect)
396 kfree(p->perfect);
397 if (p->h)
398 kfree(p->h);
399 kfree(p);
400 tp->root = NULL;
401 MOD_DEC_USE_COUNT;
402 }
403
404
405 #ifdef CONFIG_RTNETLINK
406
407 static int tcindex_dump(struct tcf_proto *tp, unsigned long fh,
408 struct sk_buff *skb, struct tcmsg *t)
409 {
410 struct tcindex_data *p = PRIV(tp);
411 struct tcindex_filter_result *r = (struct tcindex_filter_result *) fh;
412 unsigned char *b = skb->tail;
413 struct rtattr *rta;
414
415 DPRINTK("tcindex_dump(tp %p,fh 0x%lx,skb %p,t %p),p %p,r %p,b %p\n",
416 tp,fh,skb,t,p,r,b);
417 DPRINTK("p->perfect %p p->h %p\n",p->perfect,p->h);
418 rta = (struct rtattr *) b;
419 RTA_PUT(skb,TCA_OPTIONS,0,NULL);
420 if (!fh) {
421 t->tcm_handle = ~0; /* whatever ... */
422 RTA_PUT(skb,TCA_TCINDEX_HASH,sizeof(p->hash),&p->hash);
423 RTA_PUT(skb,TCA_TCINDEX_MASK,sizeof(p->mask),&p->mask);
424 RTA_PUT(skb,TCA_TCINDEX_SHIFT,sizeof(p->shift),&p->shift);
425 RTA_PUT(skb,TCA_TCINDEX_FALL_THROUGH,sizeof(p->fall_through),
426 &p->fall_through);
427 } else {
428 if (p->perfect) {
429 t->tcm_handle = r-p->perfect;
430 } else {
431 struct tcindex_filter *f;
432 int i;
433
434 t->tcm_handle = 0;
435 for (i = 0; !t->tcm_handle && i < p->hash; i++) {
436 for (f = p->h[i]; !t->tcm_handle && f;
437 f = f->next) {
438 if (&f->result == r)
439 t->tcm_handle = f->key;
440 }
441 }
442 }
443 DPRINTK("handle = %d\n",t->tcm_handle);
444 if (r->res.class)
445 RTA_PUT(skb, TCA_TCINDEX_CLASSID, 4, &r->res.classid);
446 #ifdef CONFIG_NET_CLS_POLICE
447 if (r->police) {
448 struct rtattr *p_rta = (struct rtattr *) skb->tail;
449
450 RTA_PUT(skb,TCA_TCINDEX_POLICE,0,NULL);
451 if (tcf_police_dump(skb,r->police) < 0)
452 goto rtattr_failure;
453 p_rta->rta_len = skb->tail-(u8 *) p_rta;
454 }
455 #endif
456 }
457 rta->rta_len = skb->tail-b;
458 return skb->len;
459
460 rtattr_failure:
461 skb_trim(skb, b - skb->data);
462 return -1;
463 }
464
465 #endif
466
467
468 struct tcf_proto_ops cls_tcindex_ops = {
469 NULL,
470 "tcindex",
471 tcindex_classify,
472 tcindex_init,
473 tcindex_destroy,
474
475 tcindex_get,
476 tcindex_put,
477 tcindex_change,
478 tcindex_delete,
479 tcindex_walk,
480 #ifdef CONFIG_RTNETLINK
481 tcindex_dump
482 #else
483 NULL
484 #endif
485 };
486
487
488 #ifdef MODULE
489 int init_module(void)
490 {
491 return register_tcf_proto_ops(&cls_tcindex_ops);
492 }
493
494 void cleanup_module(void)
495 {
496 unregister_tcf_proto_ops(&cls_tcindex_ops);
497 }
498 #endif
499
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.