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 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 net_device *dev, struct route4_head *head, u32 id)
  77 {
  78         qdisc_lock_tree(dev);
  79         memset(head->fastmap, 0, sizeof(head->fastmap));
  80         qdisc_unlock_tree(dev);
  81 }
  82
  83 static inline void
  84 route4_set_fastmap(struct route4_head *head, u32 id, int iif,
  85                    struct route4_filter *f)
  86 {
  87         int h = route4_fastmap_hash(id, iif);
  88         head->fastmap[h].id = id;
  89         head->fastmap[h].iif = iif;
  90         head->fastmap[h].filter = f;
  91 }
  92
  93 static __inline__ int route4_hash_to(u32 id)
  94 {
  95         return id&0xFF;
  96 }
  97
  98 static __inline__ int route4_hash_from(u32 id)
  99 {
 100         return (id>>16)&0xF;
 101 }
 102
 103 static __inline__ int route4_hash_iif(int iif)
 104 {
 105         return 16 + ((iif>>16)&0xF);
 106 }
 107
 108 static __inline__ int route4_hash_wild(void)
 109 {
 110         return 32;
 111 }
 112
 113 #define ROUTE4_APPLY_RESULT()                                   \
 114 {                                                               \
 115         *res = f->res;                                          \
 116         if (tcf_exts_is_available(&f->exts)) {                  \
 117                 int r = tcf_exts_exec(skb, &f->exts, res);      \
 118                 if (r < 0) {                                    \
 119                         dont_cache = 1;                         \
 120                         continue;                               \
 121                 }                                               \
 122                 return r;                                       \
 123         } else if (!dont_cache)                                 \
 124                 route4_set_fastmap(head, id, iif, f);           \
 125         return 0;                                               \
 126 }
 127
 128 static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp,
 129                            struct tcf_result *res)
 130 {
 131         struct route4_head *head = (struct route4_head*)tp->root;
 132         struct dst_entry *dst;
 133         struct route4_bucket *b;
 134         struct route4_filter *f;
 135         u32 id, h;
 136         int iif, dont_cache = 0;
 137
 138         if ((dst = skb->dst) == NULL)
 139                 goto failure;
 140
 141         id = dst->tclassid;
 142         if (head == NULL)
 143                 goto old_method;
 144
 145         iif = ((struct rtable*)dst)->fl.iif;
 146
 147         h = route4_fastmap_hash(id, iif);
 148         if (id == head->fastmap[h].id &&
 149             iif == head->fastmap[h].iif &&
 150             (f = head->fastmap[h].filter) != NULL) {
 151                 if (f == ROUTE4_FAILURE)
 152                         goto failure;
 153
 154                 *res = f->res;
 155                 return 0;
 156         }
 157
 158         h = route4_hash_to(id);
 159
 160 restart:
 161         if ((b = head->table[h]) != NULL) {
 162                 for (f = b->ht[route4_hash_from(id)]; f; f = f->next)
 163                         if (f->id == id)
 164                                 ROUTE4_APPLY_RESULT();
 165
 166                 for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)
 167                         if (f->iif == iif)
 168                                 ROUTE4_APPLY_RESULT();
 169
 170                 for (f = b->ht[route4_hash_wild()]; f; f = f->next)
 171                         ROUTE4_APPLY_RESULT();
 172
 173         }
 174         if (h < 256) {
 175                 h = 256;
 176                 id &= ~0xFFFF;
 177                 goto restart;
 178         }
 179
 180         if (!dont_cache)
 181                 route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
 182 failure:
 183         return -1;
 184
 185 old_method:
 186         if (id && (TC_H_MAJ(id) == 0 ||
 187                    !(TC_H_MAJ(id^tp->q->handle)))) {
 188                 res->classid = id;
 189                 res->class = 0;
 190                 return 0;
 191         }
 192         return -1;
 193 }
 194
 195 static inline u32 to_hash(u32 id)
 196 {
 197         u32 h = id&0xFF;
 198         if (id&0x8000)
 199                 h += 256;
 200         return h;
 201 }
 202
 203 static inline u32 from_hash(u32 id)
 204 {
 205         id &= 0xFFFF;
 206         if (id == 0xFFFF)
 207                 return 32;
 208         if (!(id & 0x8000)) {
 209                 if (id > 255)
 210                         return 256;
 211                 return id&0xF;
 212         }
 213         return 16 + (id&0xF);
 214 }
 215
 216 static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
 217 {
 218         struct route4_head *head = (struct route4_head*)tp->root;
 219         struct route4_bucket *b;
 220         struct route4_filter *f;
 221         unsigned h1, h2;
 222
 223         if (!head)
 224                 return 0;
 225
 226         h1 = to_hash(handle);
 227         if (h1 > 256)
 228                 return 0;
 229
 230         h2 = from_hash(handle>>16);
 231         if (h2 > 32)
 232                 return 0;
 233
 234         if ((b = head->table[h1]) != NULL) {
 235                 for (f = b->ht[h2]; f; f = f->next)
 236                         if (f->handle == handle)
 237                                 return (unsigned long)f;
 238         }
 239         return 0;
 240 }
 241
 242 static void route4_put(struct tcf_proto *tp, unsigned long f)
 243 {
 244 }
 245
 246 static int route4_init(struct tcf_proto *tp)
 247 {
 248         return 0;
 249 }
 250
 251 static inline void
 252 route4_delete_filter(struct tcf_proto *tp, struct route4_filter *f)
 253 {
 254         tcf_unbind_filter(tp, &f->res);
 255         tcf_exts_destroy(tp, &f->exts);
 256         kfree(f);
 257 }
 258
 259 static void route4_destroy(struct tcf_proto *tp)
 260 {
 261         struct route4_head *head = xchg(&tp->root, NULL);
 262         int h1, h2;
 263
 264         if (head == NULL)
 265                 return;
 266
 267         for (h1=0; h1<=256; h1++) {
 268                 struct route4_bucket *b;
 269
 270                 if ((b = head->table[h1]) != NULL) {
 271                         for (h2=0; h2<=32; h2++) {
 272                                 struct route4_filter *f;
 273
 274                                 while ((f = b->ht[h2]) != NULL) {
 275                                         b->ht[h2] = f->next;
 276                                         route4_delete_filter(tp, f);
 277                                 }
 278                         }
 279                         kfree(b);
 280                 }
 281         }
 282         kfree(head);
 283 }
 284
 285 static int route4_delete(struct tcf_proto *tp, unsigned long arg)
 286 {
 287         struct route4_head *head = (struct route4_head*)tp->root;
 288         struct route4_filter **fp, *f = (struct route4_filter*)arg;
 289         unsigned h = 0;
 290         struct route4_bucket *b;
 291         int i;
 292
 293         if (!head || !f)
 294                 return -EINVAL;
 295
 296         h = f->handle;
 297         b = f->bkt;
 298
 299         for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {
 300                 if (*fp == f) {
 301                         tcf_tree_lock(tp);
 302                         *fp = f->next;
 303                         tcf_tree_unlock(tp);
 304
 305                         route4_reset_fastmap(tp->q->dev, head, f->id);
 306                         route4_delete_filter(tp, f);
 307
 308                         /* Strip tree */
 309
 310                         for (i=0; i<=32; i++)
 311                                 if (b->ht[i])
 312                                         return 0;
 313
 314                         /* OK, session has no flows */
 315                         tcf_tree_lock(tp);
 316                         head->table[to_hash(h)] = NULL;
 317                         tcf_tree_unlock(tp);
 318
 319                         kfree(b);
 320                         return 0;
 321                 }
 322         }
 323         return 0;
 324 }
 325
 326 static int route4_set_parms(struct tcf_proto *tp, unsigned long base,
 327         struct route4_filter *f, u32 handle, struct route4_head *head,
 328         struct rtattr **tb, struct rtattr *est, int new)
 329 {
 330         int err;
 331         u32 id = 0, to = 0, nhandle = 0x8000;
 332         struct route4_filter *fp;
 333         unsigned int h1;
 334         struct route4_bucket *b;
 335         struct tcf_exts e;
 336
 337         err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map);
 338         if (err < 0)
 339                 return err;
 340
 341         err = -EINVAL;
 342         if (tb[TCA_ROUTE4_CLASSID-1])
 343                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < sizeof(u32))
 344                         goto errout;
 345
 346         if (tb[TCA_ROUTE4_TO-1]) {
 347                 if (new && handle & 0x8000)
 348                         goto errout;
 349                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < sizeof(u32))
 350                         goto errout;
 351                 to = *(u32*)RTA_DATA(tb[TCA_ROUTE4_TO-1]);
 352                 if (to > 0xFF)
 353                         goto errout;
 354                 nhandle = to;
 355         }
 356
 357         if (tb[TCA_ROUTE4_FROM-1]) {
 358                 if (tb[TCA_ROUTE4_IIF-1])
 359                         goto errout;
 360                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < sizeof(u32))
 361                         goto errout;
 362                 id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_FROM-1]);
 363                 if (id > 0xFF)
 364                         goto errout;
 365                 nhandle |= id << 16;
 366         } else if (tb[TCA_ROUTE4_IIF-1]) {
 367                 if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < sizeof(u32))
 368                         goto errout;
 369                 id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);
 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-1])
 402                 f->id = to;
 403
 404         if (tb[TCA_ROUTE4_FROM-1])
 405                 f->id = to | id<<16;
 406         else if (tb[TCA_ROUTE4_IIF-1])
 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-1]) {
 414                 f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
 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 rtattr **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 rtattr *opt = tca[TCA_OPTIONS-1];
 435         struct rtattr *tb[TCA_ROUTE4_MAX];
 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         if (rtattr_parse_nested(tb, TCA_ROUTE4_MAX, opt) < 0)
 444                 return -EINVAL;
 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-1], 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], 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->dev, 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 rtattr *rta;
 554         u32 id;
 555
 556         if (f == NULL)
 557                 return skb->len;
 558
 559         t->tcm_handle = f->handle;
 560
 561         rta = (struct rtattr*)b;
 562         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 563
 564         if (!(f->handle&0x8000)) {
 565                 id = f->id&0xFF;
 566                 RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);
 567         }
 568         if (f->handle&0x80000000) {
 569                 if ((f->handle>>16) != 0xFFFF)
 570                         RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
 571         } else {
 572                 id = f->id>>16;
 573                 RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
 574         }
 575         if (f->res.classid)
 576                 RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);
 577
 578         if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
 579                 goto rtattr_failure;
 580
 581         rta->rta_len = skb_tail_pointer(skb) - b;
 582
 583         if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0)
 584                 goto rtattr_failure;
 585
 586         return skb->len;
 587
 588 rtattr_failure:
 589         nlmsg_trim(skb, b);
 590         return -1;
 591 }
 592
 593 static struct tcf_proto_ops cls_route4_ops = {
 594         .next           =       NULL,
 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");