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