net/sched/cls_tcindex.c

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