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         /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
  63         struct route4_filter    *ht[16+16+1];
  64 };
  65
  66 struct route4_filter
  67 {
  68         struct route4_filter    *next;
  69         u32                     id;
  70         int                     iif;
  71
  72         struct tcf_result       res;
  73         struct tcf_exts         exts;
  74         u32                     handle;
  75         struct route4_bucket    *bkt;
  76 };
  77
  78 #define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
  79
  80 static struct tcf_ext_map route_ext_map = {
  81         .police = TCA_ROUTE4_POLICE,
  82         .action = TCA_ROUTE4_ACT
  83 };
  84
  85 static __inline__ int route4_fastmap_hash(u32 id, int iif)
  86 {
  87         return id&0xF;
  88 }
  89
  90 static inline
  91 void route4_reset_fastmap(struct net_device *dev, struct route4_head *head, u32 id)
  92 {
  93         spin_lock_bh(&dev->queue_lock);
  94         memset(head->fastmap, 0, sizeof(head->fastmap));
  95         spin_unlock_bh(&dev->queue_lock);
  96 }
  97
  98 static void __inline__
  99 route4_set_fastmap(struct route4_head *head, u32 id, int iif,
 100                    struct route4_filter *f)
 101 {
 102         int h = route4_fastmap_hash(id, iif);
 103         head->fastmap[h].id = id;
 104         head->fastmap[h].iif = iif;
 105         head->fastmap[h].filter = f;
 106 }
 107
 108 static __inline__ int route4_hash_to(u32 id)
 109 {
 110         return id&0xFF;
 111 }
 112
 113 static __inline__ int route4_hash_from(u32 id)
 114 {
 115         return (id>>16)&0xF;
 116 }
 117
 118 static __inline__ int route4_hash_iif(int iif)
 119 {
 120         return 16 + ((iif>>16)&0xF);
 121 }
 122
 123 static __inline__ int route4_hash_wild(void)
 124 {
 125         return 32;
 126 }
 127
 128 #define ROUTE4_APPLY_RESULT()                                   \
 129 {                                                               \
 130         *res = f->res;                                          \
 131         if (tcf_exts_is_available(&f->exts)) {                  \
 132                 int r = tcf_exts_exec(skb, &f->exts, res);      \
 133                 if (r < 0) {                                    \
 134                         dont_cache = 1;                         \
 135                         continue;                               \
 136                 }                                               \
 137                 return r;                                       \
 138         } else if (!dont_cache)                                 \
 139                 route4_set_fastmap(head, id, iif, f);           \
 140         return 0;                                               \
 141 }
 142
 143 static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp,
 144                            struct tcf_result *res)
 145 {
 146         struct route4_head *head = (struct route4_head*)tp->root;
 147         struct dst_entry *dst;
 148         struct route4_bucket *b;
 149         struct route4_filter *f;
 150         u32 id, h;
 151         int iif, dont_cache = 0;
 152
 153         if ((dst = skb->dst) == NULL)
 154                 goto failure;
 155
 156         id = dst->tclassid;
 157         if (head == NULL)
 158                 goto old_method;
 159
 160         iif = ((struct rtable*)dst)->fl.iif;
 161
 162         h = route4_fastmap_hash(id, iif);
 163         if (id == head->fastmap[h].id &&
 164             iif == head->fastmap[h].iif &&
 165             (f = head->fastmap[h].filter) != NULL) {
 166                 if (f == ROUTE4_FAILURE)
 167                         goto failure;
 168
 169                 *res = f->res;
 170                 return 0;
 171         }
 172
 173         h = route4_hash_to(id);
 174
 175 restart:
 176         if ((b = head->table[h]) != NULL) {
 177                 for (f = b->ht[route4_hash_from(id)]; f; f = f->next)
 178                         if (f->id == id)
 179                                 ROUTE4_APPLY_RESULT();
 180
 181                 for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)
 182                         if (f->iif == iif)
 183                                 ROUTE4_APPLY_RESULT();
 184
 185                 for (f = b->ht[route4_hash_wild()]; f; f = f->next)
 186                         ROUTE4_APPLY_RESULT();
 187
 188         }
 189         if (h < 256) {
 190                 h = 256;
 191                 id &= ~0xFFFF;
 192                 goto restart;
 193         }
 194
 195         if (!dont_cache)
 196                 route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
 197 failure:
 198         return -1;
 199
 200 old_method:
 201         if (id && (TC_H_MAJ(id) == 0 ||
 202                    !(TC_H_MAJ(id^tp->q->handle)))) {
 203                 res->classid = id;
 204                 res->class = 0;
 205                 return 0;
 206         }
 207         return -1;
 208 }
 209
 210 static inline u32 to_hash(u32 id)
 211 {
 212         u32 h = id&0xFF;
 213         if (id&0x8000)
 214                 h += 256;
 215         return h;
 216 }
 217
 218 static inline u32 from_hash(u32 id)
 219 {
 220         id &= 0xFFFF;
 221         if (id == 0xFFFF)
 222                 return 32;
 223         if (!(id & 0x8000)) {
 224                 if (id > 255)
 225                         return 256;
 226                 return id&0xF;
 227         }
 228         return 16 + (id&0xF);
 229 }
 230
 231 static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
 232 {
 233         struct route4_head *head = (struct route4_head*)tp->root;
 234         struct route4_bucket *b;
 235         struct route4_filter *f;
 236         unsigned h1, h2;
 237
 238         if (!head)
 239                 return 0;
 240
 241         h1 = to_hash(handle);
 242         if (h1 > 256)
 243                 return 0;
 244
 245         h2 = from_hash(handle>>16);
 246         if (h2 > 32)
 247                 return 0;
 248
 249         if ((b = head->table[h1]) != NULL) {
 250                 for (f = b->ht[h2]; f; f = f->next)
 251                         if (f->handle == handle)
 252                                 return (unsigned long)f;
 253         }
 254         return 0;
 255 }
 256
 257 static void route4_put(struct tcf_proto *tp, unsigned long f)
 258 {
 259 }
 260
 261 static int route4_init(struct tcf_proto *tp)
 262 {
 263         return 0;
 264 }
 265
 266 static inline void
 267 route4_delete_filter(struct tcf_proto *tp, struct route4_filter *f)
 268 {
 269         tcf_unbind_filter(tp, &f->res);
 270         tcf_exts_destroy(tp, &f->exts);
 271         kfree(f);
 272 }
 273
 274 static void route4_destroy(struct tcf_proto *tp)
 275 {
 276         struct route4_head *head = xchg(&tp->root, NULL);
 277         int h1, h2;
 278
 279         if (head == NULL)
 280                 return;
 281
 282         for (h1=0; h1<=256; h1++) {
 283                 struct route4_bucket *b;
 284
 285                 if ((b = head->table[h1]) != NULL) {
 286                         for (h2=0; h2<=32; h2++) {
 287                                 struct route4_filter *f;
 288
 289                                 while ((f = b->ht[h2]) != NULL) {
 290                                         b->ht[h2] = f->next;
 291                                         route4_delete_filter(tp, f);
 292                                 }
 293                         }
 294                         kfree(b);
 295                 }
 296         }
 297         kfree(head);
 298 }
 299
 300 static int route4_delete(struct tcf_proto *tp, unsigned long arg)
 301 {
 302         struct route4_head *head = (struct route4_head*)tp->root;
 303         struct route4_filter **fp, *f = (struct route4_filter*)arg;
 304         unsigned h = 0;
 305         struct route4_bucket *b;
 306         int i;
 307
 308         if (!head || !f)
 309                 return -EINVAL;
 310
 311         h = f->handle;
 312         b = f->bkt;
 313
 314         for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {
 315                 if (*fp == f) {
 316                         tcf_tree_lock(tp);
 317                         *fp = f->next;
 318                         tcf_tree_unlock(tp);
 319
 320                         route4_reset_fastmap(tp->q->dev, head, f->id);
 321                         route4_delete_filter(tp, f);
 322
 323                         /* Strip tree */
 324
 325                         for (i=0; i<=32; i++)
 326                                 if (b->ht[i])
 327                                         return 0;
 328
 329                         /* OK, session has no flows */
 330                         tcf_tree_lock(tp);
 331                         head->table[to_hash(h)] = NULL;
 332                         tcf_tree_unlock(tp);
 333
 334                         kfree(b);
 335                         return 0;
 336                 }
 337         }
 338         return 0;
 339 }
 340
 341 static int route4_set_parms(struct tcf_proto *tp, unsigned long base,
 342         struct route4_filter *f, u32 handle, struct route4_head *head,
 343         struct rtattr **tb, struct rtattr *est, int new)
 344 {
 345         int err;
 346         u32 id = 0, to = 0, nhandle = 0x8000;
 347         struct route4_filter *fp;
 348         unsigned int h1;
 349         struct route4_bucket *b;
 350         struct tcf_exts e;
 351
 352         err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map);
 353         if (err < 0)
 354                 return err;
 355
 356         err = -EINVAL;
 357         if (tb[TCA_ROUTE4_CLASSID-1])
 358                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < sizeof(u32))
 359                         goto errout;
 360
 361         if (tb[TCA_ROUTE4_TO-1]) {
 362                 if (new && handle & 0x8000)
 363                         goto errout;
 364                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < sizeof(u32))
 365                         goto errout;
 366                 to = *(u32*)RTA_DATA(tb[TCA_ROUTE4_TO-1]);
 367                 if (to > 0xFF)
 368                         goto errout;
 369                 nhandle = to;
 370         }
 371
 372         if (tb[TCA_ROUTE4_FROM-1]) {
 373                 if (tb[TCA_ROUTE4_IIF-1])
 374                         goto errout;
 375                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < sizeof(u32))
 376                         goto errout;
 377                 id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_FROM-1]);
 378                 if (id > 0xFF)
 379                         goto errout;
 380                 nhandle |= id << 16;
 381         } else if (tb[TCA_ROUTE4_IIF-1]) {
 382                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < sizeof(u32))
 383                         goto errout;
 384                 id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);
 385                 if (id > 0x7FFF)
 386                         goto errout;
 387                 nhandle |= (id | 0x8000) << 16;
 388         } else
 389                 nhandle |= 0xFFFF << 16;
 390
 391         if (handle && new) {
 392                 nhandle |= handle & 0x7F00;
 393                 if (nhandle != handle)
 394                         goto errout;
 395         }
 396
 397         h1 = to_hash(nhandle);
 398         if ((b = head->table[h1]) == NULL) {
 399                 err = -ENOBUFS;
 400                 b = kmalloc(sizeof(struct route4_bucket), GFP_KERNEL);
 401                 if (b == NULL)
 402                         goto errout;
 403                 memset(b, 0, sizeof(*b));
 404
 405                 tcf_tree_lock(tp);
 406                 head->table[h1] = b;
 407                 tcf_tree_unlock(tp);
 408         } else {
 409                 unsigned int h2 = from_hash(nhandle >> 16);
 410                 err = -EEXIST;
 411                 for (fp = b->ht[h2]; fp; fp = fp->next)
 412                         if (fp->handle == f->handle)
 413                                 goto errout;
 414         }
 415
 416         tcf_tree_lock(tp);
 417         if (tb[TCA_ROUTE4_TO-1])
 418                 f->id = to;
 419
 420         if (tb[TCA_ROUTE4_FROM-1])
 421                 f->id = to | id<<16;
 422         else if (tb[TCA_ROUTE4_IIF-1])
 423                 f->iif = id;
 424
 425         f->handle = nhandle;
 426         f->bkt = b;
 427         tcf_tree_unlock(tp);
 428
 429         if (tb[TCA_ROUTE4_CLASSID-1]) {
 430                 f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
 431                 tcf_bind_filter(tp, &f->res, base);
 432         }
 433
 434         tcf_exts_change(tp, &f->exts, &e);
 435
 436         return 0;
 437 errout:
 438         tcf_exts_destroy(tp, &e);
 439         return err;
 440 }
 441
 442 static int route4_change(struct tcf_proto *tp, unsigned long base,
 443                        u32 handle,
 444                        struct rtattr **tca,
 445                        unsigned long *arg)
 446 {
 447         struct route4_head *head = tp->root;
 448         struct route4_filter *f, *f1, **fp;
 449         struct route4_bucket *b;
 450         struct rtattr *opt = tca[TCA_OPTIONS-1];
 451         struct rtattr *tb[TCA_ROUTE4_MAX];
 452         unsigned int h, th;
 453         u32 old_handle = 0;
 454         int err;
 455
 456         if (opt == NULL)
 457                 return handle ? -EINVAL : 0;
 458
 459         if (rtattr_parse_nested(tb, TCA_ROUTE4_MAX, opt) < 0)
 460                 return -EINVAL;
 461
 462         if ((f = (struct route4_filter*)*arg) != NULL) {
 463                 if (f->handle != handle && handle)
 464                         return -EINVAL;
 465
 466                 if (f->bkt)
 467                         old_handle = f->handle;
 468
 469                 err = route4_set_parms(tp, base, f, handle, head, tb,
 470                         tca[TCA_RATE-1], 0);
 471                 if (err < 0)
 472                         return err;
 473
 474                 goto reinsert;
 475         }
 476
 477         err = -ENOBUFS;
 478         if (head == NULL) {
 479                 head = kmalloc(sizeof(struct route4_head), GFP_KERNEL);
 480                 if (head == NULL)
 481                         goto errout;
 482                 memset(head, 0, sizeof(struct route4_head));
 483
 484                 tcf_tree_lock(tp);
 485                 tp->root = head;
 486                 tcf_tree_unlock(tp);
 487         }
 488
 489         f = kmalloc(sizeof(struct route4_filter), GFP_KERNEL);
 490         if (f == NULL)
 491                 goto errout;
 492         memset(f, 0, sizeof(*f));
 493
 494         err = route4_set_parms(tp, base, f, handle, head, tb,
 495                 tca[TCA_RATE-1], 1);
 496         if (err < 0)
 497                 goto errout;
 498
 499 reinsert:
 500         h = from_hash(f->handle >> 16);
 501         for (fp = &f->bkt->ht[h]; (f1=*fp) != NULL; fp = &f1->next)
 502                 if (f->handle < f1->handle)
 503                         break;
 504
 505         f->next = f1;
 506         tcf_tree_lock(tp);
 507         *fp = f;
 508
 509         if (old_handle && f->handle != old_handle) {
 510                 th = to_hash(old_handle);
 511                 h = from_hash(old_handle >> 16);
 512                 if ((b = head->table[th]) != NULL) {
 513                         for (fp = &b->ht[h]; *fp; fp = &(*fp)->next) {
 514                                 if (*fp == f) {
 515                                         *fp = f->next;
 516                                         break;
 517                                 }
 518                         }
 519                 }
 520         }
 521         tcf_tree_unlock(tp);
 522
 523         route4_reset_fastmap(tp->q->dev, head, f->id);
 524         *arg = (unsigned long)f;
 525         return 0;
 526
 527 errout:
 528         kfree(f);
 529         return err;
 530 }
 531
 532 static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
 533 {
 534         struct route4_head *head = tp->root;
 535         unsigned h, h1;
 536
 537         if (head == NULL)
 538                 arg->stop = 1;
 539
 540         if (arg->stop)
 541                 return;
 542
 543         for (h = 0; h <= 256; h++) {
 544                 struct route4_bucket *b = head->table[h];
 545
 546                 if (b) {
 547                         for (h1 = 0; h1 <= 32; h1++) {
 548                                 struct route4_filter *f;
 549
 550                                 for (f = b->ht[h1]; f; f = f->next) {
 551                                         if (arg->count < arg->skip) {
 552                                                 arg->count++;
 553                                                 continue;
 554                                         }
 555                                         if (arg->fn(tp, (unsigned long)f, arg) < 0) {
 556                                                 arg->stop = 1;
 557                                                 return;
 558                                         }
 559                                         arg->count++;
 560                                 }
 561                         }
 562                 }
 563         }
 564 }
 565
 566 static int route4_dump(struct tcf_proto *tp, unsigned long fh,
 567                        struct sk_buff *skb, struct tcmsg *t)
 568 {
 569         struct route4_filter *f = (struct route4_filter*)fh;
 570         unsigned char    *b = skb->tail;
 571         struct rtattr *rta;
 572         u32 id;
 573
 574         if (f == NULL)
 575                 return skb->len;
 576
 577         t->tcm_handle = f->handle;
 578
 579         rta = (struct rtattr*)b;
 580         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 581
 582         if (!(f->handle&0x8000)) {
 583                 id = f->id&0xFF;
 584                 RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);
 585         }
 586         if (f->handle&0x80000000) {
 587                 if ((f->handle>>16) != 0xFFFF)
 588                         RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
 589         } else {
 590                 id = f->id>>16;
 591                 RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
 592         }
 593         if (f->res.classid)
 594                 RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);
 595
 596         if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
 597                 goto rtattr_failure;
 598
 599         rta->rta_len = skb->tail - b;
 600
 601         if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0)
 602                 goto rtattr_failure;
 603
 604         return skb->len;
 605
 606 rtattr_failure:
 607         skb_trim(skb, b - skb->data);
 608         return -1;
 609 }
 610
 611 static struct tcf_proto_ops cls_route4_ops = {
 612         .next           =       NULL,
 613         .kind           =       "route",
 614         .classify       =       route4_classify,
 615         .init           =       route4_init,
 616         .destroy        =       route4_destroy,
 617         .get            =       route4_get,
 618         .put            =       route4_put,
 619         .change         =       route4_change,
 620         .delete         =       route4_delete,
 621         .walk           =       route4_walk,
 622         .dump           =       route4_dump,
 623         .owner          =       THIS_MODULE,
 624 };
 625
 626 static int __init init_route4(void)
 627 {
 628         return register_tcf_proto_ops(&cls_route4_ops);
 629 }
 630
 631 static void __exit exit_route4(void)
 632 {
 633         unregister_tcf_proto_ops(&cls_route4_ops);
 634 }
 635
 636 module_init(init_route4)
 637 module_exit(exit_route4)
 638 MODULE_LICENSE("GPL");