dummynet/include/netinet/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.40.2.1 2008/04/25 10:26:30 oleg Exp $
  28  */
  29
  30 #ifndef _IP_DUMMYNET_H
  31 #define _IP_DUMMYNET_H
  32
  33 /*
  34  * Definition of dummynet data structures. In the structures, I decided
  35  * not to use the macros in <sys/queue.h> in the hope of making the code
  36  * easier to port to other architectures. The type of lists and queue we
  37  * use here is pretty simple anyways.
  38  */
  39
  40 /*
  41  * We start with a heap, which is used in the scheduler to decide when
  42  * to transmit packets etc.
  43  *
  44  * The key for the heap is used for two different values:
  45  *
  46  * 1. timer ticks- max 10K/second, so 32 bits are enough;
  47  *
  48  * 2. virtual times. These increase in steps of len/x, where len is the
  49  *    packet length, and x is either the weight of the flow, or the
  50  *    sum of all weights.
  51  *    If we limit to max 1000 flows and a max weight of 100, then
  52  *    x needs 17 bits. The packet size is 16 bits, so we can easily
  53  *    overflow if we do not allow errors.
  54  * So we use a key "dn_key" which is 64 bits. Some macros are used to
  55  * compare key values and handle wraparounds.
  56  * MAX64 returns the largest of two key values.
  57  * MY_M is used as a shift count when doing fixed point arithmetic
  58  * (a better name would be useful...).
  59  */
  60 typedef u_int64_t dn_key ;      /* sorting key */
  61 #define DN_KEY_LT(a,b)     ((int64_t)((a)-(b)) < 0)
  62 #define DN_KEY_LEQ(a,b)    ((int64_t)((a)-(b)) <= 0)
  63 #define DN_KEY_GT(a,b)     ((int64_t)((a)-(b)) > 0)
  64 #define DN_KEY_GEQ(a,b)    ((int64_t)((a)-(b)) >= 0)
  65 #define MAX64(x,y)  (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
  66 #define MY_M    16 /* number of left shift to obtain a larger precision */
  67
  68 /*
  69  * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
  70  * virtual time wraps every 15 days.
  71  */
  72
  73
  74 /*
  75  * The maximum hash table size for queues.  This value must be a power
  76  * of 2.
  77  */
  78 #define DN_MAX_HASH_SIZE 65536
  79
  80 /*
  81  * A heap entry is made of a key and a pointer to the actual
  82  * object stored in the heap.
  83  * The heap is an array of dn_heap_entry entries, dynamically allocated.
  84  * Current size is "size", with "elements" actually in use.
  85  * The heap normally supports only ordered insert and extract from the top.
  86  * If we want to extract an object from the middle of the heap, we
  87  * have to know where the object itself is located in the heap (or we
  88  * need to scan the whole array). To this purpose, an object has a
  89  * field (int) which contains the index of the object itself into the
  90  * heap. When the object is moved, the field must also be updated.
  91  * The offset of the index in the object is stored in the 'offset'
  92  * field in the heap descriptor. The assumption is that this offset
  93  * is non-zero if we want to support extract from the middle.
  94  */
  95 struct dn_heap_entry {
  96     dn_key key ;        /* sorting key. Topmost element is smallest one */
  97     void *object ;      /* object pointer */
  98 } ;
  99
 100 struct dn_heap {
 101     int size ;
 102     int elements ;
 103     int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */
 104     struct dn_heap_entry *p ;   /* really an array of "size" entries */
 105 } ;
 106
 107 #ifdef _KERNEL
 108 /*
 109  * Packets processed by dummynet have an mbuf tag associated with
 110  * them that carries their dummynet state.  This is used within
 111  * the dummynet code as well as outside when checking for special
 112  * processing requirements.
 113  */
 114 struct dn_pkt_tag {
 115     struct ip_fw *rule;         /* matching rule */
 116     uint32_t rule_id;           /* matching rule id */
 117     uint32_t chain_id;          /* ruleset id */
 118     int dn_dir;                 /* action when packet comes out. */
 119 #define DN_TO_IP_OUT    1
 120 #define DN_TO_IP_IN     2
 121 /* Obsolete: #define DN_TO_BDG_FWD      3 */
 122 #define DN_TO_ETH_DEMUX 4
 123 #define DN_TO_ETH_OUT   5
 124 #define DN_TO_IP6_IN    6
 125 #define DN_TO_IP6_OUT   7
 126 #define DN_TO_IFB_FWD   8
 127
 128     dn_key output_time;         /* when the pkt is due for delivery     */
 129     struct ifnet *ifp;          /* interface, for ip_output             */
 130     struct _ip6dn_args ip6opt;  /* XXX ipv6 options                     */
 131 };
 132 #endif /* _KERNEL */
 133
 134 /*
 135  * Overall structure of dummynet (with WF2Q+):
 136
 137 In dummynet, packets are selected with the firewall rules, and passed
 138 to two different objects: PIPE or QUEUE.
 139
 140 A QUEUE is just a queue with configurable size and queue management
 141 policy. It is also associated with a mask (to discriminate among
 142 different flows), a weight (used to give different shares of the
 143 bandwidth to different flows) and a "pipe", which essentially
 144 supplies the transmit clock for all queues associated with that
 145 pipe.
 146
 147 A PIPE emulates a fixed-bandwidth link, whose bandwidth is
 148 configurable.  The "clock" for a pipe can come from either an
 149 internal timer, or from the transmit interrupt of an interface.
 150 A pipe is also associated with one (or more, if masks are used)
 151 queue, where all packets for that pipe are stored.
 152
 153 The bandwidth available on the pipe is shared by the queues
 154 associated with that pipe (only one in case the packet is sent
 155 to a PIPE) according to the WF2Q+ scheduling algorithm and the
 156 configured weights.
 157
 158 In general, incoming packets are stored in the appropriate queue,
 159 which is then placed into one of a few heaps managed by a scheduler
 160 to decide when the packet should be extracted.
 161 The scheduler (a function called dummynet()) is run at every timer
 162 tick, and grabs queues from the head of the heaps when they are
 163 ready for processing.
 164
 165 There are three data structures definining a pipe and associated queues:
 166
 167  + dn_pipe, which contains the main configuration parameters related
 168    to delay and bandwidth;
 169  + dn_flow_set, which contains WF2Q+ configuration, flow
 170    masks, plr and RED configuration;
 171  + dn_flow_queue, which is the per-flow queue (containing the packets)
 172
 173 Multiple dn_flow_set can be linked to the same pipe, and multiple
 174 dn_flow_queue can be linked to the same dn_flow_set.
 175 All data structures are linked in a linear list which is used for
 176 housekeeping purposes.
 177
 178 During configuration, we create and initialize the dn_flow_set
 179 and dn_pipe structures (a dn_pipe also contains a dn_flow_set).
 180
 181 At runtime: packets are sent to the appropriate dn_flow_set (either
 182 WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows),
 183 which in turn dispatches them to the appropriate dn_flow_queue
 184 (created dynamically according to the masks).
 185
 186 The transmit clock for fixed rate flows (ready_event()) selects the
 187 dn_flow_queue to be used to transmit the next packet. For WF2Q,
 188 wfq_ready_event() extract a pipe which in turn selects the right
 189 flow using a number of heaps defined into the pipe itself.
 190
 191  *
 192  */
 193
 194 /*
 195  * per flow queue. This contains the flow identifier, the queue
 196  * of packets, counters, and parameters used to support both RED and
 197  * WF2Q+.
 198  *
 199  * A dn_flow_queue is created and initialized whenever a packet for
 200  * a new flow arrives.
 201  */
 202 struct dn_flow_queue {
 203     struct dn_flow_queue *next ;
 204     struct ipfw_flow_id id ;
 205
 206     struct mbuf *head, *tail ;  /* queue of packets */
 207     u_int len ;
 208     u_int len_bytes ;
 209
 210     /*
 211      * When we emulate MAC overheads, or channel unavailability due
 212      * to other traffic on a shared medium, we augment the packet at
 213      * the head of the queue with an 'extra_bits' field representsing
 214      * the additional delay the packet will be subject to:
 215      *          extra_bits = bw*unavailable_time.
 216      * With large bandwidth and large delays, extra_bits (and also numbytes)
 217      * can become very large, so better play safe and use 64 bit
 218      */
 219     uint64_t numbytes ;         /* credit for transmission (dynamic queues) */
 220     int64_t extra_bits;         /* extra bits simulating unavailable channel */
 221
 222     u_int64_t tot_pkts ;        /* statistics counters  */
 223     u_int64_t tot_bytes ;
 224     u_int32_t drops ;
 225
 226     int hash_slot ;             /* debugging/diagnostic */
 227
 228     /* RED parameters */
 229     int avg ;                   /* average queue length est. (scaled) */
 230     int count ;                 /* arrivals since last RED drop */
 231     int random ;                /* random value (scaled) */
 232     dn_key q_time;              /* start of queue idle time */
 233
 234     /* WF2Q+ support */
 235     struct dn_flow_set *fs ;    /* parent flow set */
 236     int heap_pos ;              /* position (index) of struct in heap */
 237     dn_key sched_time ;         /* current time when queue enters ready_heap */
 238
 239     dn_key S,F ;                /* start time, finish time */
 240     /*
 241      * Setting F < S means the timestamp is invalid. We only need
 242      * to test this when the queue is empty.
 243      */
 244 } ;
 245
 246 /*
 247  * flow_set descriptor. Contains the "template" parameters for the
 248  * queue configuration, and pointers to the hash table of dn_flow_queue's.
 249  *
 250  * The hash table is an array of lists -- we identify the slot by
 251  * hashing the flow-id, then scan the list looking for a match.
 252  * The size of the hash table (buckets) is configurable on a per-queue
 253  * basis.
 254  *
 255  * A dn_flow_set is created whenever a new queue or pipe is created (in the
 256  * latter case, the structure is located inside the struct dn_pipe).
 257  */
 258 struct dn_flow_set {
 259     SLIST_ENTRY(dn_flow_set)    next;   /* linked list in a hash slot */
 260
 261     u_short fs_nr ;             /* flow_set number       */
 262     u_short flags_fs;
 263 #define DN_HAVE_FLOW_MASK       0x0001
 264 #define DN_IS_RED               0x0002
 265 #define DN_IS_GENTLE_RED        0x0004
 266 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 267 #define DN_NOERROR              0x0010  /* do not report ENOBUFS on drops  */
 268 #define DN_HAS_PROFILE          0x0020  /* the pipe has a delay profile. */
 269 #define DN_IS_PIPE              0x4000
 270 #define DN_IS_QUEUE             0x8000
 271
 272     struct dn_pipe *pipe ;      /* pointer to parent pipe */
 273     u_short parent_nr ;         /* parent pipe#, 0 if local to a pipe */
 274
 275     int weight ;                /* WFQ queue weight */
 276     int qsize ;                 /* queue size in slots or bytes */
 277     int plr ;                   /* pkt loss rate (2^31-1 means 100%) */
 278
 279     struct ipfw_flow_id flow_mask ;
 280
 281     /* hash table of queues onto this flow_set */
 282     int rq_size ;               /* number of slots */
 283     int rq_elements ;           /* active elements */
 284     struct dn_flow_queue **rq;  /* array of rq_size entries */
 285
 286     u_int32_t last_expired ;    /* do not expire too frequently */
 287     int backlogged ;            /* #active queues for this flowset */
 288
 289         /* RED parameters */
 290 #define SCALE_RED               16
 291 #define SCALE(x)                ( (x) << SCALE_RED )
 292 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 293 #define SCALE_MUL(x,y)          ( ( (x) * (y) ) >> SCALE_RED )
 294     int w_q ;                   /* queue weight (scaled) */
 295     int max_th ;                /* maximum threshold for queue (scaled) */
 296     int min_th ;                /* minimum threshold for queue (scaled) */
 297     int max_p ;                 /* maximum value for p_b (scaled) */
 298     u_int c_1 ;                 /* max_p/(max_th-min_th) (scaled) */
 299     u_int c_2 ;                 /* max_p*min_th/(max_th-min_th) (scaled) */
 300     u_int c_3 ;                 /* for GRED, (1-max_p)/max_th (scaled) */
 301     u_int c_4 ;                 /* for GRED, 1 - 2*max_p (scaled) */
 302     u_int * w_q_lookup ;        /* lookup table for computing (1-w_q)^t */
 303     u_int lookup_depth ;        /* depth of lookup table */
 304     int lookup_step ;           /* granularity inside the lookup table */
 305     int lookup_weight ;         /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 306     int avg_pkt_size ;          /* medium packet size */
 307     int max_pkt_size ;          /* max packet size */
 308 };
 309 SLIST_HEAD(dn_flow_set_head, dn_flow_set);
 310
 311 /*
 312  * Pipe descriptor. Contains global parameters, delay-line queue,
 313  * and the flow_set used for fixed-rate queues.
 314  *
 315  * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
 316  *   not_eligible_heap, for queues whose start time is higher
 317  *      than the virtual time. Sorted by start time.
 318  *   scheduler_heap, for queues eligible for scheduling. Sorted by
 319  *      finish time.
 320  *   idle_heap, all flows that are idle and can be removed. We
 321  *      do that on each tick so we do not slow down too much
 322  *      operations during forwarding.
 323  *
 324  */
 325 struct dn_pipe {                /* a pipe */
 326     SLIST_ENTRY(dn_pipe)        next;   /* linked list in a hash slot */
 327
 328     int pipe_nr ;               /* number       */
 329     int bandwidth;              /* really, bytes/tick.  */
 330     int delay ;                 /* really, ticks        */
 331
 332     struct      mbuf *head, *tail ;     /* packets in delay line */
 333
 334     /* WF2Q+ */
 335     struct dn_heap scheduler_heap ; /* top extract - key Finish time*/
 336     struct dn_heap not_eligible_heap; /* top extract- key Start time */
 337     struct dn_heap idle_heap ; /* random extract - key Start=Finish time */
 338
 339     dn_key V ;                  /* virtual time */
 340     int sum;                    /* sum of weights of all active sessions */
 341
 342     /* Same as in dn_flow_queue, numbytes can become large */
 343     int64_t numbytes;           /* bits I can transmit (more or less). */
 344     uint64_t burst;             /* burst size, scaled: bits * hz */
 345
 346     dn_key sched_time ;         /* time pipe was scheduled in ready_heap */
 347     dn_key idle_time;           /* start of pipe idle time */
 348
 349     /*
 350      * When the tx clock come from an interface (if_name[0] != '\0'), its name
 351      * is stored below, whereas the ifp is filled when the rule is configured.
 352      */
 353     char if_name[IFNAMSIZ];
 354     struct ifnet *ifp ;
 355     int ready ; /* set if ifp != NULL and we got a signal from it */
 356
 357     struct dn_flow_set fs ; /* used with fixed-rate flows */
 358
 359     /* fields to simulate a delay profile */
 360
 361 #define ED_MAX_NAME_LEN         32
 362     char name[ED_MAX_NAME_LEN];
 363     int loss_level;
 364     int samples_no;
 365     int *samples;
 366 };
 367
 368 /* dn_pipe_max is used to pass pipe configuration from userland onto
 369  * kernel space and back
 370  */
 371 #define ED_MAX_SAMPLES_NO       1024
 372 struct dn_pipe_max {
 373         struct dn_pipe pipe;
 374         int samples[ED_MAX_SAMPLES_NO];
 375 };
 376
 377 SLIST_HEAD(dn_pipe_head, dn_pipe);
 378
 379 #ifdef _KERNEL
 380 typedef void ip_dn_ruledel_t(void *); /* ip_fw.c */
 381 extern  ip_dn_ruledel_t *ip_dn_ruledel_ptr;
 382
 383 /*
 384  * Return the IPFW rule associated with the dummynet tag; if any.
 385  * Make sure that the dummynet tag is not reused by lower layers.
 386  */
 387 static __inline struct ip_fw *
 388 ip_dn_claim_rule(struct mbuf *m)
 389 {
 390         struct m_tag *mtag = m_tag_find(m, PACKET_TAG_DUMMYNET, NULL);
 391         if (mtag != NULL) {
 392                 mtag->m_tag_id = PACKET_TAG_NONE;
 393                 return (((struct dn_pkt_tag *)(mtag+1))->rule);
 394         } else
 395                 return (NULL);
 396 }
 397 #endif
 398 #endif /* _IP_DUMMYNET_H */