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 <linux/slab.h>
13 #include <net/act_api.h>
14 #include <net/netlink.h>
15 #include <net/pkt_cls.h>
18 #define PERFECT_HASH_THRESHOLD 64 /* use perfect hash if not bigger */
19 #define DEFAULT_HASH_SIZE 64 /* optimized for diffserv */
22 #define PRIV(tp) ((struct tcindex_data *) (tp)->root)
25 struct tcindex_filter_result
{
27 struct tcf_result res
;
30 struct tcindex_filter
{
32 struct tcindex_filter_result result
;
33 struct tcindex_filter
*next
;
38 struct tcindex_filter_result
*perfect
; /* perfect hash; NULL if none */
39 struct tcindex_filter
**h
; /* imperfect hash; only used if !perfect;
41 u16 mask
; /* AND key with mask */
42 int shift
; /* shift ANDed key to the right */
43 int hash
; /* hash table size; 0 if undefined */
44 int alloc_hash
; /* allocated size */
45 int fall_through
; /* 0: only classify if explicit match */
48 static const struct tcf_ext_map tcindex_ext_map
= {
49 .police
= TCA_TCINDEX_POLICE
,
50 .action
= TCA_TCINDEX_ACT
54 tcindex_filter_is_set(struct tcindex_filter_result
*r
)
56 return tcf_exts_is_predicative(&r
->exts
) || r
->res
.classid
;
59 static struct tcindex_filter_result
*
60 tcindex_lookup(struct tcindex_data
*p
, u16 key
)
62 struct tcindex_filter
*f
;
65 return tcindex_filter_is_set(p
->perfect
+ key
) ?
66 p
->perfect
+ key
: NULL
;
68 for (f
= p
->h
[key
% p
->hash
]; f
; f
= f
->next
)
77 static int tcindex_classify(struct sk_buff
*skb
, struct tcf_proto
*tp
,
78 struct tcf_result
*res
)
80 struct tcindex_data
*p
= PRIV(tp
);
81 struct tcindex_filter_result
*f
;
82 int key
= (skb
->tc_index
& p
->mask
) >> p
->shift
;
84 pr_debug("tcindex_classify(skb %p,tp %p,res %p),p %p\n",
87 f
= tcindex_lookup(p
, key
);
91 res
->classid
= TC_H_MAKE(TC_H_MAJ(tp
->q
->handle
), key
);
93 pr_debug("alg 0x%x\n", res
->classid
);
97 pr_debug("map 0x%x\n", res
->classid
);
99 return tcf_exts_exec(skb
, &f
->exts
, res
);
103 static unsigned long tcindex_get(struct tcf_proto
*tp
, u32 handle
)
105 struct tcindex_data
*p
= PRIV(tp
);
106 struct tcindex_filter_result
*r
;
108 pr_debug("tcindex_get(tp %p,handle 0x%08x)\n", tp
, handle
);
109 if (p
->perfect
&& handle
>= p
->alloc_hash
)
111 r
= tcindex_lookup(p
, handle
);
112 return r
&& tcindex_filter_is_set(r
) ? (unsigned long) r
: 0UL;
116 static void tcindex_put(struct tcf_proto
*tp
, unsigned long f
)
118 pr_debug("tcindex_put(tp %p,f 0x%lx)\n", tp
, f
);
122 static int tcindex_init(struct tcf_proto
*tp
)
124 struct tcindex_data
*p
;
126 pr_debug("tcindex_init(tp %p)\n", tp
);
127 p
= kzalloc(sizeof(struct tcindex_data
), GFP_KERNEL
);
132 p
->hash
= DEFAULT_HASH_SIZE
;
141 __tcindex_delete(struct tcf_proto
*tp
, unsigned long arg
, int lock
)
143 struct tcindex_data
*p
= PRIV(tp
);
144 struct tcindex_filter_result
*r
= (struct tcindex_filter_result
*) arg
;
145 struct tcindex_filter
*f
= NULL
;
147 pr_debug("tcindex_delete(tp %p,arg 0x%lx),p %p,f %p\n", tp
, arg
, p
, f
);
153 struct tcindex_filter
**walk
= NULL
;
155 for (i
= 0; i
< p
->hash
; i
++)
156 for (walk
= p
->h
+i
; *walk
; walk
= &(*walk
)->next
)
157 if (&(*walk
)->result
== r
)
169 tcf_unbind_filter(tp
, &r
->res
);
170 tcf_exts_destroy(tp
, &r
->exts
);
175 static int tcindex_delete(struct tcf_proto
*tp
, unsigned long arg
)
177 return __tcindex_delete(tp
, arg
, 1);
181 valid_perfect_hash(struct tcindex_data
*p
)
183 return p
->hash
> (p
->mask
>> p
->shift
);
186 static const struct nla_policy tcindex_policy
[TCA_TCINDEX_MAX
+ 1] = {
187 [TCA_TCINDEX_HASH
] = { .type
= NLA_U32
},
188 [TCA_TCINDEX_MASK
] = { .type
= NLA_U16
},
189 [TCA_TCINDEX_SHIFT
] = { .type
= NLA_U32
},
190 [TCA_TCINDEX_FALL_THROUGH
] = { .type
= NLA_U32
},
191 [TCA_TCINDEX_CLASSID
] = { .type
= NLA_U32
},
195 tcindex_set_parms(struct tcf_proto
*tp
, unsigned long base
, u32 handle
,
196 struct tcindex_data
*p
, struct tcindex_filter_result
*r
,
197 struct nlattr
**tb
, struct nlattr
*est
)
200 struct tcindex_filter_result new_filter_result
, *old_r
= r
;
201 struct tcindex_filter_result cr
;
202 struct tcindex_data cp
;
203 struct tcindex_filter
*f
= NULL
; /* make gcc behave */
206 err
= tcf_exts_validate(tp
, tb
, est
, &e
, &tcindex_ext_map
);
210 memcpy(&cp
, p
, sizeof(cp
));
211 memset(&new_filter_result
, 0, sizeof(new_filter_result
));
214 memcpy(&cr
, r
, sizeof(cr
));
216 memset(&cr
, 0, sizeof(cr
));
218 if (tb
[TCA_TCINDEX_HASH
])
219 cp
.hash
= nla_get_u32(tb
[TCA_TCINDEX_HASH
]);
221 if (tb
[TCA_TCINDEX_MASK
])
222 cp
.mask
= nla_get_u16(tb
[TCA_TCINDEX_MASK
]);
224 if (tb
[TCA_TCINDEX_SHIFT
])
225 cp
.shift
= nla_get_u32(tb
[TCA_TCINDEX_SHIFT
]);
228 /* Hash already allocated, make sure that we still meet the
229 * requirements for the allocated hash.
232 if (!valid_perfect_hash(&cp
) ||
233 cp
.hash
> cp
.alloc_hash
)
235 } else if (cp
.h
&& cp
.hash
!= cp
.alloc_hash
)
239 if (tb
[TCA_TCINDEX_FALL_THROUGH
])
240 cp
.fall_through
= nla_get_u32(tb
[TCA_TCINDEX_FALL_THROUGH
]);
243 /* Hash not specified, use perfect hash if the upper limit
244 * of the hashing index is below the threshold.
246 if ((cp
.mask
>> cp
.shift
) < PERFECT_HASH_THRESHOLD
)
247 cp
.hash
= (cp
.mask
>> cp
.shift
)+1;
249 cp
.hash
= DEFAULT_HASH_SIZE
;
252 if (!cp
.perfect
&& !cp
.h
)
253 cp
.alloc_hash
= cp
.hash
;
255 /* Note: this could be as restrictive as if (handle & ~(mask >> shift))
256 * but then, we'd fail handles that may become valid after some future
257 * mask change. While this is extremely unlikely to ever matter,
258 * the check below is safer (and also more backwards-compatible).
260 if (cp
.perfect
|| valid_perfect_hash(&cp
))
261 if (handle
>= cp
.alloc_hash
)
266 if (!cp
.perfect
&& !cp
.h
) {
267 if (valid_perfect_hash(&cp
)) {
268 cp
.perfect
= kcalloc(cp
.hash
, sizeof(*r
), GFP_KERNEL
);
273 cp
.h
= kcalloc(cp
.hash
, sizeof(f
), GFP_KERNEL
);
281 r
= cp
.perfect
+ handle
;
283 r
= tcindex_lookup(&cp
, handle
) ? : &new_filter_result
;
285 if (r
== &new_filter_result
) {
286 f
= kzalloc(sizeof(*f
), GFP_KERNEL
);
291 if (tb
[TCA_TCINDEX_CLASSID
]) {
292 cr
.res
.classid
= nla_get_u32(tb
[TCA_TCINDEX_CLASSID
]);
293 tcf_bind_filter(tp
, &cr
.res
, base
);
296 tcf_exts_change(tp
, &cr
.exts
, &e
);
299 if (old_r
&& old_r
!= r
)
300 memset(old_r
, 0, sizeof(*old_r
));
302 memcpy(p
, &cp
, sizeof(cp
));
303 memcpy(r
, &cr
, sizeof(cr
));
305 if (r
== &new_filter_result
) {
306 struct tcindex_filter
**fp
;
309 f
->result
= new_filter_result
;
311 for (fp
= p
->h
+(handle
% p
->hash
); *fp
; fp
= &(*fp
)->next
)
322 else if (balloc
== 2)
325 tcf_exts_destroy(tp
, &e
);
330 tcindex_change(struct tcf_proto
*tp
, unsigned long base
, u32 handle
,
331 struct nlattr
**tca
, unsigned long *arg
)
333 struct nlattr
*opt
= tca
[TCA_OPTIONS
];
334 struct nlattr
*tb
[TCA_TCINDEX_MAX
+ 1];
335 struct tcindex_data
*p
= PRIV(tp
);
336 struct tcindex_filter_result
*r
= (struct tcindex_filter_result
*) *arg
;
339 pr_debug("tcindex_change(tp %p,handle 0x%08x,tca %p,arg %p),opt %p,"
340 "p %p,r %p,*arg 0x%lx\n",
341 tp
, handle
, tca
, arg
, opt
, p
, r
, arg
? *arg
: 0L);
346 err
= nla_parse_nested(tb
, TCA_TCINDEX_MAX
, opt
, tcindex_policy
);
350 return tcindex_set_parms(tp
, base
, handle
, p
, r
, tb
, tca
[TCA_RATE
]);
354 static void tcindex_walk(struct tcf_proto
*tp
, struct tcf_walker
*walker
)
356 struct tcindex_data
*p
= PRIV(tp
);
357 struct tcindex_filter
*f
, *next
;
360 pr_debug("tcindex_walk(tp %p,walker %p),p %p\n", tp
, walker
, p
);
362 for (i
= 0; i
< p
->hash
; i
++) {
363 if (!p
->perfect
[i
].res
.class)
365 if (walker
->count
>= walker
->skip
) {
367 (unsigned long) (p
->perfect
+i
), walker
)
378 for (i
= 0; i
< p
->hash
; i
++) {
379 for (f
= p
->h
[i
]; f
; f
= next
) {
381 if (walker
->count
>= walker
->skip
) {
382 if (walker
->fn(tp
, (unsigned long) &f
->result
,
394 static int tcindex_destroy_element(struct tcf_proto
*tp
,
395 unsigned long arg
, struct tcf_walker
*walker
)
397 return __tcindex_delete(tp
, arg
, 0);
401 static void tcindex_destroy(struct tcf_proto
*tp
)
403 struct tcindex_data
*p
= PRIV(tp
);
404 struct tcf_walker walker
;
406 pr_debug("tcindex_destroy(tp %p),p %p\n", tp
, p
);
409 walker
.fn
= &tcindex_destroy_element
;
410 tcindex_walk(tp
, &walker
);
418 static int tcindex_dump(struct tcf_proto
*tp
, unsigned long fh
,
419 struct sk_buff
*skb
, struct tcmsg
*t
)
421 struct tcindex_data
*p
= PRIV(tp
);
422 struct tcindex_filter_result
*r
= (struct tcindex_filter_result
*) fh
;
423 unsigned char *b
= skb_tail_pointer(skb
);
426 pr_debug("tcindex_dump(tp %p,fh 0x%lx,skb %p,t %p),p %p,r %p,b %p\n",
427 tp
, fh
, skb
, t
, p
, r
, b
);
428 pr_debug("p->perfect %p p->h %p\n", p
->perfect
, p
->h
);
430 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
432 goto nla_put_failure
;
435 t
->tcm_handle
= ~0; /* whatever ... */
436 NLA_PUT_U32(skb
, TCA_TCINDEX_HASH
, p
->hash
);
437 NLA_PUT_U16(skb
, TCA_TCINDEX_MASK
, p
->mask
);
438 NLA_PUT_U32(skb
, TCA_TCINDEX_SHIFT
, p
->shift
);
439 NLA_PUT_U32(skb
, TCA_TCINDEX_FALL_THROUGH
, p
->fall_through
);
440 nla_nest_end(skb
, nest
);
443 t
->tcm_handle
= r
-p
->perfect
;
445 struct tcindex_filter
*f
;
449 for (i
= 0; !t
->tcm_handle
&& i
< p
->hash
; i
++) {
450 for (f
= p
->h
[i
]; !t
->tcm_handle
&& f
;
453 t
->tcm_handle
= f
->key
;
457 pr_debug("handle = %d\n", t
->tcm_handle
);
459 NLA_PUT_U32(skb
, TCA_TCINDEX_CLASSID
, r
->res
.classid
);
461 if (tcf_exts_dump(skb
, &r
->exts
, &tcindex_ext_map
) < 0)
462 goto nla_put_failure
;
463 nla_nest_end(skb
, nest
);
465 if (tcf_exts_dump_stats(skb
, &r
->exts
, &tcindex_ext_map
) < 0)
466 goto nla_put_failure
;
476 static struct tcf_proto_ops cls_tcindex_ops __read_mostly
= {
478 .classify
= tcindex_classify
,
479 .init
= tcindex_init
,
480 .destroy
= tcindex_destroy
,
483 .change
= tcindex_change
,
484 .delete = tcindex_delete
,
485 .walk
= tcindex_walk
,
486 .dump
= tcindex_dump
,
487 .owner
= THIS_MODULE
,
490 static int __init
init_tcindex(void)
492 return register_tcf_proto_ops(&cls_tcindex_ops
);
495 static void __exit
exit_tcindex(void)
497 unregister_tcf_proto_ops(&cls_tcindex_ops
);
500 module_init(init_tcindex
)
501 module_exit(exit_tcindex
)
502 MODULE_LICENSE("GPL");