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