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 * Passing parameters to the root seems to be done more awkwardly than really
19 * necessary. At least, u32 doesn't seem to use such dirty hacks. To be
23 #define PERFECT_HASH_THRESHOLD 64 /* use perfect hash if not bigger */
24 #define DEFAULT_HASH_SIZE 64 /* optimized for diffserv */
27 struct tcindex_filter_result
{
29 struct tcf_result res
;
32 struct tcindex_filter
{
34 struct tcindex_filter_result result
;
35 struct tcindex_filter __rcu
*next
;
41 struct tcindex_filter_result
*perfect
; /* perfect hash; NULL if none */
42 struct tcindex_filter __rcu
**h
; /* imperfect hash; */
44 u16 mask
; /* AND key with mask */
45 u32 shift
; /* shift ANDed key to the right */
46 u32 hash
; /* hash table size; 0 if undefined */
47 u32 alloc_hash
; /* allocated size */
48 u32 fall_through
; /* 0: only classify if explicit match */
53 tcindex_filter_is_set(struct tcindex_filter_result
*r
)
55 return tcf_exts_is_predicative(&r
->exts
) || r
->res
.classid
;
58 static struct tcindex_filter_result
*
59 tcindex_lookup(struct tcindex_data
*p
, u16 key
)
62 struct tcindex_filter_result
*f
= p
->perfect
+ key
;
64 return tcindex_filter_is_set(f
) ? f
: NULL
;
66 struct tcindex_filter __rcu
**fp
;
67 struct tcindex_filter
*f
;
69 fp
= &p
->h
[key
% p
->hash
];
70 for (f
= rcu_dereference_bh_rtnl(*fp
);
72 fp
= &f
->next
, f
= rcu_dereference_bh_rtnl(*fp
))
81 static int tcindex_classify(struct sk_buff
*skb
, const struct tcf_proto
*tp
,
82 struct tcf_result
*res
)
84 struct tcindex_data
*p
= rcu_dereference_bh(tp
->root
);
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
= rtnl_dereference(tp
->root
);
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
;
139 rcu_assign_pointer(tp
->root
, p
);
144 tcindex_delete(struct tcf_proto
*tp
, unsigned long arg
)
146 struct tcindex_data
*p
= rtnl_dereference(tp
->root
);
147 struct tcindex_filter_result
*r
= (struct tcindex_filter_result
*) arg
;
148 struct tcindex_filter __rcu
**walk
;
149 struct tcindex_filter
*f
= NULL
;
151 pr_debug("tcindex_delete(tp %p,arg 0x%lx),p %p\n", tp
, arg
, p
);
158 for (i
= 0; i
< p
->hash
; i
++) {
160 for (f
= rtnl_dereference(*walk
); f
;
161 walk
= &f
->next
, f
= rtnl_dereference(*walk
)) {
169 rcu_assign_pointer(*walk
, rtnl_dereference(f
->next
));
171 tcf_unbind_filter(tp
, &r
->res
);
172 tcf_exts_destroy(&r
->exts
);
178 static int tcindex_destroy_element(struct tcf_proto
*tp
,
180 struct tcf_walker
*walker
)
182 return tcindex_delete(tp
, arg
);
185 static void __tcindex_destroy(struct rcu_head
*head
)
187 struct tcindex_data
*p
= container_of(head
, struct tcindex_data
, rcu
);
195 valid_perfect_hash(struct tcindex_data
*p
)
197 return p
->hash
> (p
->mask
>> p
->shift
);
200 static const struct nla_policy tcindex_policy
[TCA_TCINDEX_MAX
+ 1] = {
201 [TCA_TCINDEX_HASH
] = { .type
= NLA_U32
},
202 [TCA_TCINDEX_MASK
] = { .type
= NLA_U16
},
203 [TCA_TCINDEX_SHIFT
] = { .type
= NLA_U32
},
204 [TCA_TCINDEX_FALL_THROUGH
] = { .type
= NLA_U32
},
205 [TCA_TCINDEX_CLASSID
] = { .type
= NLA_U32
},
208 static void tcindex_filter_result_init(struct tcindex_filter_result
*r
)
210 memset(r
, 0, sizeof(*r
));
211 tcf_exts_init(&r
->exts
, TCA_TCINDEX_ACT
, TCA_TCINDEX_POLICE
);
214 static void __tcindex_partial_destroy(struct rcu_head
*head
)
216 struct tcindex_data
*p
= container_of(head
, struct tcindex_data
, rcu
);
223 tcindex_set_parms(struct net
*net
, struct tcf_proto
*tp
, unsigned long base
,
224 u32 handle
, struct tcindex_data
*p
,
225 struct tcindex_filter_result
*r
, struct nlattr
**tb
,
226 struct nlattr
*est
, bool ovr
)
229 struct tcindex_filter_result new_filter_result
, *old_r
= r
;
230 struct tcindex_filter_result cr
;
231 struct tcindex_data
*cp
, *oldp
;
232 struct tcindex_filter
*f
= NULL
; /* make gcc behave */
235 tcf_exts_init(&e
, TCA_TCINDEX_ACT
, TCA_TCINDEX_POLICE
);
236 err
= tcf_exts_validate(net
, tp
, tb
, est
, &e
, ovr
);
241 /* tcindex_data attributes must look atomic to classifier/lookup so
242 * allocate new tcindex data and RCU assign it onto root. Keeping
243 * perfect hash and hash pointers from old data.
245 cp
= kzalloc(sizeof(*cp
), GFP_KERNEL
);
250 cp
->shift
= p
->shift
;
252 cp
->alloc_hash
= p
->alloc_hash
;
253 cp
->fall_through
= p
->fall_through
;
259 cp
->perfect
= kmemdup(p
->perfect
,
260 sizeof(*r
) * cp
->hash
, GFP_KERNEL
);
263 for (i
= 0; i
< cp
->hash
; i
++)
264 tcf_exts_init(&cp
->perfect
[i
].exts
,
265 TCA_TCINDEX_ACT
, TCA_TCINDEX_POLICE
);
270 tcindex_filter_result_init(&new_filter_result
);
271 tcindex_filter_result_init(&cr
);
275 if (tb
[TCA_TCINDEX_HASH
])
276 cp
->hash
= nla_get_u32(tb
[TCA_TCINDEX_HASH
]);
278 if (tb
[TCA_TCINDEX_MASK
])
279 cp
->mask
= nla_get_u16(tb
[TCA_TCINDEX_MASK
]);
281 if (tb
[TCA_TCINDEX_SHIFT
])
282 cp
->shift
= nla_get_u32(tb
[TCA_TCINDEX_SHIFT
]);
286 /* Hash already allocated, make sure that we still meet the
287 * requirements for the allocated hash.
290 if (!valid_perfect_hash(cp
) ||
291 cp
->hash
> cp
->alloc_hash
)
293 } else if (cp
->h
&& cp
->hash
!= cp
->alloc_hash
) {
298 if (tb
[TCA_TCINDEX_FALL_THROUGH
])
299 cp
->fall_through
= nla_get_u32(tb
[TCA_TCINDEX_FALL_THROUGH
]);
302 /* Hash not specified, use perfect hash if the upper limit
303 * of the hashing index is below the threshold.
305 if ((cp
->mask
>> cp
->shift
) < PERFECT_HASH_THRESHOLD
)
306 cp
->hash
= (cp
->mask
>> cp
->shift
) + 1;
308 cp
->hash
= DEFAULT_HASH_SIZE
;
311 if (!cp
->perfect
&& !cp
->h
)
312 cp
->alloc_hash
= cp
->hash
;
314 /* Note: this could be as restrictive as if (handle & ~(mask >> shift))
315 * but then, we'd fail handles that may become valid after some future
316 * mask change. While this is extremely unlikely to ever matter,
317 * the check below is safer (and also more backwards-compatible).
319 if (cp
->perfect
|| valid_perfect_hash(cp
))
320 if (handle
>= cp
->alloc_hash
)
325 if (!cp
->perfect
&& !cp
->h
) {
326 if (valid_perfect_hash(cp
)) {
329 cp
->perfect
= kcalloc(cp
->hash
, sizeof(*r
), GFP_KERNEL
);
332 for (i
= 0; i
< cp
->hash
; i
++)
333 tcf_exts_init(&cp
->perfect
[i
].exts
,
338 struct tcindex_filter __rcu
**hash
;
340 hash
= kcalloc(cp
->hash
,
341 sizeof(struct tcindex_filter
*),
353 r
= cp
->perfect
+ handle
;
355 r
= tcindex_lookup(cp
, handle
) ? : &new_filter_result
;
357 if (r
== &new_filter_result
) {
358 f
= kzalloc(sizeof(*f
), GFP_KERNEL
);
362 tcindex_filter_result_init(&f
->result
);
366 if (tb
[TCA_TCINDEX_CLASSID
]) {
367 cr
.res
.classid
= nla_get_u32(tb
[TCA_TCINDEX_CLASSID
]);
368 tcf_bind_filter(tp
, &cr
.res
, base
);
372 tcf_exts_change(tp
, &r
->exts
, &e
);
374 tcf_exts_change(tp
, &cr
.exts
, &e
);
376 if (old_r
&& old_r
!= r
)
377 tcindex_filter_result_init(old_r
);
381 rcu_assign_pointer(tp
->root
, cp
);
383 if (r
== &new_filter_result
) {
384 struct tcindex_filter
*nfp
;
385 struct tcindex_filter __rcu
**fp
;
387 tcf_exts_change(tp
, &f
->result
.exts
, &r
->exts
);
389 fp
= cp
->h
+ (handle
% cp
->hash
);
390 for (nfp
= rtnl_dereference(*fp
);
392 fp
= &nfp
->next
, nfp
= rtnl_dereference(*fp
))
395 rcu_assign_pointer(*fp
, f
);
399 call_rcu(&oldp
->rcu
, __tcindex_partial_destroy
);
405 else if (balloc
== 2)
409 tcf_exts_destroy(&e
);
414 tcindex_change(struct net
*net
, struct sk_buff
*in_skb
,
415 struct tcf_proto
*tp
, unsigned long base
, u32 handle
,
416 struct nlattr
**tca
, unsigned long *arg
, bool ovr
)
418 struct nlattr
*opt
= tca
[TCA_OPTIONS
];
419 struct nlattr
*tb
[TCA_TCINDEX_MAX
+ 1];
420 struct tcindex_data
*p
= rtnl_dereference(tp
->root
);
421 struct tcindex_filter_result
*r
= (struct tcindex_filter_result
*) *arg
;
424 pr_debug("tcindex_change(tp %p,handle 0x%08x,tca %p,arg %p),opt %p,"
425 "p %p,r %p,*arg 0x%lx\n",
426 tp
, handle
, tca
, arg
, opt
, p
, r
, arg
? *arg
: 0L);
431 err
= nla_parse_nested(tb
, TCA_TCINDEX_MAX
, opt
, tcindex_policy
);
435 return tcindex_set_parms(net
, tp
, base
, handle
, p
, r
, tb
,
439 static void tcindex_walk(struct tcf_proto
*tp
, struct tcf_walker
*walker
)
441 struct tcindex_data
*p
= rtnl_dereference(tp
->root
);
442 struct tcindex_filter
*f
, *next
;
445 pr_debug("tcindex_walk(tp %p,walker %p),p %p\n", tp
, walker
, p
);
447 for (i
= 0; i
< p
->hash
; i
++) {
448 if (!p
->perfect
[i
].res
.class)
450 if (walker
->count
>= walker
->skip
) {
452 (unsigned long) (p
->perfect
+i
), walker
)
463 for (i
= 0; i
< p
->hash
; i
++) {
464 for (f
= rtnl_dereference(p
->h
[i
]); f
; f
= next
) {
465 next
= rtnl_dereference(f
->next
);
466 if (walker
->count
>= walker
->skip
) {
467 if (walker
->fn(tp
, (unsigned long) &f
->result
,
478 static void tcindex_destroy(struct tcf_proto
*tp
)
480 struct tcindex_data
*p
= rtnl_dereference(tp
->root
);
481 struct tcf_walker walker
;
483 pr_debug("tcindex_destroy(tp %p),p %p\n", tp
, p
);
486 walker
.fn
= tcindex_destroy_element
;
487 tcindex_walk(tp
, &walker
);
489 RCU_INIT_POINTER(tp
->root
, NULL
);
490 call_rcu(&p
->rcu
, __tcindex_destroy
);
494 static int tcindex_dump(struct net
*net
, struct tcf_proto
*tp
, unsigned long fh
,
495 struct sk_buff
*skb
, struct tcmsg
*t
)
497 struct tcindex_data
*p
= rtnl_dereference(tp
->root
);
498 struct tcindex_filter_result
*r
= (struct tcindex_filter_result
*) fh
;
499 unsigned char *b
= skb_tail_pointer(skb
);
502 pr_debug("tcindex_dump(tp %p,fh 0x%lx,skb %p,t %p),p %p,r %p,b %p\n",
503 tp
, fh
, skb
, t
, p
, r
, b
);
504 pr_debug("p->perfect %p p->h %p\n", p
->perfect
, p
->h
);
506 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
508 goto nla_put_failure
;
511 t
->tcm_handle
= ~0; /* whatever ... */
512 if (nla_put_u32(skb
, TCA_TCINDEX_HASH
, p
->hash
) ||
513 nla_put_u16(skb
, TCA_TCINDEX_MASK
, p
->mask
) ||
514 nla_put_u32(skb
, TCA_TCINDEX_SHIFT
, p
->shift
) ||
515 nla_put_u32(skb
, TCA_TCINDEX_FALL_THROUGH
, p
->fall_through
))
516 goto nla_put_failure
;
517 nla_nest_end(skb
, nest
);
520 t
->tcm_handle
= r
- p
->perfect
;
522 struct tcindex_filter
*f
;
523 struct tcindex_filter __rcu
**fp
;
527 for (i
= 0; !t
->tcm_handle
&& i
< p
->hash
; i
++) {
529 for (f
= rtnl_dereference(*fp
);
531 fp
= &f
->next
, f
= rtnl_dereference(*fp
)) {
533 t
->tcm_handle
= f
->key
;
537 pr_debug("handle = %d\n", t
->tcm_handle
);
539 nla_put_u32(skb
, TCA_TCINDEX_CLASSID
, r
->res
.classid
))
540 goto nla_put_failure
;
542 if (tcf_exts_dump(skb
, &r
->exts
) < 0)
543 goto nla_put_failure
;
544 nla_nest_end(skb
, nest
);
546 if (tcf_exts_dump_stats(skb
, &r
->exts
) < 0)
547 goto nla_put_failure
;
557 static struct tcf_proto_ops cls_tcindex_ops __read_mostly
= {
559 .classify
= tcindex_classify
,
560 .init
= tcindex_init
,
561 .destroy
= tcindex_destroy
,
564 .change
= tcindex_change
,
565 .delete = tcindex_delete
,
566 .walk
= tcindex_walk
,
567 .dump
= tcindex_dump
,
568 .owner
= THIS_MODULE
,
571 static int __init
init_tcindex(void)
573 return register_tcf_proto_ops(&cls_tcindex_ops
);
576 static void __exit
exit_tcindex(void)
578 unregister_tcf_proto_ops(&cls_tcindex_ops
);
581 module_init(init_tcindex
)
582 module_exit(exit_tcindex
)
583 MODULE_LICENSE("GPL");