drivers/net/shaper.c

   1 /*
   2  *                      Simple traffic shaper for Linux NET3.
   3  *
   4  *      (c) Copyright 1996 Alan Cox <alan@redhat.com>, All Rights Reserved.
   5  *                              http://www.redhat.com
   6  *
   7  *      This program is free software; you can redistribute it and/or
   8  *      modify it under the terms of the GNU General Public License
   9  *      as published by the Free Software Foundation; either version
  10  *      2 of the License, or (at your option) any later version.
  11  *
  12  *      Neither Alan Cox nor CymruNet Ltd. admit liability nor provide
  13  *      warranty for any of this software. This material is provided
  14  *      "AS-IS" and at no charge.
  15  *
  16  *
  17  *      Algorithm:
  18  *
  19  *      Queue Frame:
  20  *              Compute time length of frame at regulated speed
  21  *              Add frame to queue at appropriate point
  22  *              Adjust time length computation for followup frames
  23  *              Any frame that falls outside of its boundaries is freed
  24  *
  25  *      We work to the following constants
  26  *
  27  *              SHAPER_QLEN     Maximum queued frames
  28  *              SHAPER_LATENCY  Bounding latency on a frame. Leaving this latency
  29  *                              window drops the frame. This stops us queueing
  30  *                              frames for a long time and confusing a remote
  31  *                              host.
  32  *              SHAPER_MAXSLIP  Maximum time a priority frame may jump forward.
  33  *                              That bounds the penalty we will inflict on low
  34  *                              priority traffic.
  35  *              SHAPER_BURST    Time range we call "now" in order to reduce
  36  *                              system load. The more we make this the burstier
  37  *                              the behaviour, the better local performance you
  38  *                              get through packet clustering on routers and the
  39  *                              worse the remote end gets to judge rtts.
  40  *
  41  *      This is designed to handle lower speed links ( < 200K/second or so). We
  42  *      run off a 100-150Hz base clock typically. This gives us a resolution at
  43  *      200Kbit/second of about 2Kbit or 256 bytes. Above that our timer
  44  *      resolution may start to cause much more burstiness in the traffic. We
  45  *      could avoid a lot of that by calling kick_shaper() at the end of the
  46  *      tied device transmissions. If you run above about 100K second you
  47  *      may need to tune the supposed speed rate for the right values.
  48  *
  49  *      BUGS:
  50  *              Downing the interface under the shaper before the shaper
  51  *              will render your machine defunct. Don't for now shape over
  52  *              PPP or SLIP therefore!
  53  *              This will be fixed in BETA4
  54  *
  55  * Update History :
  56  *
  57  *              bh_atomic() SMP races fixes and rewritten the locking code to
  58  *              be SMP safe and irq-mask friendly.
  59  *              NOTE: we can't use start_bh_atomic() in kick_shaper()
  60  *              because it's going to be recalled from an irq handler,
  61  *              and synchronize_bh() is a nono if called from irq context.
  62  *                                              1999  Andrea Arcangeli
  63  *
  64  *              Device statistics (tx_pakets, tx_bytes,
  65  *              tx_drops: queue_over_time and collisions: max_queue_exceded)
  66  *                               1999/06/18 Jordi Murgo <savage@apostols.org>
  67  *
  68  *              Use skb->cb for private data.
  69  *                               2000/03 Andi Kleen
  70  */
  71
  72 #include <linux/config.h>
  73 #include <linux/module.h>
  74 #include <linux/kernel.h>
  75 #include <linux/fcntl.h>
  76 #include <linux/mm.h>
  77 #include <linux/slab.h>
  78 #include <linux/string.h>
  79 #include <linux/errno.h>
  80 #include <linux/netdevice.h>
  81 #include <linux/etherdevice.h>
  82 #include <linux/skbuff.h>
  83 #include <linux/if_arp.h>
  84 #include <linux/init.h>
  85 #include <linux/if_shaper.h>
  86
  87 #include <net/dst.h>
  88 #include <net/arp.h>
  89
  90 struct shaper_cb {
  91         unsigned long   shapeclock;             /* Time it should go out */
  92         unsigned long   shapestamp;             /* Stamp for shaper    */
  93         __u32           shapelatency;           /* Latency on frame */
  94         __u32           shapelen;               /* Frame length in clocks */
  95         __u16           shapepend;              /* Pending */
  96 };
  97 #define SHAPERCB(skb) ((struct shaper_cb *) ((skb)->cb))
  98
  99 static int sh_debug;            /* Debug flag */
 100
 101 #define SHAPER_BANNER   "CymruNet Traffic Shaper BETA 0.04 for Linux 2.1\n"
 102
 103 static void shaper_kick(struct shaper *sh);
 104
 105 /*
 106  *      Compute clocks on a buffer
 107  */
 108
 109 static int shaper_clocks(struct shaper *shaper, struct sk_buff *skb)
 110 {
 111         int t=skb->len/shaper->bytespertick;
 112         return t;
 113 }
 114
 115 /*
 116  *      Set the speed of a shaper. We compute this in bytes per tick since
 117  *      thats how the machine wants to run. Quoted input is in bits per second
 118  *      as is traditional (note not BAUD). We assume 8 bit bytes.
 119  */
 120
 121 static void shaper_setspeed(struct shaper *shaper, int bitspersec)
 122 {
 123         shaper->bitspersec=bitspersec;
 124         shaper->bytespertick=(bitspersec/HZ)/8;
 125         if(!shaper->bytespertick)
 126                 shaper->bytespertick++;
 127 }
 128
 129 /*
 130  *      Throw a frame at a shaper.
 131  */
 132
 133
 134 static int shaper_start_xmit(struct sk_buff *skb, struct net_device *dev)
 135 {
 136         struct shaper *shaper = dev->priv;
 137         struct sk_buff *ptr;
 138
 139         if (down_trylock(&shaper->sem))
 140                 return -1;
 141
 142         ptr=shaper->sendq.prev;
 143
 144         /*
 145          *      Set up our packet details
 146          */
 147
 148         SHAPERCB(skb)->shapelatency=0;
 149         SHAPERCB(skb)->shapeclock=shaper->recovery;
 150         if(time_before(SHAPERCB(skb)->shapeclock, jiffies))
 151                 SHAPERCB(skb)->shapeclock=jiffies;
 152         skb->priority=0;        /* short term bug fix */
 153         SHAPERCB(skb)->shapestamp=jiffies;
 154
 155         /*
 156          *      Time slots for this packet.
 157          */
 158
 159         SHAPERCB(skb)->shapelen= shaper_clocks(shaper,skb);
 160
 161 #ifdef SHAPER_COMPLEX /* and broken.. */
 162
 163         while(ptr && ptr!=(struct sk_buff *)&shaper->sendq)
 164         {
 165                 if(ptr->pri<skb->pri
 166                         && jiffies - SHAPERCB(ptr)->shapeclock < SHAPER_MAXSLIP)
 167                 {
 168                         struct sk_buff *tmp=ptr->prev;
 169
 170                         /*
 171                          *      It goes before us therefore we slip the length
 172                          *      of the new frame.
 173                          */
 174
 175                         SHAPERCB(ptr)->shapeclock+=SHAPERCB(skb)->shapelen;
 176                         SHAPERCB(ptr)->shapelatency+=SHAPERCB(skb)->shapelen;
 177
 178                         /*
 179                          *      The packet may have slipped so far back it
 180                          *      fell off.
 181                          */
 182                         if(SHAPERCB(ptr)->shapelatency > SHAPER_LATENCY)
 183                         {
 184                                 skb_unlink(ptr);
 185                                 dev_kfree_skb(ptr);
 186                         }
 187                         ptr=tmp;
 188                 }
 189                 else
 190                         break;
 191         }
 192         if(ptr==NULL || ptr==(struct sk_buff *)&shaper->sendq)
 193                 skb_queue_head(&shaper->sendq,skb);
 194         else
 195         {
 196                 struct sk_buff *tmp;
 197                 /*
 198                  *      Set the packet clock out time according to the
 199                  *      frames ahead. Im sure a bit of thought could drop
 200                  *      this loop.
 201                  */
 202                 for(tmp=skb_peek(&shaper->sendq); tmp!=NULL && tmp!=ptr; tmp=tmp->next)
 203                         SHAPERCB(skb)->shapeclock+=tmp->shapelen;
 204                 skb_append(ptr,skb);
 205         }
 206 #else
 207         {
 208                 struct sk_buff *tmp;
 209                 /*
 210                  *      Up our shape clock by the time pending on the queue
 211                  *      (Should keep this in the shaper as a variable..)
 212                  */
 213                 for(tmp=skb_peek(&shaper->sendq); tmp!=NULL &&
 214                         tmp!=(struct sk_buff *)&shaper->sendq; tmp=tmp->next)
 215                         SHAPERCB(skb)->shapeclock+=SHAPERCB(tmp)->shapelen;
 216                 /*
 217                  *      Queue over time. Spill packet.
 218                  */
 219                 if(SHAPERCB(skb)->shapeclock-jiffies > SHAPER_LATENCY) {
 220                         dev_kfree_skb(skb);
 221                         shaper->stats.tx_dropped++;
 222                 } else
 223                         skb_queue_tail(&shaper->sendq, skb);
 224         }
 225 #endif
 226         if(sh_debug)
 227                 printk("Frame queued.\n");
 228         if(skb_queue_len(&shaper->sendq)>SHAPER_QLEN)
 229         {
 230                 ptr=skb_dequeue(&shaper->sendq);
 231                 dev_kfree_skb(ptr);
 232                 shaper->stats.collisions++;
 233         }
 234         shaper_kick(shaper);
 235         up(&shaper->sem);
 236         return 0;
 237 }
 238
 239 /*
 240  *      Transmit from a shaper
 241  */
 242
 243 static void shaper_queue_xmit(struct shaper *shaper, struct sk_buff *skb)
 244 {
 245         struct sk_buff *newskb=skb_clone(skb, GFP_ATOMIC);
 246         if(sh_debug)
 247                 printk("Kick frame on %p\n",newskb);
 248         if(newskb)
 249         {
 250                 newskb->dev=shaper->dev;
 251                 newskb->priority=2;
 252                 if(sh_debug)
 253                         printk("Kick new frame to %s, %d\n",
 254                                 shaper->dev->name,newskb->priority);
 255                 dev_queue_xmit(newskb);
 256
 257                 shaper->stats.tx_bytes += skb->len;
 258                 shaper->stats.tx_packets++;
 259
 260                 if(sh_debug)
 261                         printk("Kicked new frame out.\n");
 262                 dev_kfree_skb(skb);
 263         }
 264 }
 265
 266 /*
 267  *      Timer handler for shaping clock
 268  */
 269
 270 static void shaper_timer(unsigned long data)
 271 {
 272         struct shaper *shaper = (struct shaper *)data;
 273
 274         if (!down_trylock(&shaper->sem)) {
 275                 shaper_kick(shaper);
 276                 up(&shaper->sem);
 277         } else
 278                 mod_timer(&shaper->timer, jiffies);
 279 }
 280
 281 /*
 282  *      Kick a shaper queue and try and do something sensible with the
 283  *      queue.
 284  */
 285
 286 static void shaper_kick(struct shaper *shaper)
 287 {
 288         struct sk_buff *skb;
 289
 290         /*
 291          *      Walk the list (may be empty)
 292          */
 293
 294         while((skb=skb_peek(&shaper->sendq))!=NULL)
 295         {
 296                 /*
 297                  *      Each packet due to go out by now (within an error
 298                  *      of SHAPER_BURST) gets kicked onto the link
 299                  */
 300
 301                 if(sh_debug)
 302                         printk("Clock = %ld, jiffies = %ld\n", SHAPERCB(skb)->shapeclock, jiffies);
 303                 if(time_before_eq(SHAPERCB(skb)->shapeclock, jiffies + SHAPER_BURST))
 304                 {
 305                         /*
 306                          *      Pull the frame and get interrupts back on.
 307                          */
 308
 309                         skb_unlink(skb);
 310                         if (shaper->recovery <
 311                             SHAPERCB(skb)->shapeclock + SHAPERCB(skb)->shapelen)
 312                                 shaper->recovery = SHAPERCB(skb)->shapeclock + SHAPERCB(skb)->shapelen;
 313                         /*
 314                          *      Pass on to the physical target device via
 315                          *      our low level packet thrower.
 316                          */
 317
 318                         SHAPERCB(skb)->shapepend=0;
 319                         shaper_queue_xmit(shaper, skb); /* Fire */
 320                 }
 321                 else
 322                         break;
 323         }
 324
 325         /*
 326          *      Next kick.
 327          */
 328
 329         if(skb!=NULL)
 330                 mod_timer(&shaper->timer, SHAPERCB(skb)->shapeclock);
 331 }
 332
 333
 334 /*
 335  *      Flush the shaper queues on a closedown
 336  */
 337
 338 static void shaper_flush(struct shaper *shaper)
 339 {
 340         struct sk_buff *skb;
 341
 342         down(&shaper->sem);
 343         while((skb=skb_dequeue(&shaper->sendq))!=NULL)
 344                 dev_kfree_skb(skb);
 345         shaper_kick(shaper);
 346         up(&shaper->sem);
 347 }
 348
 349 /*
 350  *      Bring the interface up. We just disallow this until a
 351  *      bind.
 352  */
 353
 354 static int shaper_open(struct net_device *dev)
 355 {
 356         struct shaper *shaper=dev->priv;
 357
 358         /*
 359          *      Can't open until attached.
 360          *      Also can't open until speed is set, or we'll get
 361          *      a division by zero.
 362          */
 363
 364         if(shaper->dev==NULL)
 365                 return -ENODEV;
 366         if(shaper->bitspersec==0)
 367                 return -EINVAL;
 368         return 0;
 369 }
 370
 371 /*
 372  *      Closing a shaper flushes the queues.
 373  */
 374
 375 static int shaper_close(struct net_device *dev)
 376 {
 377         struct shaper *shaper=dev->priv;
 378         shaper_flush(shaper);
 379         del_timer_sync(&shaper->timer);
 380         return 0;
 381 }
 382
 383 /*
 384  *      Revectored calls. We alter the parameters and call the functions
 385  *      for our attached device. This enables us to bandwidth allocate after
 386  *      ARP and other resolutions and not before.
 387  */
 388
 389 static struct net_device_stats *shaper_get_stats(struct net_device *dev)
 390 {
 391         struct shaper *sh=dev->priv;
 392         return &sh->stats;
 393 }
 394
 395 static int shaper_header(struct sk_buff *skb, struct net_device *dev,
 396         unsigned short type, void *daddr, void *saddr, unsigned len)
 397 {
 398         struct shaper *sh=dev->priv;
 399         int v;
 400         if(sh_debug)
 401                 printk("Shaper header\n");
 402         skb->dev=sh->dev;
 403         v=sh->hard_header(skb,sh->dev,type,daddr,saddr,len);
 404         skb->dev=dev;
 405         return v;
 406 }
 407
 408 static int shaper_rebuild_header(struct sk_buff *skb)
 409 {
 410         struct shaper *sh=skb->dev->priv;
 411         struct net_device *dev=skb->dev;
 412         int v;
 413         if(sh_debug)
 414                 printk("Shaper rebuild header\n");
 415         skb->dev=sh->dev;
 416         v=sh->rebuild_header(skb);
 417         skb->dev=dev;
 418         return v;
 419 }
 420
 421 #if 0
 422 static int shaper_cache(struct neighbour *neigh, struct hh_cache *hh)
 423 {
 424         struct shaper *sh=neigh->dev->priv;
 425         struct net_device *tmp;
 426         int ret;
 427         if(sh_debug)
 428                 printk("Shaper header cache bind\n");
 429         tmp=neigh->dev;
 430         neigh->dev=sh->dev;
 431         ret=sh->hard_header_cache(neigh,hh);
 432         neigh->dev=tmp;
 433         return ret;
 434 }
 435
 436 static void shaper_cache_update(struct hh_cache *hh, struct net_device *dev,
 437         unsigned char *haddr)
 438 {
 439         struct shaper *sh=dev->priv;
 440         if(sh_debug)
 441                 printk("Shaper cache update\n");
 442         sh->header_cache_update(hh, sh->dev, haddr);
 443 }
 444 #endif
 445
 446 #ifdef CONFIG_INET
 447
 448 static int shaper_neigh_setup(struct neighbour *n)
 449 {
 450 #ifdef CONFIG_INET
 451         if (n->nud_state == NUD_NONE) {
 452                 n->ops = &arp_broken_ops;
 453                 n->output = n->ops->output;
 454         }
 455 #endif
 456         return 0;
 457 }
 458
 459 static int shaper_neigh_setup_dev(struct net_device *dev, struct neigh_parms *p)
 460 {
 461 #ifdef CONFIG_INET
 462         if (p->tbl->family == AF_INET) {
 463                 p->neigh_setup = shaper_neigh_setup;
 464                 p->ucast_probes = 0;
 465                 p->mcast_probes = 0;
 466         }
 467 #endif
 468         return 0;
 469 }
 470
 471 #else /* !(CONFIG_INET) */
 472
 473 static int shaper_neigh_setup_dev(struct net_device *dev, struct neigh_parms *p)
 474 {
 475         return 0;
 476 }
 477
 478 #endif
 479
 480 static int shaper_attach(struct net_device *shdev, struct shaper *sh, struct net_device *dev)
 481 {
 482         sh->dev = dev;
 483         sh->hard_start_xmit=dev->hard_start_xmit;
 484         sh->get_stats=dev->get_stats;
 485         if(dev->hard_header)
 486         {
 487                 sh->hard_header=dev->hard_header;
 488                 shdev->hard_header = shaper_header;
 489         }
 490         else
 491                 shdev->hard_header = NULL;
 492
 493         if(dev->rebuild_header)
 494         {
 495                 sh->rebuild_header      = dev->rebuild_header;
 496                 shdev->rebuild_header   = shaper_rebuild_header;
 497         }
 498         else
 499                 shdev->rebuild_header   = NULL;
 500
 501 #if 0
 502         if(dev->hard_header_cache)
 503         {
 504                 sh->hard_header_cache   = dev->hard_header_cache;
 505                 shdev->hard_header_cache= shaper_cache;
 506         }
 507         else
 508         {
 509                 shdev->hard_header_cache= NULL;
 510         }
 511
 512         if(dev->header_cache_update)
 513         {
 514                 sh->header_cache_update = dev->header_cache_update;
 515                 shdev->header_cache_update = shaper_cache_update;
 516         }
 517         else
 518                 shdev->header_cache_update= NULL;
 519 #else
 520         shdev->header_cache_update = NULL;
 521         shdev->hard_header_cache = NULL;
 522 #endif
 523         shdev->neigh_setup = shaper_neigh_setup_dev;
 524
 525         shdev->hard_header_len=dev->hard_header_len;
 526         shdev->type=dev->type;
 527         shdev->addr_len=dev->addr_len;
 528         shdev->mtu=dev->mtu;
 529         sh->bitspersec=0;
 530         return 0;
 531 }
 532
 533 static int shaper_ioctl(struct net_device *dev,  struct ifreq *ifr, int cmd)
 534 {
 535         struct shaperconf *ss= (struct shaperconf *)&ifr->ifr_ifru;
 536         struct shaper *sh=dev->priv;
 537
 538         if(ss->ss_cmd == SHAPER_SET_DEV || ss->ss_cmd == SHAPER_SET_SPEED)
 539         {
 540                 if(!capable(CAP_NET_ADMIN))
 541                         return -EPERM;
 542         }
 543
 544         switch(ss->ss_cmd)
 545         {
 546                 case SHAPER_SET_DEV:
 547                 {
 548                         struct net_device *them=__dev_get_by_name(ss->ss_name);
 549                         if(them==NULL)
 550                                 return -ENODEV;
 551                         if(sh->dev)
 552                                 return -EBUSY;
 553                         return shaper_attach(dev,dev->priv, them);
 554                 }
 555                 case SHAPER_GET_DEV:
 556                         if(sh->dev==NULL)
 557                                 return -ENODEV;
 558                         strcpy(ss->ss_name, sh->dev->name);
 559                         return 0;
 560                 case SHAPER_SET_SPEED:
 561                         shaper_setspeed(sh,ss->ss_speed);
 562                         return 0;
 563                 case SHAPER_GET_SPEED:
 564                         ss->ss_speed=sh->bitspersec;
 565                         return 0;
 566                 default:
 567                         return -EINVAL;
 568         }
 569 }
 570
 571 static void shaper_init_priv(struct net_device *dev)
 572 {
 573         struct shaper *sh = dev->priv;
 574
 575         skb_queue_head_init(&sh->sendq);
 576         init_timer(&sh->timer);
 577         sh->timer.function=shaper_timer;
 578         sh->timer.data=(unsigned long)sh;
 579 }
 580
 581 /*
 582  *      Add a shaper device to the system
 583  */
 584
 585 static void __init shaper_setup(struct net_device *dev)
 586 {
 587         /*
 588          *      Set up the shaper.
 589          */
 590
 591         SET_MODULE_OWNER(dev);
 592
 593         shaper_init_priv(dev);
 594
 595         dev->open               = shaper_open;
 596         dev->stop               = shaper_close;
 597         dev->hard_start_xmit    = shaper_start_xmit;
 598         dev->get_stats          = shaper_get_stats;
 599         dev->set_multicast_list = NULL;
 600
 601         /*
 602          *      Intialise the packet queues
 603          */
 604
 605         /*
 606          *      Handlers for when we attach to a device.
 607          */
 608
 609         dev->hard_header        = shaper_header;
 610         dev->rebuild_header     = shaper_rebuild_header;
 611 #if 0
 612         dev->hard_header_cache  = shaper_cache;
 613         dev->header_cache_update= shaper_cache_update;
 614 #endif
 615         dev->neigh_setup        = shaper_neigh_setup_dev;
 616         dev->do_ioctl           = shaper_ioctl;
 617         dev->hard_header_len    = 0;
 618         dev->type               = ARPHRD_ETHER; /* initially */
 619         dev->set_mac_address    = NULL;
 620         dev->mtu                = 1500;
 621         dev->addr_len           = 0;
 622         dev->tx_queue_len       = 10;
 623         dev->flags              = 0;
 624 }
 625
 626 static int shapers = 1;
 627 #ifdef MODULE
 628
 629 module_param(shapers, int, 0);
 630 MODULE_PARM_DESC(shapers, "Traffic shaper: maximum number of shapers");
 631
 632 #else /* MODULE */
 633
 634 static int __init set_num_shapers(char *str)
 635 {
 636         shapers = simple_strtol(str, NULL, 0);
 637         return 1;
 638 }
 639
 640 __setup("shapers=", set_num_shapers);
 641
 642 #endif /* MODULE */
 643
 644 static struct net_device **devs;
 645
 646 static unsigned int shapers_registered = 0;
 647
 648 static int __init shaper_init(void)
 649 {
 650         int i;
 651         size_t alloc_size;
 652         struct net_device *dev;
 653         char name[IFNAMSIZ];
 654
 655         if (shapers < 1)
 656                 return -ENODEV;
 657
 658         alloc_size = sizeof(*dev) * shapers;
 659         devs = kmalloc(alloc_size, GFP_KERNEL);
 660         if (!devs)
 661                 return -ENOMEM;
 662         memset(devs, 0, alloc_size);
 663
 664         for (i = 0; i < shapers; i++) {
 665
 666                 snprintf(name, IFNAMSIZ, "shaper%d", i);
 667                 dev = alloc_netdev(sizeof(struct shaper), name,
 668                                    shaper_setup);
 669                 if (!dev)
 670                         break;
 671
 672                 if (register_netdev(dev)) {
 673                         free_netdev(dev);
 674                         break;
 675                 }
 676
 677                 devs[i] = dev;
 678                 shapers_registered++;
 679         }
 680
 681         if (!shapers_registered) {
 682                 kfree(devs);
 683                 devs = NULL;
 684         }
 685
 686         return (shapers_registered ? 0 : -ENODEV);
 687 }
 688
 689 static void __exit shaper_exit (void)
 690 {
 691         int i;
 692
 693         for (i = 0; i < shapers_registered; i++) {
 694                 if (devs[i]) {
 695                         unregister_netdev(devs[i]);
 696                         free_netdev(devs[i]);
 697                 }
 698         }
 699
 700         kfree(devs);
 701         devs = NULL;
 702 }
 703
 704 module_init(shaper_init);
 705 module_exit(shaper_exit);
 706 MODULE_LICENSE("GPL");
 707