Merge master.kernel.org:/pub/scm/linux/kernel/git/davem/sparc-2.6
[linux-2.6] / 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/module.h>
73 #include <linux/kernel.h>
74 #include <linux/fcntl.h>
75 #include <linux/mm.h>
76 #include <linux/slab.h>
77 #include <linux/string.h>
78 #include <linux/errno.h>
79 #include <linux/netdevice.h>
80 #include <linux/etherdevice.h>
81 #include <linux/skbuff.h>
82 #include <linux/if_arp.h>
83 #include <linux/init.h>
84 #include <linux/if_shaper.h>
85 #include <linux/jiffies.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         spin_lock(&shaper->lock);
140         ptr=shaper->sendq.prev;
141         
142         /*
143          *      Set up our packet details
144          */
145          
146         SHAPERCB(skb)->shapelatency=0;
147         SHAPERCB(skb)->shapeclock=shaper->recovery;
148         if(time_before(SHAPERCB(skb)->shapeclock, jiffies))
149                 SHAPERCB(skb)->shapeclock=jiffies;
150         skb->priority=0;        /* short term bug fix */
151         SHAPERCB(skb)->shapestamp=jiffies;
152         
153         /*
154          *      Time slots for this packet.
155          */
156          
157         SHAPERCB(skb)->shapelen= shaper_clocks(shaper,skb);
158         
159         {
160                 struct sk_buff *tmp;
161                 /*
162                  *      Up our shape clock by the time pending on the queue
163                  *      (Should keep this in the shaper as a variable..)
164                  */
165                 for(tmp=skb_peek(&shaper->sendq); tmp!=NULL && 
166                         tmp!=(struct sk_buff *)&shaper->sendq; tmp=tmp->next)
167                         SHAPERCB(skb)->shapeclock+=SHAPERCB(tmp)->shapelen;
168                 /*
169                  *      Queue over time. Spill packet.
170                  */
171                 if(time_after(SHAPERCB(skb)->shapeclock,jiffies + SHAPER_LATENCY)) {
172                         dev_kfree_skb(skb);
173                         shaper->stats.tx_dropped++;
174                 } else
175                         skb_queue_tail(&shaper->sendq, skb);
176         }
177
178         if(sh_debug)
179                 printk("Frame queued.\n");
180         if(skb_queue_len(&shaper->sendq)>SHAPER_QLEN)
181         {
182                 ptr=skb_dequeue(&shaper->sendq);
183                 dev_kfree_skb(ptr);
184                 shaper->stats.collisions++;
185         }
186         shaper_kick(shaper);
187         spin_unlock(&shaper->lock);
188         return 0;
189 }
190
191 /*
192  *      Transmit from a shaper
193  */
194  
195 static void shaper_queue_xmit(struct shaper *shaper, struct sk_buff *skb)
196 {
197         struct sk_buff *newskb=skb_clone(skb, GFP_ATOMIC);
198         if(sh_debug)
199                 printk("Kick frame on %p\n",newskb);
200         if(newskb)
201         {
202                 newskb->dev=shaper->dev;
203                 newskb->priority=2;
204                 if(sh_debug)
205                         printk("Kick new frame to %s, %d\n",
206                                 shaper->dev->name,newskb->priority);
207                 dev_queue_xmit(newskb);
208
209                 shaper->stats.tx_bytes += skb->len;
210                 shaper->stats.tx_packets++;
211
212                 if(sh_debug)
213                         printk("Kicked new frame out.\n");
214                 dev_kfree_skb(skb);
215         }
216 }
217
218 /*
219  *      Timer handler for shaping clock
220  */
221  
222 static void shaper_timer(unsigned long data)
223 {
224         struct shaper *shaper = (struct shaper *)data;
225
226         spin_lock(&shaper->lock);
227         shaper_kick(shaper);
228         spin_unlock(&shaper->lock);
229 }
230
231 /*
232  *      Kick a shaper queue and try and do something sensible with the 
233  *      queue. 
234  */
235
236 static void shaper_kick(struct shaper *shaper)
237 {
238         struct sk_buff *skb;
239         
240         /*
241          *      Walk the list (may be empty)
242          */
243          
244         while((skb=skb_peek(&shaper->sendq))!=NULL)
245         {
246                 /*
247                  *      Each packet due to go out by now (within an error
248                  *      of SHAPER_BURST) gets kicked onto the link 
249                  */
250                  
251                 if(sh_debug)
252                         printk("Clock = %ld, jiffies = %ld\n", SHAPERCB(skb)->shapeclock, jiffies);
253                 if(time_before_eq(SHAPERCB(skb)->shapeclock, jiffies + SHAPER_BURST))
254                 {
255                         /*
256                          *      Pull the frame and get interrupts back on.
257                          */
258                          
259                         skb_unlink(skb, &shaper->sendq);
260                         if (shaper->recovery < 
261                             SHAPERCB(skb)->shapeclock + SHAPERCB(skb)->shapelen)
262                                 shaper->recovery = SHAPERCB(skb)->shapeclock + SHAPERCB(skb)->shapelen;
263                         /*
264                          *      Pass on to the physical target device via
265                          *      our low level packet thrower.
266                          */
267                         
268                         SHAPERCB(skb)->shapepend=0;
269                         shaper_queue_xmit(shaper, skb); /* Fire */
270                 }
271                 else
272                         break;
273         }
274
275         /*
276          *      Next kick.
277          */
278          
279         if(skb!=NULL)
280                 mod_timer(&shaper->timer, SHAPERCB(skb)->shapeclock);
281 }
282
283
284 /*
285  *      Bring the interface up. We just disallow this until a 
286  *      bind.
287  */
288
289 static int shaper_open(struct net_device *dev)
290 {
291         struct shaper *shaper=dev->priv;
292         
293         /*
294          *      Can't open until attached.
295          *      Also can't open until speed is set, or we'll get
296          *      a division by zero.
297          */
298          
299         if(shaper->dev==NULL)
300                 return -ENODEV;
301         if(shaper->bitspersec==0)
302                 return -EINVAL;
303         return 0;
304 }
305
306 /*
307  *      Closing a shaper flushes the queues.
308  */
309  
310 static int shaper_close(struct net_device *dev)
311 {
312         struct shaper *shaper=dev->priv;
313         struct sk_buff *skb;
314
315         while ((skb = skb_dequeue(&shaper->sendq)) != NULL)
316                 dev_kfree_skb(skb);
317
318         spin_lock_bh(&shaper->lock);
319         shaper_kick(shaper);
320         spin_unlock_bh(&shaper->lock);
321
322         del_timer_sync(&shaper->timer);
323         return 0;
324 }
325
326 /*
327  *      Revectored calls. We alter the parameters and call the functions
328  *      for our attached device. This enables us to bandwidth allocate after
329  *      ARP and other resolutions and not before.
330  */
331
332 static struct net_device_stats *shaper_get_stats(struct net_device *dev)
333 {
334         struct shaper *sh=dev->priv;
335         return &sh->stats;
336 }
337
338 static int shaper_header(struct sk_buff *skb, struct net_device *dev, 
339         unsigned short type, void *daddr, void *saddr, unsigned len)
340 {
341         struct shaper *sh=dev->priv;
342         int v;
343         if(sh_debug)
344                 printk("Shaper header\n");
345         skb->dev=sh->dev;
346         v=sh->hard_header(skb,sh->dev,type,daddr,saddr,len);
347         skb->dev=dev;
348         return v;
349 }
350
351 static int shaper_rebuild_header(struct sk_buff *skb)
352 {
353         struct shaper *sh=skb->dev->priv;
354         struct net_device *dev=skb->dev;
355         int v;
356         if(sh_debug)
357                 printk("Shaper rebuild header\n");
358         skb->dev=sh->dev;
359         v=sh->rebuild_header(skb);
360         skb->dev=dev;
361         return v;
362 }
363
364 #if 0
365 static int shaper_cache(struct neighbour *neigh, struct hh_cache *hh)
366 {
367         struct shaper *sh=neigh->dev->priv;
368         struct net_device *tmp;
369         int ret;
370         if(sh_debug)
371                 printk("Shaper header cache bind\n");
372         tmp=neigh->dev;
373         neigh->dev=sh->dev;
374         ret=sh->hard_header_cache(neigh,hh);
375         neigh->dev=tmp;
376         return ret;
377 }
378
379 static void shaper_cache_update(struct hh_cache *hh, struct net_device *dev,
380         unsigned char *haddr)
381 {
382         struct shaper *sh=dev->priv;
383         if(sh_debug)
384                 printk("Shaper cache update\n");
385         sh->header_cache_update(hh, sh->dev, haddr);
386 }
387 #endif
388
389 #ifdef CONFIG_INET
390
391 static int shaper_neigh_setup(struct neighbour *n)
392 {
393 #ifdef CONFIG_INET
394         if (n->nud_state == NUD_NONE) {
395                 n->ops = &arp_broken_ops;
396                 n->output = n->ops->output;
397         }
398 #endif  
399         return 0;
400 }
401
402 static int shaper_neigh_setup_dev(struct net_device *dev, struct neigh_parms *p)
403 {
404 #ifdef CONFIG_INET
405         if (p->tbl->family == AF_INET) {
406                 p->neigh_setup = shaper_neigh_setup;
407                 p->ucast_probes = 0;
408                 p->mcast_probes = 0;
409         }
410 #endif  
411         return 0;
412 }
413
414 #else /* !(CONFIG_INET) */
415
416 static int shaper_neigh_setup_dev(struct net_device *dev, struct neigh_parms *p)
417 {
418         return 0;
419 }
420
421 #endif
422
423 static int shaper_attach(struct net_device *shdev, struct shaper *sh, struct net_device *dev)
424 {
425         sh->dev = dev;
426         sh->hard_start_xmit=dev->hard_start_xmit;
427         sh->get_stats=dev->get_stats;
428         if(dev->hard_header)
429         {
430                 sh->hard_header=dev->hard_header;
431                 shdev->hard_header = shaper_header;
432         }
433         else
434                 shdev->hard_header = NULL;
435                 
436         if(dev->rebuild_header)
437         {
438                 sh->rebuild_header      = dev->rebuild_header;
439                 shdev->rebuild_header   = shaper_rebuild_header;
440         }
441         else
442                 shdev->rebuild_header   = NULL;
443         
444 #if 0
445         if(dev->hard_header_cache)
446         {
447                 sh->hard_header_cache   = dev->hard_header_cache;
448                 shdev->hard_header_cache= shaper_cache;
449         }
450         else
451         {
452                 shdev->hard_header_cache= NULL;
453         }
454                         
455         if(dev->header_cache_update)
456         {
457                 sh->header_cache_update = dev->header_cache_update;
458                 shdev->header_cache_update = shaper_cache_update;
459         }
460         else
461                 shdev->header_cache_update= NULL;
462 #else
463         shdev->header_cache_update = NULL;
464         shdev->hard_header_cache = NULL;
465 #endif
466         shdev->neigh_setup = shaper_neigh_setup_dev;
467         
468         shdev->hard_header_len=dev->hard_header_len;
469         shdev->type=dev->type;
470         shdev->addr_len=dev->addr_len;
471         shdev->mtu=dev->mtu;
472         sh->bitspersec=0;
473         return 0;
474 }
475
476 static int shaper_ioctl(struct net_device *dev,  struct ifreq *ifr, int cmd)
477 {
478         struct shaperconf *ss= (struct shaperconf *)&ifr->ifr_ifru;
479         struct shaper *sh=dev->priv;
480         
481         if(ss->ss_cmd == SHAPER_SET_DEV || ss->ss_cmd == SHAPER_SET_SPEED)
482         {
483                 if(!capable(CAP_NET_ADMIN))
484                         return -EPERM;
485         }
486         
487         switch(ss->ss_cmd)
488         {
489                 case SHAPER_SET_DEV:
490                 {
491                         struct net_device *them=__dev_get_by_name(ss->ss_name);
492                         if(them==NULL)
493                                 return -ENODEV;
494                         if(sh->dev)
495                                 return -EBUSY;
496                         return shaper_attach(dev,dev->priv, them);
497                 }
498                 case SHAPER_GET_DEV:
499                         if(sh->dev==NULL)
500                                 return -ENODEV;
501                         strcpy(ss->ss_name, sh->dev->name);
502                         return 0;
503                 case SHAPER_SET_SPEED:
504                         shaper_setspeed(sh,ss->ss_speed);
505                         return 0;
506                 case SHAPER_GET_SPEED:
507                         ss->ss_speed=sh->bitspersec;
508                         return 0;
509                 default:
510                         return -EINVAL;
511         }
512 }
513
514 static void shaper_init_priv(struct net_device *dev)
515 {
516         struct shaper *sh = dev->priv;
517
518         skb_queue_head_init(&sh->sendq);
519         init_timer(&sh->timer);
520         sh->timer.function=shaper_timer;
521         sh->timer.data=(unsigned long)sh;
522         spin_lock_init(&sh->lock);
523 }
524
525 /*
526  *      Add a shaper device to the system
527  */
528  
529 static void __init shaper_setup(struct net_device *dev)
530 {
531         /*
532          *      Set up the shaper.
533          */
534
535         SET_MODULE_OWNER(dev);
536
537         shaper_init_priv(dev);
538
539         dev->open               = shaper_open;
540         dev->stop               = shaper_close;
541         dev->hard_start_xmit    = shaper_start_xmit;
542         dev->get_stats          = shaper_get_stats;
543         dev->set_multicast_list = NULL;
544         
545         /*
546          *      Intialise the packet queues
547          */
548          
549         /*
550          *      Handlers for when we attach to a device.
551          */
552
553         dev->hard_header        = shaper_header;
554         dev->rebuild_header     = shaper_rebuild_header;
555 #if 0
556         dev->hard_header_cache  = shaper_cache;
557         dev->header_cache_update= shaper_cache_update;
558 #endif
559         dev->neigh_setup        = shaper_neigh_setup_dev;
560         dev->do_ioctl           = shaper_ioctl;
561         dev->hard_header_len    = 0;
562         dev->type               = ARPHRD_ETHER; /* initially */
563         dev->set_mac_address    = NULL;
564         dev->mtu                = 1500;
565         dev->addr_len           = 0;
566         dev->tx_queue_len       = 10;
567         dev->flags              = 0;
568 }
569  
570 static int shapers = 1;
571 #ifdef MODULE
572
573 module_param(shapers, int, 0);
574 MODULE_PARM_DESC(shapers, "Traffic shaper: maximum number of shapers");
575
576 #else /* MODULE */
577
578 static int __init set_num_shapers(char *str)
579 {
580         shapers = simple_strtol(str, NULL, 0);
581         return 1;
582 }
583
584 __setup("shapers=", set_num_shapers);
585
586 #endif /* MODULE */
587
588 static struct net_device **devs;
589
590 static unsigned int shapers_registered = 0;
591
592 static int __init shaper_init(void)
593 {
594         int i;
595         size_t alloc_size;
596         struct net_device *dev;
597         char name[IFNAMSIZ];
598
599         if (shapers < 1)
600                 return -ENODEV;
601
602         alloc_size = sizeof(*dev) * shapers;
603         devs = kmalloc(alloc_size, GFP_KERNEL);
604         if (!devs)
605                 return -ENOMEM;
606         memset(devs, 0, alloc_size);
607
608         for (i = 0; i < shapers; i++) {
609
610                 snprintf(name, IFNAMSIZ, "shaper%d", i);
611                 dev = alloc_netdev(sizeof(struct shaper), name,
612                                    shaper_setup);
613                 if (!dev) 
614                         break;
615
616                 if (register_netdev(dev)) {
617                         free_netdev(dev);
618                         break;
619                 }
620
621                 devs[i] = dev;
622                 shapers_registered++;
623         }
624
625         if (!shapers_registered) {
626                 kfree(devs);
627                 devs = NULL;
628         }
629
630         return (shapers_registered ? 0 : -ENODEV);
631 }
632
633 static void __exit shaper_exit (void)
634 {
635         int i;
636
637         for (i = 0; i < shapers_registered; i++) {
638                 if (devs[i]) {
639                         unregister_netdev(devs[i]);
640                         free_netdev(devs[i]);
641                 }
642         }
643
644         kfree(devs);
645         devs = NULL;
646 }
647
648 module_init(shaper_init);
649 module_exit(shaper_exit);
650 MODULE_LICENSE("GPL");
651