Implement per-flow queueing. Using a single pipe config rule,

now you can dynamically create rate-limited queues for different
flows using masks on dst/src IP, port and protocols.
Read the ipfw(8) manpage for details and examples.

Restructure the internals of the traffic shaper to use heaps,
so that it manages efficiently large number of queues.

Fix a bug which was present in the previous versions which could
cause, under certain unfrequent conditions, to send out very large
bursts of traffic.

All in all, this new code is much cleaner than the previous one and
should also perform better.

Work supported by Akamba Corp.

1 files changed, 95 insertions, 46 deletions

diff --git a/sys/netinet/ip_dummynet.h b/sys/netinet/ip_dummynet.h
index 61ca6dd..dbfa8a2 100644
--- a/sys/netinet/ip_dummynet.h
+++ b/sys/netinet/ip_dummynet.h
@@ -1,14 +1,28 @@
 /*
- * Copyright (c) 1998 Luigi Rizzo
+ * Copyright (c) 1998-2000 Luigi Rizzo, Universita` di Pisa
+ * Portions Copyright (c) 2000 Akamba Corp.
+ * All rights reserved
  *
- * Redistribution and use in source forms, with and without modification,
- * are permitted provided that this entire comment appears intact.
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
  *
- * Redistribution in binary form may occur without any restrictions.
- * Obviously, it would be nice if you gave credit where credit is due
- * but requiring it would be too onerous.
- *
- * This software is provided ``AS IS'' without any warranties of any kind.
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
  *
  * $FreeBSD$
  */
@@ -18,8 +32,7 @@
 
 /*
  * Definition of dummynet data structures.
- * Dummynet handles a list of pipes, each one identified by a unique
- * number (hopefully the list is short so we use a linked list).
+ * We first start with the heap which is used by the scheduler.
  *
  * Each list contains a set of parameters identifying the pipe, and
  * a set of packets queued on the pipe itself.
@@ -28,6 +41,31 @@
  * is pretty simple and this makes the code more portable.
  */
 
+typedef u_int32_t dn_key ;      /* sorting key */
+#define DN_KEY_LT(a,b)     ((int)((a)-(b)) < 0)
+#define DN_KEY_LEQ(a,b)    ((int)((a)-(b)) <= 0)
+#define DN_KEY_GT(a,b)     ((int)((a)-(b)) > 0)
+#define DN_KEY_GEQ(a,b)    ((int)((a)-(b)) >= 0)
+
+struct dn_heap_entry {
+    dn_key key ;	/* sorting key. Topmost element is smallest one */
+    void *object ;	/* object pointer */
+} ;
+
+struct dn_heap {
+    int size ;
+    int elements ;
+    struct dn_heap_entry *p ;	/* really an array of "size" entries */
+} ;
+
+/*
+ * MT_DUMMYNET is a new (fake) mbuf type that is prepended to the
+ * packet when it comes out of a pipe. The definition
+ * ought to go in /sys/sys/mbuf.h but here it is less intrusive.
+ */
+
+#define MT_DUMMYNET MT_CONTROL
+
 /*
  * struct dn_pkt identifies a packet in the dummynet queue. The
  * first part is really an m_hdr for implementation purposes, and some
@@ -38,19 +76,19 @@
 struct dn_pkt {
 	struct m_hdr hdr ;
 #define dn_next	hdr.mh_nextpkt	/* next element in queue */
+#define DN_NEXT(x)	(struct dn_pkt *)(x)->dn_next
 #define dn_m	hdr.mh_next	/* packet to be forwarded */
-#define dn_dst	hdr.mh_len	/* dst, for ip_output			*/
-#define dn_dir	hdr.mh_flags	/* IP_FW_F_IN or IP_FW_F_OUT		*/
-        int     delay;		/* stays queued until delay=0		*/
+/* #define dn_dst	hdr.mh_len -* dst, for ip_output		*/
+#define dn_dir	hdr.mh_flags	/* action when pkt extracted from a queue */
+#define DN_TO_IP_OUT	1
+#define DN_TO_IP_IN	2
+#define DN_TO_BDG_FWD	3
+
+	dn_key  output_time;    /* when the pkt is due for delivery */
         struct ifnet *ifp;	/* interface, for ip_output		*/
+	struct sockaddr_in *dn_dst ;
         struct route ro;	/* route, for ip_output. MUST COPY	*/
-	int	flags;		/* flags, for ip_output			*/
-
-#ifdef   DUMMYNET_DEBUG
-        struct timeval beg, mid;        /* testing only */
-        int     act_delay;      /* testing only */
-        int     in_delay;       /* testing only */
-#endif
+	int flags ;		/* flags, for ip_output (IPv6 ?) */
 };
 
 struct dn_queue {
@@ -58,53 +96,64 @@ struct dn_queue {
 } ;
 
 /*
- * descriptor of a pipe. The flags field will be used to speed up the
- * forwarding code paths, in case some of the parameters are not
- * used.
+ * Flow mask/flow id for each queue.
+ */
+struct dn_flow_id {
+    u_int32_t dst_ip, src_ip ;
+    u_int16_t dst_port, src_port ;
+    u_int8_t proto ;
+} ;
+
+/*
+ * We use per flow queues. Hashing is used to select the right slot,
+ * then we scan the list to match the flow-id.
+ * The pipe is shared as it is only a delay line and thus one is enough.
+ */
+struct dn_flow_queue {
+    struct dn_flow_queue *next ;
+    struct dn_flow_id id ;
+    struct dn_pipe *p ;	/* parent pipe */
+    struct dn_queue r;
+    long numbytes ;
+    u_int len ;
+    u_int len_bytes ;
+
+    u_int64_t tot_pkts ;	/* statistics counters	*/
+    u_int64_t tot_bytes ;
+    u_int32_t drops ;
+    int hash_slot ;	/* debugging/diagnostic */
+} ;
+
+/*
+ * Pipe descriptor. Contains global parameters, delay-line queue,
+ * and the hash array of the per-flow queues.
  */
 struct dn_pipe {			/* a pipe */
 	struct dn_pipe *next ;
 
 	u_short	pipe_nr ;		/* number	*/
 	u_short	flags ;			/* to speed up things	*/
-#define DN_HAVE_BW	1
-#define DN_HAVE_QUEUE	2
-#define DN_HAVE_DELAY	4
+#define DN_HAVE_FLOW_MASK	8
 	int	bandwidth;		/* really, bytes/tick.	*/
 	int	queue_size ;
 	int	queue_size_bytes ;
 	int	delay ;			/* really, ticks	*/
 	int	plr ;		/* pkt loss rate (2^31-1 means 100%) */
 
-        struct	dn_queue r;
-        int	r_len;			/* elements in r_queue */
-        int	r_len_bytes;		/* bytes in r_queue */
-        int	r_drops;		/* drops from r_queue */
         struct	dn_queue p ;
-        int     ticks_from_last_insert;
-        long    numbytes;		/* which can send or receive */
+	struct dn_flow_id flow_mask ;
+	int rq_size ;
+	int rq_elements ;
+	struct dn_flow_queue **rq ;	/* array of rq_size entries */
 };
 
-/*
- * The following is used to define a new mbuf type that is
- * prepended to the packet when it comes out of a pipe. The definition
- * ought to go in /sys/sys/mbuf.h but here it is less intrusive.
- */
-
-#define MT_DUMMYNET MT_CONTROL
-/*
- * what to do of a packet when it comes out of a pipe
- */
-#define DN_TO_IP_OUT	1
-#define DN_TO_IP_IN	2
-#define DN_TO_BDG_FWD	3
-
 #ifdef _KERNEL
 
 MALLOC_DECLARE(M_IPFW);
 
 typedef int ip_dn_ctl_t __P((struct sockopt *)) ;
 extern ip_dn_ctl_t *ip_dn_ctl_ptr;
+extern struct dn_flow_id dn_last_pkt ;
 
 void dn_rule_delete(void *r);		/* used in ip_fw.c */
 int dummynet_io(int pipe, int dir,