2 * net/sched/cls_tcindex.c Packet classifier for skb->tc_index
4 * Written 1998,1999 by Werner Almesberger, EPFL ICA
7 #include <linux/module.h>
8 #include <linux/types.h>
9 #include <linux/kernel.h>
10 #include <linux/skbuff.h>
11 #include <linux/errno.h>
12 #include <net/act_api.h>
13 #include <net/netlink.h>
14 #include <net/pkt_cls.h>
17 * Passing parameters to the root seems to be done more awkwardly than really
18 * necessary. At least, u32 doesn't seem to use such dirty hacks. To be
22 #define PERFECT_HASH_THRESHOLD 64 /* use perfect hash if not bigger */
23 #define DEFAULT_HASH_SIZE 64 /* optimized for diffserv */
26 #define PRIV(tp) ((struct tcindex_data *) (tp)->root)
29 struct tcindex_filter_result
{
31 struct tcf_result res
;
34 struct tcindex_filter
{
36 struct tcindex_filter_result result
;
37 struct tcindex_filter
*next
;
42 struct tcindex_filter_result
*perfect
; /* perfect hash; NULL if none */
43 struct tcindex_filter
**h
; /* imperfect hash; only used if !perfect;
45 u16 mask
; /* AND key with mask */
46 int shift
; /* shift ANDed key to the right */
47 int hash
; /* hash table size; 0 if undefined */
48 int alloc_hash
; /* allocated size */
49 int fall_through
; /* 0: only classify if explicit match */
52 static const struct tcf_ext_map tcindex_ext_map
= {
53 .police
= TCA_TCINDEX_POLICE
,
54 .action
= TCA_TCINDEX_ACT
58 tcindex_filter_is_set(struct tcindex_filter_result
*r
)
60 return tcf_exts_is_predicative(&r
->exts
) || r
->res
.classid
;
63 static struct tcindex_filter_result
*
64 tcindex_lookup(struct tcindex_data
*p
, u16 key
)
66 struct tcindex_filter
*f
;
69 return tcindex_filter_is_set(p
->perfect
+ key
) ?
70 p
->perfect
+ key
: NULL
;
72 for (f
= p
->h
[key
% p
->hash
]; f
; f
= f
->next
)
81 static int tcindex_classify(struct sk_buff
*skb
, struct tcf_proto
*tp
,
82 struct tcf_result
*res
)
84 struct tcindex_data
*p
= PRIV(tp
);
85 struct tcindex_filter_result
*f
;
86 int key
= (skb
->tc_index
& p
->mask
) >> p
->shift
;
88 pr_debug("tcindex_classify(skb %p,tp %p,res %p),p %p\n",
91 f
= tcindex_lookup(p
, key
);
95 res
->classid
= TC_H_MAKE(TC_H_MAJ(tp
->q
->handle
), key
);
97 pr_debug("alg 0x%x\n", res
->classid
);
101 pr_debug("map 0x%x\n", res
->classid
);
103 return tcf_exts_exec(skb
, &f
->exts
, res
);
107 static unsigned long tcindex_get(struct tcf_proto
*tp
, u32 handle
)
109 struct tcindex_data
*p
= PRIV(tp
);
110 struct tcindex_filter_result
*r
;
112 pr_debug("tcindex_get(tp %p,handle 0x%08x)\n", tp
, handle
);
113 if (p
->perfect
&& handle
>= p
->alloc_hash
)
115 r
= tcindex_lookup(p
, handle
);
116 return r
&& tcindex_filter_is_set(r
) ? (unsigned long) r
: 0UL;
120 static void tcindex_put(struct tcf_proto
*tp
, unsigned long f
)
122 pr_debug("tcindex_put(tp %p,f 0x%lx)\n", tp
, f
);
126 static int tcindex_init(struct tcf_proto
*tp
)
128 struct tcindex_data
*p
;
130 pr_debug("tcindex_init(tp %p)\n", tp
);
131 p
= kzalloc(sizeof(struct tcindex_data
), GFP_KERNEL
);
136 p
->hash
= DEFAULT_HASH_SIZE
;
145 __tcindex_delete(struct tcf_proto
*tp
, unsigned long arg
, int lock
)
147 struct tcindex_data
*p
= PRIV(tp
);
148 struct tcindex_filter_result
*r
= (struct tcindex_filter_result
*) arg
;
149 struct tcindex_filter
*f
= NULL
;
151 pr_debug("tcindex_delete(tp %p,arg 0x%lx),p %p,f %p\n", tp
, arg
, p
, f
);
157 struct tcindex_filter
**walk
= NULL
;
159 for (i
= 0; i
< p
->hash
; i
++)
160 for (walk
= p
->h
+i
; *walk
; walk
= &(*walk
)->next
)
161 if (&(*walk
)->result
== r
)
173 tcf_unbind_filter(tp
, &r
->res
);
174 tcf_exts_destroy(tp
, &r
->exts
);
179 static int tcindex_delete(struct tcf_proto
*tp
, unsigned long arg
)
181 return __tcindex_delete(tp
, arg
, 1);
185 valid_perfect_hash(struct tcindex_data
*p
)
187 return p
->hash
> (p
->mask
>> p
->shift
);
190 static const struct nla_policy tcindex_policy
[TCA_TCINDEX_MAX
+ 1] = {
191 [TCA_TCINDEX_HASH
] = { .type
= NLA_U32
},
192 [TCA_TCINDEX_MASK
] = { .type
= NLA_U16
},
193 [TCA_TCINDEX_SHIFT
] = { .type
= NLA_U32
},
194 [TCA_TCINDEX_FALL_THROUGH
] = { .type
= NLA_U32
},
195 [TCA_TCINDEX_CLASSID
] = { .type
= NLA_U32
},
199 tcindex_set_parms(struct tcf_proto
*tp
, unsigned long base
, u32 handle
,
200 struct tcindex_data
*p
, struct tcindex_filter_result
*r
,
201 struct nlattr
**tb
, struct nlattr
*est
)
204 struct tcindex_filter_result new_filter_result
, *old_r
= r
;
205 struct tcindex_filter_result cr
;
206 struct tcindex_data cp
;
207 struct tcindex_filter
*f
= NULL
; /* make gcc behave */
210 err
= tcf_exts_validate(tp
, tb
, est
, &e
, &tcindex_ext_map
);
214 memcpy(&cp
, p
, sizeof(cp
));
215 memset(&new_filter_result
, 0, sizeof(new_filter_result
));
218 memcpy(&cr
, r
, sizeof(cr
));
220 memset(&cr
, 0, sizeof(cr
));
222 if (tb
[TCA_TCINDEX_HASH
])
223 cp
.hash
= nla_get_u32(tb
[TCA_TCINDEX_HASH
]);
225 if (tb
[TCA_TCINDEX_MASK
])
226 cp
.mask
= nla_get_u16(tb
[TCA_TCINDEX_MASK
]);
228 if (tb
[TCA_TCINDEX_SHIFT
])
229 cp
.shift
= nla_get_u32(tb
[TCA_TCINDEX_SHIFT
]);
232 /* Hash already allocated, make sure that we still meet the
233 * requirements for the allocated hash.
236 if (!valid_perfect_hash(&cp
) ||
237 cp
.hash
> cp
.alloc_hash
)
239 } else if (cp
.h
&& cp
.hash
!= cp
.alloc_hash
)
243 if (tb
[TCA_TCINDEX_FALL_THROUGH
])
244 cp
.fall_through
= nla_get_u32(tb
[TCA_TCINDEX_FALL_THROUGH
]);
247 /* Hash not specified, use perfect hash if the upper limit
248 * of the hashing index is below the threshold.
250 if ((cp
.mask
>> cp
.shift
) < PERFECT_HASH_THRESHOLD
)
251 cp
.hash
= (cp
.mask
>> cp
.shift
)+1;
253 cp
.hash
= DEFAULT_HASH_SIZE
;
256 if (!cp
.perfect
&& !cp
.h
)
257 cp
.alloc_hash
= cp
.hash
;
259 /* Note: this could be as restrictive as if (handle & ~(mask >> shift))
260 * but then, we'd fail handles that may become valid after some future
261 * mask change. While this is extremely unlikely to ever matter,
262 * the check below is safer (and also more backwards-compatible).
264 if (cp
.perfect
|| valid_perfect_hash(&cp
))
265 if (handle
>= cp
.alloc_hash
)
270 if (!cp
.perfect
&& !cp
.h
) {
271 if (valid_perfect_hash(&cp
)) {
272 cp
.perfect
= kcalloc(cp
.hash
, sizeof(*r
), GFP_KERNEL
);
277 cp
.h
= kcalloc(cp
.hash
, sizeof(f
), GFP_KERNEL
);
285 r
= cp
.perfect
+ handle
;
287 r
= tcindex_lookup(&cp
, handle
) ? : &new_filter_result
;
289 if (r
== &new_filter_result
) {
290 f
= kzalloc(sizeof(*f
), GFP_KERNEL
);
295 if (tb
[TCA_TCINDEX_CLASSID
]) {
296 cr
.res
.classid
= nla_get_u32(tb
[TCA_TCINDEX_CLASSID
]);
297 tcf_bind_filter(tp
, &cr
.res
, base
);
300 tcf_exts_change(tp
, &cr
.exts
, &e
);
303 if (old_r
&& old_r
!= r
)
304 memset(old_r
, 0, sizeof(*old_r
));
306 memcpy(p
, &cp
, sizeof(cp
));
307 memcpy(r
, &cr
, sizeof(cr
));
309 if (r
== &new_filter_result
) {
310 struct tcindex_filter
**fp
;
313 f
->result
= new_filter_result
;
315 for (fp
= p
->h
+(handle
% p
->hash
); *fp
; fp
= &(*fp
)->next
)
326 else if (balloc
== 2)
329 tcf_exts_destroy(tp
, &e
);
334 tcindex_change(struct tcf_proto
*tp
, unsigned long base
, u32 handle
,
335 struct nlattr
**tca
, unsigned long *arg
)
337 struct nlattr
*opt
= tca
[TCA_OPTIONS
];
338 struct nlattr
*tb
[TCA_TCINDEX_MAX
+ 1];
339 struct tcindex_data
*p
= PRIV(tp
);
340 struct tcindex_filter_result
*r
= (struct tcindex_filter_result
*) *arg
;
343 pr_debug("tcindex_change(tp %p,handle 0x%08x,tca %p,arg %p),opt %p,"
344 "p %p,r %p,*arg 0x%lx\n",
345 tp
, handle
, tca
, arg
, opt
, p
, r
, arg
? *arg
: 0L);
350 err
= nla_parse_nested(tb
, TCA_TCINDEX_MAX
, opt
, tcindex_policy
);
354 return tcindex_set_parms(tp
, base
, handle
, p
, r
, tb
, tca
[TCA_RATE
]);
358 static void tcindex_walk(struct tcf_proto
*tp
, struct tcf_walker
*walker
)
360 struct tcindex_data
*p
= PRIV(tp
);
361 struct tcindex_filter
*f
, *next
;
364 pr_debug("tcindex_walk(tp %p,walker %p),p %p\n", tp
, walker
, p
);
366 for (i
= 0; i
< p
->hash
; i
++) {
367 if (!p
->perfect
[i
].res
.class)
369 if (walker
->count
>= walker
->skip
) {
371 (unsigned long) (p
->perfect
+i
), walker
)
382 for (i
= 0; i
< p
->hash
; i
++) {
383 for (f
= p
->h
[i
]; f
; f
= next
) {
385 if (walker
->count
>= walker
->skip
) {
386 if (walker
->fn(tp
, (unsigned long) &f
->result
,
398 static int tcindex_destroy_element(struct tcf_proto
*tp
,
399 unsigned long arg
, struct tcf_walker
*walker
)
401 return __tcindex_delete(tp
, arg
, 0);
405 static void tcindex_destroy(struct tcf_proto
*tp
)
407 struct tcindex_data
*p
= PRIV(tp
);
408 struct tcf_walker walker
;
410 pr_debug("tcindex_destroy(tp %p),p %p\n", tp
, p
);
413 walker
.fn
= &tcindex_destroy_element
;
414 tcindex_walk(tp
, &walker
);
422 static int tcindex_dump(struct tcf_proto
*tp
, unsigned long fh
,
423 struct sk_buff
*skb
, struct tcmsg
*t
)
425 struct tcindex_data
*p
= PRIV(tp
);
426 struct tcindex_filter_result
*r
= (struct tcindex_filter_result
*) fh
;
427 unsigned char *b
= skb_tail_pointer(skb
);
430 pr_debug("tcindex_dump(tp %p,fh 0x%lx,skb %p,t %p),p %p,r %p,b %p\n",
431 tp
, fh
, skb
, t
, p
, r
, b
);
432 pr_debug("p->perfect %p p->h %p\n", p
->perfect
, p
->h
);
434 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
436 goto nla_put_failure
;
439 t
->tcm_handle
= ~0; /* whatever ... */
440 NLA_PUT_U32(skb
, TCA_TCINDEX_HASH
, p
->hash
);
441 NLA_PUT_U16(skb
, TCA_TCINDEX_MASK
, p
->mask
);
442 NLA_PUT_U32(skb
, TCA_TCINDEX_SHIFT
, p
->shift
);
443 NLA_PUT_U32(skb
, TCA_TCINDEX_FALL_THROUGH
, p
->fall_through
);
444 nla_nest_end(skb
, nest
);
447 t
->tcm_handle
= r
-p
->perfect
;
449 struct tcindex_filter
*f
;
453 for (i
= 0; !t
->tcm_handle
&& i
< p
->hash
; i
++) {
454 for (f
= p
->h
[i
]; !t
->tcm_handle
&& f
;
457 t
->tcm_handle
= f
->key
;
461 pr_debug("handle = %d\n", t
->tcm_handle
);
463 NLA_PUT_U32(skb
, TCA_TCINDEX_CLASSID
, r
->res
.classid
);
465 if (tcf_exts_dump(skb
, &r
->exts
, &tcindex_ext_map
) < 0)
466 goto nla_put_failure
;
467 nla_nest_end(skb
, nest
);
469 if (tcf_exts_dump_stats(skb
, &r
->exts
, &tcindex_ext_map
) < 0)
470 goto nla_put_failure
;
480 static struct tcf_proto_ops cls_tcindex_ops __read_mostly
= {
482 .classify
= tcindex_classify
,
483 .init
= tcindex_init
,
484 .destroy
= tcindex_destroy
,
487 .change
= tcindex_change
,
488 .delete = tcindex_delete
,
489 .walk
= tcindex_walk
,
490 .dump
= tcindex_dump
,
491 .owner
= THIS_MODULE
,
494 static int __init
init_tcindex(void)
496 return register_tcf_proto_ops(&cls_tcindex_ops
);
499 static void __exit
exit_tcindex(void)
501 unregister_tcf_proto_ops(&cls_tcindex_ops
);
504 module_init(init_tcindex
)
505 module_exit(exit_tcindex
)
506 MODULE_LICENSE("GPL");