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