2 * Simple traffic shaper for Linux NET3.
4 * (c) Copyright 1996 Alan Cox <alan@redhat.com>, All Rights Reserved.
5 * http://www.redhat.com
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.
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.
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
25 * We work to the following constants
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
32 * SHAPER_MAXSLIP Maximum time a priority frame may jump forward.
33 * That bounds the penalty we will inflict on low
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.
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.
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
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
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>
68 * Use skb->cb for private data.
72 #include <linux/config.h>
73 #include <linux/module.h>
74 #include <linux/kernel.h>
75 #include <linux/sched.h>
76 #include <linux/ptrace.h>
77 #include <linux/fcntl.h>
79 #include <linux/malloc.h>
80 #include <linux/string.h>
81 #include <linux/errno.h>
82 #include <linux/netdevice.h>
83 #include <linux/etherdevice.h>
84 #include <linux/skbuff.h>
85 #include <linux/if_arp.h>
86 #include <linux/init.h>
89 #include <linux/if_shaper.h>
92 __u32 shapelatency
; /* Latency on frame */
93 __u32 shapeclock
; /* Time it should go out */
94 __u32 shapelen
; /* Frame length in clocks */
95 __u32 shapestamp
; /* Stamp for shaper */
96 __u16 shapepend
; /* Pending */
98 #define SHAPERCB(skb) ((struct shaper_cb *) ((skb)->cb))
100 int sh_debug
; /* Debug flag */
102 #define SHAPER_BANNER "CymruNet Traffic Shaper BETA 0.04 for Linux 2.1\n"
108 static int shaper_lock(struct shaper
*sh
)
111 * Lock in an interrupt must fail
113 while (test_and_set_bit(0, &sh
->locked
))
116 sleep_on(&sh
->wait_queue
);
124 static void shaper_kick(struct shaper
*sh
);
126 static void shaper_unlock(struct shaper
*sh
)
128 clear_bit(0, &sh
->locked
);
129 wake_up(&sh
->wait_queue
);
134 * Compute clocks on a buffer
137 static int shaper_clocks(struct shaper
*shaper
, struct sk_buff
*skb
)
139 int t
=skb
->len
/shaper
->bytespertick
;
144 * Set the speed of a shaper. We compute this in bytes per tick since
145 * thats how the machine wants to run. Quoted input is in bits per second
146 * as is traditional (note not BAUD). We assume 8 bit bytes.
149 static void shaper_setspeed(struct shaper
*shaper
, int bitspersec
)
151 shaper
->bitspersec
=bitspersec
;
152 shaper
->bytespertick
=(bitspersec
/HZ
)/8;
153 if(!shaper
->bytespertick
)
154 shaper
->bytespertick
++;
158 * Throw a frame at a shaper.
161 static int shaper_qframe(struct shaper
*shaper
, struct sk_buff
*skb
)
166 * Get ready to work on this shaper. Lock may fail if its
167 * an interrupt and locked.
170 if(!shaper_lock(shaper
))
172 ptr
=shaper
->sendq
.prev
;
175 * Set up our packet details
178 SHAPERCB(skb
)->shapelatency
=0;
179 SHAPERCB(skb
)->shapeclock
=shaper
->recovery
;
180 if(time_before(SHAPERCB(skb
)->shapeclock
, jiffies
))
181 SHAPERCB(skb
)->shapeclock
=jiffies
;
182 skb
->priority
=0; /* short term bug fix */
183 SHAPERCB(skb
)->shapestamp
=jiffies
;
186 * Time slots for this packet.
189 SHAPERCB(skb
)->shapelen
= shaper_clocks(shaper
,skb
);
191 #ifdef SHAPER_COMPLEX /* and broken.. */
193 while(ptr
&& ptr
!=(struct sk_buff
*)&shaper
->sendq
)
196 && jiffies
- SHAPERCB(ptr
)->shapeclock
< SHAPER_MAXSLIP
)
198 struct sk_buff
*tmp
=ptr
->prev
;
201 * It goes before us therefore we slip the length
205 SHAPERCB(ptr
)->shapeclock
+=SHAPERCB(skb
)->shapelen
;
206 SHAPERCB(ptr
)->shapelatency
+=SHAPERCB(skb
)->shapelen
;
209 * The packet may have slipped so far back it
212 if(SHAPERCB(ptr
)->shapelatency
> SHAPER_LATENCY
)
222 if(ptr
==NULL
|| ptr
==(struct sk_buff
*)&shaper
->sendq
)
223 skb_queue_head(&shaper
->sendq
,skb
);
228 * Set the packet clock out time according to the
229 * frames ahead. Im sure a bit of thought could drop
232 for(tmp
=skb_peek(&shaper
->sendq
); tmp
!=NULL
&& tmp
!=ptr
; tmp
=tmp
->next
)
233 SHAPERCB(skb
)->shapeclock
+=tmp
->shapelen
;
240 * Up our shape clock by the time pending on the queue
241 * (Should keep this in the shaper as a variable..)
243 for(tmp
=skb_peek(&shaper
->sendq
); tmp
!=NULL
&&
244 tmp
!=(struct sk_buff
*)&shaper
->sendq
; tmp
=tmp
->next
)
245 SHAPERCB(skb
)->shapeclock
+=SHAPERCB(tmp
)->shapelen
;
247 * Queue over time. Spill packet.
249 if(SHAPERCB(skb
)->shapeclock
-jiffies
> SHAPER_LATENCY
) {
251 shaper
->stats
.tx_dropped
++;
253 skb_queue_tail(&shaper
->sendq
, skb
);
257 printk("Frame queued.\n");
258 if(skb_queue_len(&shaper
->sendq
)>SHAPER_QLEN
)
260 ptr
=skb_dequeue(&shaper
->sendq
);
262 shaper
->stats
.collisions
++;
264 shaper_unlock(shaper
);
269 * Transmit from a shaper
272 static void shaper_queue_xmit(struct shaper
*shaper
, struct sk_buff
*skb
)
274 struct sk_buff
*newskb
=skb_clone(skb
, GFP_ATOMIC
);
276 printk("Kick frame on %p\n",newskb
);
279 newskb
->dev
=shaper
->dev
;
282 printk("Kick new frame to %s, %d\n",
283 shaper
->dev
->name
,newskb
->priority
);
284 dev_queue_xmit(newskb
);
286 shaper
->stats
.tx_bytes
+=newskb
->len
;
287 shaper
->stats
.tx_packets
++;
290 printk("Kicked new frame out.\n");
296 * Timer handler for shaping clock
299 static void shaper_timer(unsigned long data
)
301 struct shaper
*sh
=(struct shaper
*)data
;
306 * Kick a shaper queue and try and do something sensible with the
310 static void shaper_kick(struct shaper
*shaper
)
315 * Shaper unlock will kick
318 if (test_and_set_bit(0, &shaper
->locked
))
321 printk("Shaper locked.\n");
322 mod_timer(&shaper
->timer
, jiffies
);
328 * Walk the list (may be empty)
331 while((skb
=skb_peek(&shaper
->sendq
))!=NULL
)
334 * Each packet due to go out by now (within an error
335 * of SHAPER_BURST) gets kicked onto the link
339 printk("Clock = %d, jiffies = %ld\n", SHAPERCB(skb
)->shapeclock
, jiffies
);
340 if(time_before_eq(SHAPERCB(skb
)->shapeclock
- jiffies
, SHAPER_BURST
))
343 * Pull the frame and get interrupts back on.
347 if (shaper
->recovery
<
348 SHAPERCB(skb
)->shapeclock
+ SHAPERCB(skb
)->shapelen
)
349 shaper
->recovery
= SHAPERCB(skb
)->shapeclock
+ SHAPERCB(skb
)->shapelen
;
351 * Pass on to the physical target device via
352 * our low level packet thrower.
355 SHAPERCB(skb
)->shapepend
=0;
356 shaper_queue_xmit(shaper
, skb
); /* Fire */
367 mod_timer(&shaper
->timer
, SHAPERCB(skb
)->shapeclock
);
369 clear_bit(0, &shaper
->locked
);
374 * Flush the shaper queues on a closedown
377 static void shaper_flush(struct shaper
*shaper
)
380 if(!shaper_lock(shaper
))
382 printk(KERN_ERR
"shaper: shaper_flush() called by an irq!\n");
385 while((skb
=skb_dequeue(&shaper
->sendq
))!=NULL
)
387 shaper_unlock(shaper
);
391 * Bring the interface up. We just disallow this until a
395 static int shaper_open(struct net_device
*dev
)
397 struct shaper
*shaper
=dev
->priv
;
400 * Can't open until attached.
401 * Also can't open until speed is set, or we'll get
402 * a division by zero.
405 if(shaper
->dev
==NULL
)
407 if(shaper
->bitspersec
==0)
413 * Closing a shaper flushes the queues.
416 static int shaper_close(struct net_device
*dev
)
418 struct shaper
*shaper
=dev
->priv
;
419 shaper_flush(shaper
);
420 del_timer_sync(&shaper
->timer
);
425 * Revectored calls. We alter the parameters and call the functions
426 * for our attached device. This enables us to bandwidth allocate after
427 * ARP and other resolutions and not before.
431 static int shaper_start_xmit(struct sk_buff
*skb
, struct net_device
*dev
)
433 struct shaper
*sh
=dev
->priv
;
434 return shaper_qframe(sh
, skb
);
437 static struct net_device_stats
*shaper_get_stats(struct net_device
*dev
)
439 struct shaper
*sh
=dev
->priv
;
443 static int shaper_header(struct sk_buff
*skb
, struct net_device
*dev
,
444 unsigned short type
, void *daddr
, void *saddr
, unsigned len
)
446 struct shaper
*sh
=dev
->priv
;
449 printk("Shaper header\n");
451 v
=sh
->hard_header(skb
,sh
->dev
,type
,daddr
,saddr
,len
);
456 static int shaper_rebuild_header(struct sk_buff
*skb
)
458 struct shaper
*sh
=skb
->dev
->priv
;
459 struct net_device
*dev
=skb
->dev
;
462 printk("Shaper rebuild header\n");
464 v
=sh
->rebuild_header(skb
);
470 static int shaper_cache(struct neighbour
*neigh
, struct hh_cache
*hh
)
472 struct shaper
*sh
=neigh
->dev
->priv
;
473 struct net_device
*tmp
;
476 printk("Shaper header cache bind\n");
479 ret
=sh
->hard_header_cache(neigh
,hh
);
484 static void shaper_cache_update(struct hh_cache
*hh
, struct net_device
*dev
,
485 unsigned char *haddr
)
487 struct shaper
*sh
=dev
->priv
;
489 printk("Shaper cache update\n");
490 sh
->header_cache_update(hh
, sh
->dev
, haddr
);
496 static int shaper_neigh_setup(struct neighbour
*n
)
499 if (n
->nud_state
== NUD_NONE
) {
500 n
->ops
= &arp_broken_ops
;
501 n
->output
= n
->ops
->output
;
507 static int shaper_neigh_setup_dev(struct net_device
*dev
, struct neigh_parms
*p
)
510 if (p
->tbl
->family
== AF_INET
) {
511 p
->neigh_setup
= shaper_neigh_setup
;
519 #else /* !(CONFIG_INET) */
521 static int shaper_neigh_setup_dev(struct net_device
*dev
, struct neigh_parms
*p
)
528 static int shaper_attach(struct net_device
*shdev
, struct shaper
*sh
, struct net_device
*dev
)
531 sh
->hard_start_xmit
=dev
->hard_start_xmit
;
532 sh
->get_stats
=dev
->get_stats
;
535 sh
->hard_header
=dev
->hard_header
;
536 shdev
->hard_header
= shaper_header
;
539 shdev
->hard_header
= NULL
;
541 if(dev
->rebuild_header
)
543 sh
->rebuild_header
= dev
->rebuild_header
;
544 shdev
->rebuild_header
= shaper_rebuild_header
;
547 shdev
->rebuild_header
= NULL
;
550 if(dev
->hard_header_cache
)
552 sh
->hard_header_cache
= dev
->hard_header_cache
;
553 shdev
->hard_header_cache
= shaper_cache
;
557 shdev
->hard_header_cache
= NULL
;
560 if(dev
->header_cache_update
)
562 sh
->header_cache_update
= dev
->header_cache_update
;
563 shdev
->header_cache_update
= shaper_cache_update
;
566 shdev
->header_cache_update
= NULL
;
568 shdev
->header_cache_update
= NULL
;
569 shdev
->hard_header_cache
= NULL
;
571 shdev
->neigh_setup
= shaper_neigh_setup_dev
;
573 shdev
->hard_header_len
=dev
->hard_header_len
;
574 shdev
->type
=dev
->type
;
575 shdev
->addr_len
=dev
->addr_len
;
581 static int shaper_ioctl(struct net_device
*dev
, struct ifreq
*ifr
, int cmd
)
583 struct shaperconf
*ss
= (struct shaperconf
*)&ifr
->ifr_data
;
584 struct shaper
*sh
=dev
->priv
;
586 if(ss
->ss_cmd
== SHAPER_SET_DEV
|| ss
->ss_cmd
== SHAPER_SET_SPEED
)
588 if(!capable(CAP_NET_ADMIN
))
596 struct net_device
*them
=__dev_get_by_name(ss
->ss_name
);
601 return shaper_attach(dev
,dev
->priv
, them
);
606 strcpy(ss
->ss_name
, sh
->dev
->name
);
608 case SHAPER_SET_SPEED
:
609 shaper_setspeed(sh
,ss
->ss_speed
);
611 case SHAPER_GET_SPEED
:
612 ss
->ss_speed
=sh
->bitspersec
;
619 static void shaper_init_priv(struct net_device
*dev
)
621 struct shaper
*sh
= dev
->priv
;
623 skb_queue_head_init(&sh
->sendq
);
624 init_timer(&sh
->timer
);
625 sh
->timer
.function
=shaper_timer
;
626 sh
->timer
.data
=(unsigned long)sh
;
627 init_waitqueue_head(&sh
->wait_queue
);
631 * Add a shaper device to the system
634 static int __init
shaper_probe(struct net_device
*dev
)
640 SET_MODULE_OWNER(dev
);
642 shaper_init_priv(dev
);
644 dev
->open
= shaper_open
;
645 dev
->stop
= shaper_close
;
646 dev
->hard_start_xmit
= shaper_start_xmit
;
647 dev
->get_stats
= shaper_get_stats
;
648 dev
->set_multicast_list
= NULL
;
651 * Intialise the packet queues
654 dev_init_buffers(dev
);
657 * Handlers for when we attach to a device.
660 dev
->hard_header
= shaper_header
;
661 dev
->rebuild_header
= shaper_rebuild_header
;
663 dev
->hard_header_cache
= shaper_cache
;
664 dev
->header_cache_update
= shaper_cache_update
;
666 dev
->neigh_setup
= shaper_neigh_setup_dev
;
667 dev
->do_ioctl
= shaper_ioctl
;
668 dev
->hard_header_len
= 0;
669 dev
->type
= ARPHRD_ETHER
; /* initially */
670 dev
->set_mac_address
= NULL
;
673 dev
->tx_queue_len
= 10;
683 static int shapers
= 1;
686 MODULE_PARM(shapers
, "i");
690 static int __init
set_num_shapers(char *str
)
692 shapers
= simple_strtol(str
, NULL
, 0);
696 __setup("shapers=", set_num_shapers
);
700 static struct net_device
*devs
;
702 static int __init
shaper_init(void)
707 unsigned int shapers_registered
= 0;
712 alloc_size
= (sizeof(*devs
) * shapers
) +
713 (sizeof(struct shaper
) * shapers
);
714 devs
= kmalloc(alloc_size
, GFP_KERNEL
);
717 memset(devs
, 0, alloc_size
);
718 sp
= (struct shaper
*) &devs
[shapers
];
720 for (i
= 0; i
< shapers
; i
++) {
721 err
= dev_alloc_name(&devs
[i
], "shaper%d");
724 devs
[i
].init
= shaper_probe
;
725 devs
[i
].priv
= &sp
[i
];
726 if (register_netdev(&devs
[i
]))
728 shapers_registered
++;
731 if (!shapers_registered
) {
736 return (shapers_registered
? 0 : -ENODEV
);
739 static void __exit
shaper_exit (void)
745 module_init(shaper_init
);
746 module_exit(shaper_exit
);