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