bsd/netinet/ip_dummynet.h

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /*
  26  * Copyright (c) 1998 Luigi Rizzo
  27  *
  28  * Redistribution and use in source forms, with and without modification,
  29  * are permitted provided that this entire comment appears intact.
  30  *
  31  * Redistribution in binary form may occur without any restrictions.
  32  * Obviously, it would be nice if you gave credit where credit is due
  33  * but requiring it would be too onerous.
  34  *
  35  * This software is provided ``AS IS'' without any warranties of any kind.
  36  *
  37  * $FreeBSD: src/sys/netinet/ip_dummynet.h,v 1.10.2.3 2001/02/01 20:25:09 luigi Exp $
  38  */
  39
  40 #ifndef _IP_DUMMYNET_H
  41 #define _IP_DUMMYNET_H
  42 #include <sys/appleapiopts.h>
  43 #ifdef __APPLE_API_PRIVATE
  44
  45 /*
  46  * Definition of dummynet data structures. In the structures, I decided
  47  * not to use the macros in <sys/queue.h> in the hope of making the code
  48  * easier to port to other architectures. The type of lists and queue we
  49  * use here is pretty simple anyways.
  50  */
  51
  52 /*
  53  * We start with a heap, which is used in the scheduler to decide when
  54  * to transmit packets etc.
  55  *
  56  * The key for the heap is used for two different values:
  57  *
  58  * 1. timer ticks- max 10K/second, so 32 bits are enough;
  59  *
  60  * 2. virtual times. These increase in steps of len/x, where len is the
  61  *    packet length, and x is either the weight of the flow, or the
  62  *    sum of all weights.
  63  *    If we limit to max 1000 flows and a max weight of 100, then
  64  *    x needs 17 bits. The packet size is 16 bits, so we can easily
  65  *    overflow if we do not allow errors.
  66  * So we use a key "dn_key" which is 64 bits. Some macros are used to
  67  * compare key values and handle wraparounds.
  68  * MAX64 returns the largest of two key values.
  69  * MY_M is used as a shift count when doing fixed point arithmetic
  70  * (a better name would be useful...).
  71  */
  72 typedef u_int64_t dn_key ;      /* sorting key */
  73 #define DN_KEY_LT(a,b)     ((int64_t)((a)-(b)) < 0)
  74 #define DN_KEY_LEQ(a,b)    ((int64_t)((a)-(b)) <= 0)
  75 #define DN_KEY_GT(a,b)     ((int64_t)((a)-(b)) > 0)
  76 #define DN_KEY_GEQ(a,b)    ((int64_t)((a)-(b)) >= 0)
  77 #define MAX64(x,y)  (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
  78 #define MY_M    16 /* number of left shift to obtain a larger precision */
  79
  80 /*
  81  * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
  82  * virtual time wraps every 15 days.
  83  */
  84
  85 /*
  86  * The OFFSET_OF macro is used to return the offset of a field within
  87  * a structure. It is used by the heap management routines.
  88  */
  89 #define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) )
  90
  91 /*
  92  * A heap entry is made of a key and a pointer to the actual
  93  * object stored in the heap.
  94  * The heap is an array of dn_heap_entry entries, dynamically allocated.
  95  * Current size is "size", with "elements" actually in use.
  96  * The heap normally supports only ordered insert and extract from the top.
  97  * If we want to extract an object from the middle of the heap, we
  98  * have to know where the object itself is located in the heap (or we
  99  * need to scan the whole array). To this purpose, an object has a
 100  * field (int) which contains the index of the object itself into the
 101  * heap. When the object is moved, the field must also be updated.
 102  * The offset of the index in the object is stored in the 'offset'
 103  * field in the heap descriptor. The assumption is that this offset
 104  * is non-zero if we want to support extract from the middle.
 105  */
 106 struct dn_heap_entry {
 107     dn_key key ;        /* sorting key. Topmost element is smallest one */
 108     void *object ;      /* object pointer */
 109 } ;
 110
 111 struct dn_heap {
 112     int size ;
 113     int elements ;
 114     int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */
 115     struct dn_heap_entry *p ;   /* really an array of "size" entries */
 116 } ;
 117
 118 /*
 119  * MT_DUMMYNET is a new (fake) mbuf type that is prepended to the
 120  * packet when it comes out of a pipe. The definition
 121  * ought to go in /sys/sys/mbuf.h but here it is less intrusive.
 122  */
 123
 124 #define MT_DUMMYNET MT_CONTROL
 125
 126 /*
 127  * struct dn_pkt identifies a packet in the dummynet queue. The
 128  * first part is really an m_hdr for implementation purposes, and some
 129  * fields are saved there. When passing the packet back to the ip_input/
 130  * ip_output()/bdg_forward, the struct is prepended to the mbuf chain with type
 131  * MT_DUMMYNET, and contains the pointer to the matching rule.
 132  *
 133  * Note: there is no real need to make this structure contain an m_hdr,
 134  * in the future this should be changed to a normal data structure.
 135  */
 136 struct dn_pkt {
 137         struct m_hdr hdr ;
 138 #define dn_next hdr.mh_nextpkt  /* next element in queue */
 139 #define DN_NEXT(x)      (struct dn_pkt *)(x)->dn_next
 140 #define dn_m    hdr.mh_next     /* packet to be forwarded */
 141 #define dn_dir  hdr.mh_flags    /* action when pkt extracted from a queue */
 142 #define DN_TO_IP_OUT    1
 143 #define DN_TO_IP_IN     2
 144 #define DN_TO_BDG_FWD   3
 145
 146         dn_key  output_time;    /* when the pkt is due for delivery */
 147         struct ifnet *ifp;      /* interface, for ip_output             */
 148         struct sockaddr_in *dn_dst ;
 149         struct route ro;        /* route, for ip_output. MUST COPY      */
 150         int flags ;             /* flags, for ip_output (IPv6 ?) */
 151 };
 152
 153 /*
 154  * Overall structure of dummynet (with WF2Q+):
 155
 156 In dummynet, packets are selected with the firewall rules, and passed
 157 to two different objects: PIPE or QUEUE.
 158
 159 A QUEUE is just a queue with configurable size and queue management
 160 policy. It is also associated with a mask (to discriminate among
 161 different flows), a weight (used to give different shares of the
 162 bandwidth to different flows) and a "pipe", which essentially
 163 supplies the transmit clock for all queues associated with that
 164 pipe.
 165
 166 A PIPE emulates a fixed-bandwidth link, whose bandwidth is
 167 configurable.  The "clock" for a pipe can come from either an
 168 internal timer, or from the transmit interrupt of an interface.
 169 A pipe is also associated with one (or more, if masks are used)
 170 queue, where all packets for that pipe are stored.
 171
 172 The bandwidth available on the pipe is shared by the queues
 173 associated with that pipe (only one in case the packet is sent
 174 to a PIPE) according to the WF2Q+ scheduling algorithm and the
 175 configured weights.
 176
 177 In general, incoming packets are stored in the appropriate queue,
 178 which is then placed into one of a few heaps managed by a scheduler
 179 to decide when the packet should be extracted.
 180 The scheduler (a function called dummynet()) is run at every timer
 181 tick, and grabs queues from the head of the heaps when they are
 182 ready for processing.
 183
 184 There are three data structures definining a pipe and associated queues:
 185
 186  + dn_pipe, which contains the main configuration parameters related
 187    to delay and bandwidth;
 188  + dn_flow_set, which contains WF2Q+ configuration, flow
 189    masks, plr and RED configuration;
 190  + dn_flow_queue, which is the per-flow queue (containing the packets)
 191
 192 Multiple dn_flow_set can be linked to the same pipe, and multiple
 193 dn_flow_queue can be linked to the same dn_flow_set.
 194 All data structures are linked in a linear list which is used for
 195 housekeeping purposes.
 196
 197 During configuration, we create and initialize the dn_flow_set
 198 and dn_pipe structures (a dn_pipe also contains a dn_flow_set).
 199
 200 At runtime: packets are sent to the appropriate dn_flow_set (either
 201 WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows),
 202 which in turn dispatches them to the appropriate dn_flow_queue
 203 (created dynamically according to the masks).
 204
 205 The transmit clock for fixed rate flows (ready_event()) selects the
 206 dn_flow_queue to be used to transmit the next packet. For WF2Q,
 207 wfq_ready_event() extract a pipe which in turn selects the right
 208 flow using a number of heaps defined into the pipe itself.
 209
 210  *
 211  */
 212
 213 /*
 214  * per flow queue. This contains the flow identifier, the queue
 215  * of packets, counters, and parameters used to support both RED and
 216  * WF2Q+.
 217  */
 218 struct dn_flow_queue {
 219     struct dn_flow_queue *next ;
 220     struct ipfw_flow_id id ;
 221     struct dn_pkt *head, *tail ;        /* queue of packets */
 222     u_int len ;
 223     u_int len_bytes ;
 224     long numbytes ;             /* credit for transmission (dynamic queues) */
 225
 226     u_int64_t tot_pkts ;        /* statistics counters  */
 227     u_int64_t tot_bytes ;
 228     u_int32_t drops ;
 229     int hash_slot ;     /* debugging/diagnostic */
 230
 231     /* RED parameters */
 232     int avg ;                   /* average queue length est. (scaled) */
 233     int count ;                 /* arrivals since last RED drop */
 234     int random ;                /* random value (scaled) */
 235     u_int32_t q_time ;          /* start of queue idle time */
 236
 237     /* WF2Q+ support */
 238     struct dn_flow_set *fs ; /* parent flow set */
 239     int heap_pos ;      /* position (index) of struct in heap */
 240     dn_key sched_time ; /* current time when queue enters ready_heap */
 241
 242     dn_key S,F ; /* start-time, finishing time */
 243     /* setting F < S means the timestamp is invalid. We only need
 244      * to test this when the queue is empty.
 245      */
 246 } ;
 247
 248 /*
 249  * flow_set descriptor. Contains the "template" parameters for the
 250  * queue configuration, and pointers to the hash table of dn_flow_queue's.
 251  *
 252  * The hash table is an array of lists -- we identify the slot by
 253  * hashing the flow-id, then scan the list looking for a match.
 254  * The size of the hash table (buckets) is configurable on a per-queue
 255  * basis.
 256  */
 257 struct dn_flow_set {
 258     struct dn_flow_set *next; /* next flow set in all_flow_sets list */
 259
 260     u_short fs_nr ;             /* flow_set number       */
 261     u_short flags_fs;
 262 #define DN_HAVE_FLOW_MASK       0x0001
 263 #define DN_IS_PIPE              0x4000
 264 #define DN_IS_QUEUE             0x8000
 265 #define DN_IS_RED               0x0002
 266 #define DN_IS_GENTLE_RED        0x0004
 267 #define DN_QSIZE_IS_BYTES       0x0008  /* queue measured in bytes */
 268
 269     struct dn_pipe *pipe ;              /* pointer to parent pipe */
 270     u_short parent_nr ;         /* parent pipe#, 0 if local to a pipe */
 271
 272     int weight ; /* WFQ queue weight */
 273     int qsize ;         /* queue size in slots or bytes */
 274     int plr ;           /* pkt loss rate (2^31-1 means 100%) */
 275
 276     struct ipfw_flow_id flow_mask ;
 277     /* hash table of queues onto this flow_set */
 278     int rq_size ;               /* number of slots */
 279     int rq_elements ;           /* active elements */
 280     struct dn_flow_queue **rq;  /* array of rq_size entries */
 281     u_int32_t last_expired ;    /* do not expire too frequently */
 282         /* XXX some RED parameters as well ? */
 283     int backlogged ;            /* #active queues for this flowset */
 284
 285         /* RED parameters */
 286 #define SCALE_RED               16
 287 #define SCALE(x)                ( (x) << SCALE_RED )
 288 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 289 #define SCALE_MUL(x,y)          ( ( (x) * (y) ) >> SCALE_RED )
 290     int w_q ;               /* queue weight (scaled) */
 291     int max_th ;            /* maximum threshold for queue (scaled) */
 292     int min_th ;            /* minimum threshold for queue (scaled) */
 293     int max_p ;             /* maximum value for p_b (scaled) */
 294     u_int c_1 ;             /* max_p/(max_th-min_th) (scaled) */
 295     u_int c_2 ;             /* max_p*min_th/(max_th-min_th) (scaled) */
 296     u_int c_3 ;             /* for GRED, (1-max_p)/max_th (scaled) */
 297     u_int c_4 ;             /* for GRED, 1 - 2*max_p (scaled) */
 298     u_int * w_q_lookup ;    /* lookup table for computing (1-w_q)^t */
 299     u_int lookup_depth ;    /* depth of lookup table */
 300     int lookup_step ;       /* granularity inside the lookup table */
 301     int lookup_weight ;     /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 302     int avg_pkt_size ;      /* medium packet size */
 303     int max_pkt_size ;      /* max packet size */
 304 } ;
 305
 306 /*
 307  * Pipe descriptor. Contains global parameters, delay-line queue,
 308  * and the flow_set used for fixed-rate queues.
 309  *
 310  * For WF2Q support it also has 4 heaps holding dn_flow_queue:
 311  *   not_eligible_heap, for queues whose start time is higher
 312  *      than the virtual time. Sorted by start time.
 313  *   scheduler_heap, for queues eligible for scheduling. Sorted by
 314  *      finish time.
 315  *   backlogged_heap, all flows in the two heaps above, sorted by
 316  *      start time. This is used to compute the virtual time.
 317  *   idle_heap, all flows that are idle and can be removed. We
 318  *      do that on each tick so we do not slow down too much
 319  *      operations during forwarding.
 320  *
 321  */
 322 struct dn_pipe {                        /* a pipe */
 323         struct dn_pipe *next ;
 324
 325     int pipe_nr ;               /* number       */
 326         int     bandwidth;              /* really, bytes/tick.  */
 327         int     delay ;                 /* really, ticks        */
 328
 329     struct      dn_pkt *head, *tail ;   /* packets in delay line */
 330
 331     /* WF2Q+ */
 332     struct dn_heap scheduler_heap ; /* top extract - key Finish time*/
 333     struct dn_heap not_eligible_heap; /* top extract- key Start time */
 334     struct dn_heap idle_heap ; /* random extract - key Start=Finish time */
 335
 336     dn_key V ; /* virtual time */
 337     int sum;    /* sum of weights of all active sessions */
 338     int numbytes;       /* bit i can transmit (more or less). */
 339
 340     dn_key sched_time ; /* first time pipe is scheduled in ready_heap */
 341
 342     /* the tx clock can come from an interface. In this case, the
 343      * name is below, and the pointer is filled when the rule is
 344      * configured. We identify this by setting the if_name to a
 345      * non-empty string.
 346      */
 347     char if_name[16];
 348     struct ifnet *ifp ;
 349     int ready ; /* set if ifp != NULL and we got a signal from it */
 350
 351     struct dn_flow_set fs ; /* used with fixed-rate flows */
 352 };
 353
 354 #ifdef KERNEL
 355
 356 MALLOC_DECLARE(M_IPFW);
 357
 358 typedef int ip_dn_ctl_t __P((struct sockopt *)) ;
 359 extern ip_dn_ctl_t *ip_dn_ctl_ptr;
 360
 361 void dn_rule_delete(void *r);           /* used in ip_fw.c */
 362 int dummynet_io(int pipe, int dir,
 363         struct mbuf *m, struct ifnet *ifp, struct route *ro,
 364         struct sockaddr_in * dst,
 365         struct ip_fw_chain *rule, int flags);
 366 #endif
 367
 368 #endif /* __APPLE_API_PRIVATE */
 369 #endif /* _IP_DUMMYNET_H */