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