net/sched/cls_route.c

   1 /*
   2  * net/sched/cls_route.c        ROUTE4 classifier.
   3  *
   4  *              This program is free software; you can redistribute it and/or
   5  *              modify it under the terms of the GNU General Public License
   6  *              as published by the Free Software Foundation; either version
   7  *              2 of the License, or (at your option) any later version.
   8  *
   9  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  10  */
  11
  12 #include <linux/module.h>
  13 #include <linux/config.h>
  14 #include <asm/uaccess.h>
  15 #include <asm/system.h>
  16 #include <linux/bitops.h>
  17 #include <linux/types.h>
  18 #include <linux/kernel.h>
  19 #include <linux/sched.h>
  20 #include <linux/string.h>
  21 #include <linux/mm.h>
  22 #include <linux/socket.h>
  23 #include <linux/sockios.h>
  24 #include <linux/in.h>
  25 #include <linux/errno.h>
  26 #include <linux/interrupt.h>
  27 #include <linux/if_ether.h>
  28 #include <linux/inet.h>
  29 #include <linux/netdevice.h>
  30 #include <linux/etherdevice.h>
  31 #include <linux/notifier.h>
  32 #include <net/ip.h>
  33 #include <net/route.h>
  34 #include <linux/skbuff.h>
  35 #include <net/sock.h>
  36 #include <net/act_api.h>
  37 #include <net/pkt_cls.h>
  38
  39 /*
  40    1. For now we assume that route tags < 256.
  41       It allows to use direct table lookups, instead of hash tables.
  42    2. For now we assume that "from TAG" and "fromdev DEV" statements
  43       are mutually  exclusive.
  44    3. "to TAG from ANY" has higher priority, than "to ANY from XXX"
  45  */
  46
  47 struct route4_fastmap
  48 {
  49         struct route4_filter    *filter;
  50         u32                     id;
  51         int                     iif;
  52 };
  53
  54 struct route4_head
  55 {
  56         struct route4_fastmap   fastmap[16];
  57         struct route4_bucket    *table[256+1];
  58 };
  59
  60 struct route4_bucket
  61 {
  62         struct route4_filter    *ht[16+16+1];
  63 };
  64
  65 struct route4_filter
  66 {
  67         struct route4_filter    *next;
  68         u32                     id;
  69         int                     iif;
  70
  71         struct tcf_result       res;
  72 #ifdef CONFIG_NET_CLS_POLICE
  73         struct tcf_police       *police;
  74 #endif
  75
  76         u32                     handle;
  77         struct route4_bucket    *bkt;
  78 };
  79
  80 #define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
  81
  82 static __inline__ int route4_fastmap_hash(u32 id, int iif)
  83 {
  84         return id&0xF;
  85 }
  86
  87 static void route4_reset_fastmap(struct net_device *dev, struct route4_head *head, u32 id)
  88 {
  89         spin_lock_bh(&dev->queue_lock);
  90         memset(head->fastmap, 0, sizeof(head->fastmap));
  91         spin_unlock_bh(&dev->queue_lock);
  92 }
  93
  94 static void __inline__
  95 route4_set_fastmap(struct route4_head *head, u32 id, int iif,
  96                    struct route4_filter *f)
  97 {
  98         int h = route4_fastmap_hash(id, iif);
  99         head->fastmap[h].id = id;
 100         head->fastmap[h].iif = iif;
 101         head->fastmap[h].filter = f;
 102 }
 103
 104 static __inline__ int route4_hash_to(u32 id)
 105 {
 106         return id&0xFF;
 107 }
 108
 109 static __inline__ int route4_hash_from(u32 id)
 110 {
 111         return (id>>16)&0xF;
 112 }
 113
 114 static __inline__ int route4_hash_iif(int iif)
 115 {
 116         return 16 + ((iif>>16)&0xF);
 117 }
 118
 119 static __inline__ int route4_hash_wild(void)
 120 {
 121         return 32;
 122 }
 123
 124 #ifdef CONFIG_NET_CLS_POLICE
 125 #define IF_ROUTE_POLICE \
 126 if (f->police) { \
 127         int pol_res = tcf_police(skb, f->police); \
 128         if (pol_res >= 0) return pol_res; \
 129         dont_cache = 1; \
 130         continue; \
 131 } \
 132 if (!dont_cache)
 133 #else
 134 #define IF_ROUTE_POLICE
 135 #endif
 136
 137
 138 static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp,
 139                            struct tcf_result *res)
 140 {
 141         struct route4_head *head = (struct route4_head*)tp->root;
 142         struct dst_entry *dst;
 143         struct route4_bucket *b;
 144         struct route4_filter *f;
 145 #ifdef CONFIG_NET_CLS_POLICE
 146         int dont_cache = 0;
 147 #endif
 148         u32 id, h;
 149         int iif;
 150
 151         if ((dst = skb->dst) == NULL)
 152                 goto failure;
 153
 154         id = dst->tclassid;
 155         if (head == NULL)
 156                 goto old_method;
 157
 158         iif = ((struct rtable*)dst)->fl.iif;
 159
 160         h = route4_fastmap_hash(id, iif);
 161         if (id == head->fastmap[h].id &&
 162             iif == head->fastmap[h].iif &&
 163             (f = head->fastmap[h].filter) != NULL) {
 164                 if (f == ROUTE4_FAILURE)
 165                         goto failure;
 166
 167                 *res = f->res;
 168                 return 0;
 169         }
 170
 171         h = route4_hash_to(id);
 172
 173 restart:
 174         if ((b = head->table[h]) != NULL) {
 175                 f = b->ht[route4_hash_from(id)];
 176
 177                 for ( ; f; f = f->next) {
 178                         if (f->id == id) {
 179                                 *res = f->res;
 180                                 IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);
 181                                 return 0;
 182                         }
 183                 }
 184
 185                 for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next) {
 186                         if (f->iif == iif) {
 187                                 *res = f->res;
 188                                 IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);
 189                                 return 0;
 190                         }
 191                 }
 192
 193                 for (f = b->ht[route4_hash_wild()]; f; f = f->next) {
 194                         *res = f->res;
 195                         IF_ROUTE_POLICE route4_set_fastmap(head, id, iif, f);
 196                         return 0;
 197                 }
 198
 199         }
 200         if (h < 256) {
 201                 h = 256;
 202                 id &= ~0xFFFF;
 203                 goto restart;
 204         }
 205
 206 #ifdef CONFIG_NET_CLS_POLICE
 207         if (!dont_cache)
 208 #endif
 209                 route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
 210 failure:
 211         return -1;
 212
 213 old_method:
 214         if (id && (TC_H_MAJ(id) == 0 ||
 215                    !(TC_H_MAJ(id^tp->q->handle)))) {
 216                 res->classid = id;
 217                 res->class = 0;
 218                 return 0;
 219         }
 220         return -1;
 221 }
 222
 223 static u32 to_hash(u32 id)
 224 {
 225         u32 h = id&0xFF;
 226         if (id&0x8000)
 227                 h += 256;
 228         return h;
 229 }
 230
 231 static u32 from_hash(u32 id)
 232 {
 233         id &= 0xFFFF;
 234         if (id == 0xFFFF)
 235                 return 32;
 236         if (!(id & 0x8000)) {
 237                 if (id > 255)
 238                         return 256;
 239                 return id&0xF;
 240         }
 241         return 16 + (id&0xF);
 242 }
 243
 244 static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
 245 {
 246         struct route4_head *head = (struct route4_head*)tp->root;
 247         struct route4_bucket *b;
 248         struct route4_filter *f;
 249         unsigned h1, h2;
 250
 251         if (!head)
 252                 return 0;
 253
 254         h1 = to_hash(handle);
 255         if (h1 > 256)
 256                 return 0;
 257
 258         h2 = from_hash(handle>>16);
 259         if (h2 > 32)
 260                 return 0;
 261
 262         if ((b = head->table[h1]) != NULL) {
 263                 for (f = b->ht[h2]; f; f = f->next)
 264                         if (f->handle == handle)
 265                                 return (unsigned long)f;
 266         }
 267         return 0;
 268 }
 269
 270 static void route4_put(struct tcf_proto *tp, unsigned long f)
 271 {
 272 }
 273
 274 static int route4_init(struct tcf_proto *tp)
 275 {
 276         return 0;
 277 }
 278
 279 static void route4_destroy(struct tcf_proto *tp)
 280 {
 281         struct route4_head *head = xchg(&tp->root, NULL);
 282         int h1, h2;
 283
 284         if (head == NULL)
 285                 return;
 286
 287         for (h1=0; h1<=256; h1++) {
 288                 struct route4_bucket *b;
 289
 290                 if ((b = head->table[h1]) != NULL) {
 291                         for (h2=0; h2<=32; h2++) {
 292                                 struct route4_filter *f;
 293
 294                                 while ((f = b->ht[h2]) != NULL) {
 295                                         b->ht[h2] = f->next;
 296                                         tcf_unbind_filter(tp, &f->res);
 297 #ifdef CONFIG_NET_CLS_POLICE
 298                                         tcf_police_release(f->police,TCA_ACT_UNBIND);
 299 #endif
 300                                         kfree(f);
 301                                 }
 302                         }
 303                         kfree(b);
 304                 }
 305         }
 306         kfree(head);
 307 }
 308
 309 static int route4_delete(struct tcf_proto *tp, unsigned long arg)
 310 {
 311         struct route4_head *head = (struct route4_head*)tp->root;
 312         struct route4_filter **fp, *f = (struct route4_filter*)arg;
 313         unsigned h = 0;
 314         struct route4_bucket *b;
 315         int i;
 316
 317         if (!head || !f)
 318                 return -EINVAL;
 319
 320         h = f->handle;
 321         b = f->bkt;
 322
 323         for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {
 324                 if (*fp == f) {
 325                         tcf_tree_lock(tp);
 326                         *fp = f->next;
 327                         tcf_tree_unlock(tp);
 328
 329                         route4_reset_fastmap(tp->q->dev, head, f->id);
 330                         tcf_unbind_filter(tp, &f->res);
 331 #ifdef CONFIG_NET_CLS_POLICE
 332                         tcf_police_release(f->police,TCA_ACT_UNBIND);
 333 #endif
 334                         kfree(f);
 335
 336                         /* Strip tree */
 337
 338                         for (i=0; i<=32; i++)
 339                                 if (b->ht[i])
 340                                         return 0;
 341
 342                         /* OK, session has no flows */
 343                         tcf_tree_lock(tp);
 344                         head->table[to_hash(h)] = NULL;
 345                         tcf_tree_unlock(tp);
 346
 347                         kfree(b);
 348                         return 0;
 349                 }
 350         }
 351         return 0;
 352 }
 353
 354 static int route4_change(struct tcf_proto *tp, unsigned long base,
 355                        u32 handle,
 356                        struct rtattr **tca,
 357                        unsigned long *arg)
 358 {
 359         struct route4_head *head = tp->root;
 360         struct route4_filter *f, *f1, **ins_f;
 361         struct route4_bucket *b;
 362         struct rtattr *opt = tca[TCA_OPTIONS-1];
 363         struct rtattr *tb[TCA_ROUTE4_MAX];
 364         unsigned h1, h2;
 365         int err;
 366
 367         if (opt == NULL)
 368                 return handle ? -EINVAL : 0;
 369
 370         if (rtattr_parse(tb, TCA_ROUTE4_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)
 371                 return -EINVAL;
 372
 373         if ((f = (struct route4_filter*)*arg) != NULL) {
 374                 if (f->handle != handle && handle)
 375                         return -EINVAL;
 376                 if (tb[TCA_ROUTE4_CLASSID-1]) {
 377                         f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
 378                         tcf_bind_filter(tp, &f->res, base);
 379                 }
 380 #ifdef CONFIG_NET_CLS_POLICE
 381                 if (tb[TCA_ROUTE4_POLICE-1]) {
 382                         err = tcf_change_police(tp, &f->police,
 383                                 tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);
 384                         if (err < 0)
 385                                 return err;
 386                 }
 387 #endif
 388                 return 0;
 389         }
 390
 391         /* Now more serious part... */
 392
 393         if (head == NULL) {
 394                 head = kmalloc(sizeof(struct route4_head), GFP_KERNEL);
 395                 if (head == NULL)
 396                         return -ENOBUFS;
 397                 memset(head, 0, sizeof(struct route4_head));
 398
 399                 tcf_tree_lock(tp);
 400                 tp->root = head;
 401                 tcf_tree_unlock(tp);
 402         }
 403
 404         f = kmalloc(sizeof(struct route4_filter), GFP_KERNEL);
 405         if (f == NULL)
 406                 return -ENOBUFS;
 407
 408         memset(f, 0, sizeof(*f));
 409
 410         err = -EINVAL;
 411         f->handle = 0x8000;
 412         if (tb[TCA_ROUTE4_TO-1]) {
 413                 if (handle&0x8000)
 414                         goto errout;
 415                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < 4)
 416                         goto errout;
 417                 f->id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_TO-1]);
 418                 if (f->id > 0xFF)
 419                         goto errout;
 420                 f->handle = f->id;
 421         }
 422         if (tb[TCA_ROUTE4_FROM-1]) {
 423                 u32 sid;
 424                 if (tb[TCA_ROUTE4_IIF-1])
 425                         goto errout;
 426                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < 4)
 427                         goto errout;
 428                 sid = (*(u32*)RTA_DATA(tb[TCA_ROUTE4_FROM-1]));
 429                 if (sid > 0xFF)
 430                         goto errout;
 431                 f->handle |= sid<<16;
 432                 f->id |= sid<<16;
 433         } else if (tb[TCA_ROUTE4_IIF-1]) {
 434                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < 4)
 435                         goto errout;
 436                 f->iif = *(u32*)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);
 437                 if (f->iif > 0x7FFF)
 438                         goto errout;
 439                 f->handle |= (f->iif|0x8000)<<16;
 440         } else
 441                 f->handle |= 0xFFFF<<16;
 442
 443         if (handle) {
 444                 f->handle |= handle&0x7F00;
 445                 if (f->handle != handle)
 446                         goto errout;
 447         }
 448
 449         if (tb[TCA_ROUTE4_CLASSID-1]) {
 450                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < 4)
 451                         goto errout;
 452                 f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
 453         }
 454
 455         h1 = to_hash(f->handle);
 456         if ((b = head->table[h1]) == NULL) {
 457                 err = -ENOBUFS;
 458                 b = kmalloc(sizeof(struct route4_bucket), GFP_KERNEL);
 459                 if (b == NULL)
 460                         goto errout;
 461                 memset(b, 0, sizeof(*b));
 462
 463                 tcf_tree_lock(tp);
 464                 head->table[h1] = b;
 465                 tcf_tree_unlock(tp);
 466         }
 467         f->bkt = b;
 468
 469         err = -EEXIST;
 470         h2 = from_hash(f->handle>>16);
 471         for (ins_f = &b->ht[h2]; (f1=*ins_f) != NULL; ins_f = &f1->next) {
 472                 if (f->handle < f1->handle)
 473                         break;
 474                 if (f1->handle == f->handle)
 475                         goto errout;
 476         }
 477
 478         tcf_bind_filter(tp, &f->res, base);
 479 #ifdef CONFIG_NET_CLS_POLICE
 480         if (tb[TCA_ROUTE4_POLICE-1])
 481                 tcf_change_police(tp, &f->police, tb[TCA_ROUTE4_POLICE-1], tca[TCA_RATE-1]);
 482 #endif
 483
 484         f->next = f1;
 485         tcf_tree_lock(tp);
 486         *ins_f = f;
 487         tcf_tree_unlock(tp);
 488
 489         route4_reset_fastmap(tp->q->dev, head, f->id);
 490         *arg = (unsigned long)f;
 491         return 0;
 492
 493 errout:
 494         if (f)
 495                 kfree(f);
 496         return err;
 497 }
 498
 499 static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
 500 {
 501         struct route4_head *head = tp->root;
 502         unsigned h, h1;
 503
 504         if (head == NULL)
 505                 arg->stop = 1;
 506
 507         if (arg->stop)
 508                 return;
 509
 510         for (h = 0; h <= 256; h++) {
 511                 struct route4_bucket *b = head->table[h];
 512
 513                 if (b) {
 514                         for (h1 = 0; h1 <= 32; h1++) {
 515                                 struct route4_filter *f;
 516
 517                                 for (f = b->ht[h1]; f; f = f->next) {
 518                                         if (arg->count < arg->skip) {
 519                                                 arg->count++;
 520                                                 continue;
 521                                         }
 522                                         if (arg->fn(tp, (unsigned long)f, arg) < 0) {
 523                                                 arg->stop = 1;
 524                                                 return;
 525                                         }
 526                                         arg->count++;
 527                                 }
 528                         }
 529                 }
 530         }
 531 }
 532
 533 static int route4_dump(struct tcf_proto *tp, unsigned long fh,
 534                        struct sk_buff *skb, struct tcmsg *t)
 535 {
 536         struct route4_filter *f = (struct route4_filter*)fh;
 537         unsigned char    *b = skb->tail;
 538         struct rtattr *rta;
 539         u32 id;
 540
 541         if (f == NULL)
 542                 return skb->len;
 543
 544         t->tcm_handle = f->handle;
 545
 546         rta = (struct rtattr*)b;
 547         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 548
 549         if (!(f->handle&0x8000)) {
 550                 id = f->id&0xFF;
 551                 RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);
 552         }
 553         if (f->handle&0x80000000) {
 554                 if ((f->handle>>16) != 0xFFFF)
 555                         RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
 556         } else {
 557                 id = f->id>>16;
 558                 RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
 559         }
 560         if (f->res.classid)
 561                 RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);
 562 #ifdef CONFIG_NET_CLS_POLICE
 563         if (tcf_dump_police(skb, f->police, TCA_ROUTE4_POLICE) < 0)
 564                 goto rtattr_failure;
 565 #endif
 566
 567         rta->rta_len = skb->tail - b;
 568 #ifdef CONFIG_NET_CLS_POLICE
 569         if (f->police)
 570                 if (tcf_police_dump_stats(skb, f->police) < 0)
 571                         goto rtattr_failure;
 572 #endif
 573         return skb->len;
 574
 575 rtattr_failure:
 576         skb_trim(skb, b - skb->data);
 577         return -1;
 578 }
 579
 580 static struct tcf_proto_ops cls_route4_ops = {
 581         .next           =       NULL,
 582         .kind           =       "route",
 583         .classify       =       route4_classify,
 584         .init           =       route4_init,
 585         .destroy        =       route4_destroy,
 586         .get            =       route4_get,
 587         .put            =       route4_put,
 588         .change         =       route4_change,
 589         .delete         =       route4_delete,
 590         .walk           =       route4_walk,
 591         .dump           =       route4_dump,
 592         .owner          =       THIS_MODULE,
 593 };
 594
 595 static int __init init_route4(void)
 596 {
 597         return register_tcf_proto_ops(&cls_route4_ops);
 598 }
 599
 600 static void __exit exit_route4(void)
 601 {
 602         unregister_tcf_proto_ops(&cls_route4_ops);
 603 }
 604
 605 module_init(init_route4)
 606 module_exit(exit_route4)
 607 MODULE_LICENSE("GPL");