bsd/netinet/ip_dummynet.h

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 /*
  23  * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
  24  * Portions Copyright (c) 2000 Akamba Corp.
  25  * All rights reserved
  26  *
  27  * Redistribution and use in source and binary forms, with or without
  28  * modification, are permitted provided that the following conditions
  29  * are met:
  30  * 1. Redistributions of source code must retain the above copyright
  31  *    notice, this list of conditions and the following disclaimer.
  32  * 2. Redistributions in binary form must reproduce the above copyright
  33  *    notice, this list of conditions and the following disclaimer in the
  34  *    documentation and/or other materials provided with the distribution.
  35  *
  36  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  37  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  38  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  39  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  40  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  41  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  42  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  43  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  44  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  45  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  46  * SUCH DAMAGE.
  47  *
  48  * $FreeBSD: src/sys/netinet/ip_dummynet.h,v 1.32 2004/08/17 22:05:54 andre Exp $
  49  */
  50
  51 #ifndef _IP_DUMMYNET_H
  52 #define _IP_DUMMYNET_H
  53 #include <sys/appleapiopts.h>
  54
  55 #ifdef PRIVATE
  56 /*
  57  * Definition of dummynet data structures. In the structures, I decided
  58  * not to use the macros in <sys/queue.h> in the hope of making the code
  59  * easier to port to other architectures. The type of lists and queue we
  60  * use here is pretty simple anyways.
  61  */
  62
  63 /*
  64  * We start with a heap, which is used in the scheduler to decide when
  65  * to transmit packets etc.
  66  *
  67  * The key for the heap is used for two different values:
  68  *
  69  * 1. timer ticks- max 10K/second, so 32 bits are enough;
  70  *
  71  * 2. virtual times. These increase in steps of len/x, where len is the
  72  *    packet length, and x is either the weight of the flow, or the
  73  *    sum of all weights.
  74  *    If we limit to max 1000 flows and a max weight of 100, then
  75  *    x needs 17 bits. The packet size is 16 bits, so we can easily
  76  *    overflow if we do not allow errors.
  77  * So we use a key "dn_key" which is 64 bits. Some macros are used to
  78  * compare key values and handle wraparounds.
  79  * MAX64 returns the largest of two key values.
  80  * MY_M is used as a shift count when doing fixed point arithmetic
  81  * (a better name would be useful...).
  82  */
  83 typedef u_int64_t dn_key ;      /* sorting key */
  84 #define DN_KEY_LT(a,b)     ((int64_t)((a)-(b)) < 0)
  85 #define DN_KEY_LEQ(a,b)    ((int64_t)((a)-(b)) <= 0)
  86 #define DN_KEY_GT(a,b)     ((int64_t)((a)-(b)) > 0)
  87 #define DN_KEY_GEQ(a,b)    ((int64_t)((a)-(b)) >= 0)
  88 #define MAX64(x,y)  (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
  89 #define MY_M    16 /* number of left shift to obtain a larger precision */
  90
  91 /*
  92  * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
  93  * virtual time wraps every 15 days.
  94  */
  95
  96 /*
  97  * The OFFSET_OF macro is used to return the offset of a field within
  98  * a structure. It is used by the heap management routines.
  99  */
 100 #define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) )
 101
 102 /*
 103  * The maximum hash table size for queues.  This value must be a power
 104  * of 2.
 105  */
 106 #define DN_MAX_HASH_SIZE 65536
 107
 108 /*
 109  * A heap entry is made of a key and a pointer to the actual
 110  * object stored in the heap.
 111  * The heap is an array of dn_heap_entry entries, dynamically allocated.
 112  * Current size is "size", with "elements" actually in use.
 113  * The heap normally supports only ordered insert and extract from the top.
 114  * If we want to extract an object from the middle of the heap, we
 115  * have to know where the object itself is located in the heap (or we
 116  * need to scan the whole array). To this purpose, an object has a
 117  * field (int) which contains the index of the object itself into the
 118  * heap. When the object is moved, the field must also be updated.
 119  * The offset of the index in the object is stored in the 'offset'
 120  * field in the heap descriptor. The assumption is that this offset
 121  * is non-zero if we want to support extract from the middle.
 122  */
 123 struct dn_heap_entry {
 124     dn_key key ;        /* sorting key. Topmost element is smallest one */
 125     void *object ;      /* object pointer */
 126 } ;
 127
 128 struct dn_heap {
 129     int size ;
 130     int elements ;
 131     int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */
 132     struct dn_heap_entry *p ;   /* really an array of "size" entries */
 133 } ;
 134
 135 /*
 136  * Packets processed by dummynet have an mbuf tag associated with
 137  * them that carries their dummynet state.  This is used within
 138  * the dummynet code as well as outside when checking for special
 139  * processing requirements.
 140  */
 141 #ifdef KERNEL
 142 struct dn_pkt_tag {
 143     struct ip_fw *rule;         /* matching rule */
 144     int dn_dir;                 /* action when packet comes out. */
 145 #define DN_TO_IP_OUT    1
 146 #define DN_TO_IP_IN     2
 147 #define DN_TO_BDG_FWD   3
 148
 149     dn_key output_time;         /* when the pkt is due for delivery     */
 150     struct ifnet *ifp;          /* interface, for ip_output             */
 151     struct sockaddr_in *dn_dst ;
 152     struct route ro;            /* route, for ip_output. MUST COPY      */
 153     int flags ;                 /* flags, for ip_output (IPv6 ?)        */
 154 };
 155 #else
 156 struct dn_pkt;
 157 #endif /* KERNEL */
 158
 159 /*
 160  * Overall structure of dummynet (with WF2Q+):
 161
 162 In dummynet, packets are selected with the firewall rules, and passed
 163 to two different objects: PIPE or QUEUE.
 164
 165 A QUEUE is just a queue with configurable size and queue management
 166 policy. It is also associated with a mask (to discriminate among
 167 different flows), a weight (used to give different shares of the
 168 bandwidth to different flows) and a "pipe", which essentially
 169 supplies the transmit clock for all queues associated with that
 170 pipe.
 171
 172 A PIPE emulates a fixed-bandwidth link, whose bandwidth is
 173 configurable.  The "clock" for a pipe can come from either an
 174 internal timer, or from the transmit interrupt of an interface.
 175 A pipe is also associated with one (or more, if masks are used)
 176 queue, where all packets for that pipe are stored.
 177
 178 The bandwidth available on the pipe is shared by the queues
 179 associated with that pipe (only one in case the packet is sent
 180 to a PIPE) according to the WF2Q+ scheduling algorithm and the
 181 configured weights.
 182
 183 In general, incoming packets are stored in the appropriate queue,
 184 which is then placed into one of a few heaps managed by a scheduler
 185 to decide when the packet should be extracted.
 186 The scheduler (a function called dummynet()) is run at every timer
 187 tick, and grabs queues from the head of the heaps when they are
 188 ready for processing.
 189
 190 There are three data structures definining a pipe and associated queues:
 191
 192  + dn_pipe, which contains the main configuration parameters related
 193    to delay and bandwidth;
 194  + dn_flow_set, which contains WF2Q+ configuration, flow
 195    masks, plr and RED configuration;
 196  + dn_flow_queue, which is the per-flow queue (containing the packets)
 197
 198 Multiple dn_flow_set can be linked to the same pipe, and multiple
 199 dn_flow_queue can be linked to the same dn_flow_set.
 200 All data structures are linked in a linear list which is used for
 201 housekeeping purposes.
 202
 203 During configuration, we create and initialize the dn_flow_set
 204 and dn_pipe structures (a dn_pipe also contains a dn_flow_set).
 205
 206 At runtime: packets are sent to the appropriate dn_flow_set (either
 207 WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows),
 208 which in turn dispatches them to the appropriate dn_flow_queue
 209 (created dynamically according to the masks).
 210
 211 The transmit clock for fixed rate flows (ready_event()) selects the
 212 dn_flow_queue to be used to transmit the next packet. For WF2Q,
 213 wfq_ready_event() extract a pipe which in turn selects the right
 214 flow using a number of heaps defined into the pipe itself.
 215
 216  *
 217  */
 218
 219 /*
 220  * per flow queue. This contains the flow identifier, the queue
 221  * of packets, counters, and parameters used to support both RED and
 222  * WF2Q+.
 223  *
 224  * A dn_flow_queue is created and initialized whenever a packet for
 225  * a new flow arrives.
 226  */
 227 struct dn_flow_queue {
 228     struct dn_flow_queue *next ;
 229     struct ipfw_flow_id id ;
 230
 231     struct mbuf *head, *tail ;  /* queue of packets */
 232     u_int len ;
 233     u_int len_bytes ;
 234     u_long numbytes ;           /* credit for transmission (dynamic queues) */
 235
 236     u_int64_t tot_pkts ;        /* statistics counters  */
 237     u_int64_t tot_bytes ;
 238     u_int32_t drops ;
 239
 240     int hash_slot ;             /* debugging/diagnostic */
 241
 242     /* RED parameters */
 243     int avg ;                   /* average queue length est. (scaled) */
 244     int count ;                 /* arrivals since last RED drop */
 245     int random ;                /* random value (scaled) */
 246     u_int32_t q_time ;          /* start of queue idle time */
 247
 248     /* WF2Q+ support */
 249     struct dn_flow_set *fs ;    /* parent flow set */
 250     int heap_pos ;              /* position (index) of struct in heap */
 251     dn_key sched_time ;         /* current time when queue enters ready_heap */
 252
 253     dn_key S,F ;                /* start time, finish time */
 254     /*
 255      * Setting F < S means the timestamp is invalid. We only need
 256      * to test this when the queue is empty.
 257      */
 258 } ;
 259
 260 /*
 261  * flow_set descriptor. Contains the "template" parameters for the
 262  * queue configuration, and pointers to the hash table of dn_flow_queue's.
 263  *
 264  * The hash table is an array of lists -- we identify the slot by
 265  * hashing the flow-id, then scan the list looking for a match.
 266  * The size of the hash table (buckets) is configurable on a per-queue
 267  * basis.
 268  *
 269  * A dn_flow_set is created whenever a new queue or pipe is created (in the
 270  * latter case, the structure is located inside the struct dn_pipe).
 271  */
 272 struct dn_flow_set {
 273     struct dn_flow_set *next; /* next flow set in all_flow_sets list */
 274
 275     u_short fs_nr ;             /* flow_set number       */
 276     u_short flags_fs;
 277 #define DN_HAVE_FLOW_MASK       0x0001
 278 #define DN_IS_RED               0x0002
 279 #define DN_IS_GENTLE_RED        0x0004
 280 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 281 #define DN_NOERROR              0x0010  /* do not report ENOBUFS on drops  */
 282 #define DN_IS_PIPE              0x4000
 283 #define DN_IS_QUEUE             0x8000
 284
 285     struct dn_pipe *pipe ;      /* pointer to parent pipe */
 286     u_short parent_nr ;         /* parent pipe#, 0 if local to a pipe */
 287
 288     int weight ;                /* WFQ queue weight */
 289     int qsize ;                 /* queue size in slots or bytes */
 290     int plr ;                   /* pkt loss rate (2^31-1 means 100%) */
 291
 292     struct ipfw_flow_id flow_mask ;
 293
 294     /* hash table of queues onto this flow_set */
 295     int rq_size ;               /* number of slots */
 296     int rq_elements ;           /* active elements */
 297     struct dn_flow_queue **rq;  /* array of rq_size entries */
 298
 299     u_int32_t last_expired ;    /* do not expire too frequently */
 300     int backlogged ;            /* #active queues for this flowset */
 301
 302         /* RED parameters */
 303 #define SCALE_RED               16
 304 #define SCALE(x)                ( (x) << SCALE_RED )
 305 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 306 #define SCALE_MUL(x,y)          ( ( (x) * (y) ) >> SCALE_RED )
 307     int w_q ;                   /* queue weight (scaled) */
 308     int max_th ;                /* maximum threshold for queue (scaled) */
 309     int min_th ;                /* minimum threshold for queue (scaled) */
 310     int max_p ;                 /* maximum value for p_b (scaled) */
 311     u_int c_1 ;                 /* max_p/(max_th-min_th) (scaled) */
 312     u_int c_2 ;                 /* max_p*min_th/(max_th-min_th) (scaled) */
 313     u_int c_3 ;                 /* for GRED, (1-max_p)/max_th (scaled) */
 314     u_int c_4 ;                 /* for GRED, 1 - 2*max_p (scaled) */
 315     u_int * w_q_lookup ;        /* lookup table for computing (1-w_q)^t */
 316     u_int lookup_depth ;        /* depth of lookup table */
 317     int lookup_step ;           /* granularity inside the lookup table */
 318     int lookup_weight ;         /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 319     int avg_pkt_size ;          /* medium packet size */
 320     int max_pkt_size ;          /* max packet size */
 321 } ;
 322
 323 /*
 324  * Pipe descriptor. Contains global parameters, delay-line queue,
 325  * and the flow_set used for fixed-rate queues.
 326  *
 327  * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
 328  *   not_eligible_heap, for queues whose start time is higher
 329  *      than the virtual time. Sorted by start time.
 330  *   scheduler_heap, for queues eligible for scheduling. Sorted by
 331  *      finish time.
 332  *   idle_heap, all flows that are idle and can be removed. We
 333  *      do that on each tick so we do not slow down too much
 334  *      operations during forwarding.
 335  *
 336  */
 337 struct dn_pipe {                /* a pipe */
 338     struct dn_pipe *next ;
 339
 340     int pipe_nr ;               /* number       */
 341     int bandwidth;              /* really, bytes/tick.  */
 342     int delay ;                 /* really, ticks        */
 343
 344     struct      mbuf *head, *tail ;     /* packets in delay line */
 345
 346     /* WF2Q+ */
 347     struct dn_heap scheduler_heap ; /* top extract - key Finish time*/
 348     struct dn_heap not_eligible_heap; /* top extract- key Start time */
 349     struct dn_heap idle_heap ; /* random extract - key Start=Finish time */
 350
 351     dn_key V ;                  /* virtual time */
 352     int sum;                    /* sum of weights of all active sessions */
 353     int numbytes;               /* bits I can transmit (more or less). */
 354
 355     dn_key sched_time ;         /* time pipe was scheduled in ready_heap */
 356
 357     /*
 358      * When the tx clock come from an interface (if_name[0] != '\0'), its name
 359      * is stored below, whereas the ifp is filled when the rule is configured.
 360      */
 361     char if_name[IFNAMSIZ];
 362     struct ifnet *ifp ;
 363     int ready ; /* set if ifp != NULL and we got a signal from it */
 364
 365     struct dn_flow_set fs ; /* used with fixed-rate flows */
 366 };
 367
 368 #ifdef KERNEL
 369
 370 void ip_dn_init(void); /* called from raw_ip.c:load_ipfw() */
 371
 372 typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */
 373 typedef void ip_dn_ruledel_t(void *); /* ip_fw.c */
 374 typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir,
 375         struct ip_fw_args *fwa);
 376 extern  ip_dn_ctl_t *ip_dn_ctl_ptr;
 377 extern  ip_dn_ruledel_t *ip_dn_ruledel_ptr;
 378 extern  ip_dn_io_t *ip_dn_io_ptr;
 379 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
 380
 381 /*
 382  * Return the IPFW rule associated with the dummynet tag; if any.
 383  * Make sure that the dummynet tag is not reused by lower layers.
 384  */
 385 static __inline struct ip_fw *
 386 ip_dn_claim_rule(struct mbuf *m)
 387 {
 388         struct m_tag *mtag = m_tag_locate(m, KERNEL_MODULE_TAG_ID,
 389                                                                           KERNEL_TAG_TYPE_DUMMYNET, NULL);
 390         if (mtag != NULL) {
 391                 mtag->m_tag_type = KERNEL_TAG_TYPE_NONE;
 392                 return (((struct dn_pkt_tag *)(mtag+1))->rule);
 393         } else
 394                 return (NULL);
 395 }
 396 #endif /* KERNEL */
 397
 398 #endif /* PRIVATE */
 399 #endif /* _IP_DUMMYNET_H */