sys/net/dummynet/ip_dummynet.h

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