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.13 2007/11/05 15:16:46 sephe 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 to
  43  * 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 sum
  51  *    of all weights.
  52  *    If we limit to max 1000 flows and a max weight of 100, then x needs
  53  *    17 bits.  The packet size is 16 bits, so we can easily overflow if
  54  *    we do not allow errors.
  55  *
  56  * So we use a key "dn_key" which is 64 bits.
  57  *
  58  * MY_M is used as a shift count when doing fixed point arithmetic
  59  * (a better name would be useful...).
  60  */
  61 typedef uint64_t        dn_key; /* sorting key */
  62
  63 /*
  64  * Number of left shift to obtain a larger precision
  65  *
  66  * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
  67  * virtual time wraps every 15 days.
  68  */
  69 #define MY_M            16
  70
  71 #ifdef _KERNEL
  72
  73 /*
  74  * A heap entry is made of a key and a pointer to the actual object stored
  75  * in the heap.
  76  *
  77  * The heap is an array of dn_heap_entry entries, dynamically allocated.
  78  * Current size is "size", with "elements" actually in use.
  79  *
  80  * The heap normally supports only ordered insert and extract from the top.
  81  * If we want to extract an object from the middle of the heap, we have to
  82  * know where the object itself is located in the heap (or we need to scan
  83  * the whole array).  To this purpose, an object has a field (int) which
  84  * contains the index of the object itself into the heap.  When the object
  85  * is moved, the field must also be updated.  The offset of the index in the
  86  * object is stored in the 'offset' field in the heap descriptor.  The
  87  * assumption is that this offset is non-zero if we want to support extract
  88  * from the middle.
  89  */
  90 struct dn_heap_entry {
  91     dn_key key;         /* sorting key.  Topmost element is smallest one */
  92     void *object;       /* object pointer */
  93 };
  94
  95 struct dn_heap {
  96     int size;
  97     int elements;
  98     int offset; /* XXX if > 0 this is the offset of direct ptr to obj */
  99     struct dn_heap_entry *p;    /* really an array of "size" entries */
 100 };
 101
 102 /*
 103  * struct dn_pkt identifies a packet in the dummynet queue, but is also used
 104  * to tag packets passed back to the various destinations (ip_input(),
 105  * ip_output() and so on).
 106  *
 107  * It is a tag (PACKET_TAG_DUMMYNET) associated with the actual mbuf.
 108  */
 109 struct dn_pkt {
 110     struct mbuf *dn_m;
 111     struct dn_pkt *dn_next;
 112
 113     struct ip_fw *rule;         /* matching rule */
 114     int dn_dir;                 /* action when packet comes out. */
 115 #define DN_TO_IP_OUT    1
 116 #define DN_TO_IP_IN     2
 117 #define DN_TO_ETH_DEMUX 4
 118 #define DN_TO_ETH_OUT   5
 119
 120     dn_key output_time;         /* when the pkt is due for delivery */
 121     struct ifnet *ifp;          /* interface, for ip_output */
 122     struct sockaddr_in *dn_dst;
 123     struct route ro;            /* route, for ip_output. MUST COPY */
 124     int flags;                  /* flags, for ip_output (IPv6 ?) */
 125 };
 126
 127 /*
 128  * Overall structure of dummynet (with WF2Q+):
 129  *
 130  * In dummynet, packets are selected with the firewall rules, and passed to
 131  * two different objects: PIPE or QUEUE.
 132  *
 133  * A QUEUE is just a queue with configurable size and queue management policy.
 134  * It is also associated with a mask (to discriminate among different flows),
 135  * a weight (used to give different shares of the bandwidth to different flows)
 136  * and a "pipe", which essentially supplies the transmit clock for all queues
 137  * associated with that pipe.
 138  *
 139  * A PIPE emulates a fixed-bandwidth link, whose bandwidth is configurable.
 140  * The "clock" for a pipe comes from an internal timer.  A pipe is also
 141  * associated with one (or more, if masks are used) queue, where all packets
 142  * for that pipe are stored.
 143  *
 144  * The bandwidth available on the pipe is shared by the queues associated with
 145  * that pipe (only one in case the packet is sent to a PIPE) according to the
 146  * WF2Q+ scheduling algorithm and the configured weights.
 147  *
 148  * In general, incoming packets are stored in the appropriate queue, which is
 149  * then placed into one of a few heaps managed by a scheduler to decide when
 150  * the packet should be extracted.  The scheduler (a function called dummynet())
 151  * is run at every timer tick, and grabs queues from the head of the heaps when
 152  * they are ready for processing.
 153  *
 154  * There are three data structures definining a pipe and associated queues:
 155  *
 156  *  + dn_pipe, which contains the main configuration parameters related to
 157  *    delay and bandwidth;
 158  *  + dn_flow_set, which contains WF2Q+ configuration, flow masks, plr and
 159  *    RED configuration;
 160  *  + dn_flow_queue, which is the per-flow queue (containing the packets)
 161  *
 162  * Multiple dn_flow_set can be linked to the same pipe, and multiple
 163  * dn_flow_queue can be linked to the same dn_flow_set.
 164  * All data structures are linked in a linear list which is used for
 165  * housekeeping purposes.
 166  *
 167  * During configuration, we create and initialize the dn_flow_set and dn_pipe
 168  * structures (a dn_pipe also contains a dn_flow_set).
 169  *
 170  * At runtime: packets are sent to the appropriate dn_flow_set (either WFQ
 171  * ones, or the one embedded in the dn_pipe for fixed-rate flows), which in
 172  * turn dispatches them to the appropriate dn_flow_queue (created dynamically
 173  * according to the masks).
 174  *
 175  * The transmit clock for fixed rate flows (ready_event()) selects the
 176  * dn_flow_queue to be used to transmit the next packet. For WF2Q,
 177  * wfq_ready_event() extract a pipe which in turn selects the right flow using
 178  * a number of heaps defined into the pipe itself.
 179  */
 180
 181 /*
 182  * Per flow queue.  This contains the flow identifier, the queue of packets,
 183  * counters, and parameters used to support both RED and WF2Q+.
 184  *
 185  * A dn_flow_queue is created and initialized whenever a packet for a new
 186  * flow arrives.
 187  */
 188 struct dn_flow_queue {
 189     struct dn_flow_queue *next;
 190     struct ipfw_flow_id id;
 191
 192     struct dn_pkt *head, *tail; /* queue of packets */
 193     u_int len;
 194     u_int len_bytes;
 195     u_long numbytes;            /* credit for transmission (dynamic queues) */
 196
 197     uint64_t tot_pkts;          /* statistics counters */
 198     uint64_t tot_bytes;
 199     uint32_t drops;
 200
 201     int hash_slot;              /* debugging/diagnostic */
 202
 203     /* RED parameters */
 204     int avg;                    /* average queue length est. (scaled) */
 205     int count;                  /* arrivals since last RED drop */
 206     int random;                 /* random value (scaled) */
 207     uint32_t q_time;            /* start of queue idle time */
 208
 209     /* WF2Q+ support */
 210     struct dn_flow_set *fs;     /* parent flow set */
 211     int heap_pos;               /* position (index) of struct in heap */
 212     dn_key sched_time;          /* current time when queue enters ready_heap */
 213
 214     dn_key S, F;                /* start time, finish time */
 215     /*
 216      * Setting F < S means the timestamp is invalid. We only need
 217      * to test this when the queue is empty.
 218      */
 219 };
 220
 221 /*
 222  * flow_set descriptor.  Contains the "template" parameters for the queue
 223  * configuration, and pointers to the hash table of dn_flow_queue's.
 224  *
 225  * The hash table is an array of lists -- we identify the slot by hashing
 226  * the flow-id, then scan the list looking for a match.
 227  * The size of the hash table (buckets) is configurable on a per-queue basis.
 228  *
 229  * A dn_flow_set is created whenever a new queue or pipe is created (in the
 230  * latter case, the structure is located inside the struct dn_pipe).
 231  */
 232 struct dn_flow_set {
 233     struct dn_flow_set *next;   /* next flow set in all_flow_sets list */
 234
 235     u_short fs_nr;              /* flow_set number */
 236     u_short flags_fs;           /* see 'Flow set flags' */
 237
 238     struct dn_pipe *pipe;       /* pointer to parent pipe */
 239     u_short parent_nr;          /* parent pipe#, 0 if local to a pipe */
 240
 241     int weight;                 /* WFQ queue weight */
 242     int qsize;                  /* queue size in slots or bytes */
 243     int plr;                    /* pkt loss rate (2^31-1 means 100%) */
 244
 245     struct ipfw_flow_id flow_mask;
 246
 247     /* hash table of queues onto this flow_set */
 248     int rq_size;                /* number of slots */
 249     int rq_elements;            /* active elements */
 250     struct dn_flow_queue **rq;  /* array of rq_size entries */
 251
 252     uint32_t last_expired;      /* do not expire too frequently */
 253     int backlogged;             /* #active queues for this flowset */
 254
 255     /* RED parameters */
 256     int w_q;                    /* queue weight (scaled) */
 257     int max_th;                 /* maximum threshold for queue (scaled) */
 258     int min_th;                 /* minimum threshold for queue (scaled) */
 259     int max_p;                  /* maximum value for p_b (scaled) */
 260     u_int c_1;                  /* max_p/(max_th-min_th) (scaled) */
 261     u_int c_2;                  /* max_p*min_th/(max_th-min_th) (scaled) */
 262     u_int c_3;                  /* for GRED, (1-max_p)/max_th (scaled) */
 263     u_int c_4;                  /* for GRED, 1 - 2*max_p (scaled) */
 264     u_int *w_q_lookup;          /* lookup table for computing (1-w_q)^t */
 265     u_int lookup_depth;         /* depth of lookup table */
 266     int lookup_step;            /* granularity inside the lookup table */
 267     int lookup_weight;          /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 268     int avg_pkt_size;           /* medium packet size */
 269     int max_pkt_size;           /* max packet size */
 270 };
 271
 272 /*
 273  * Pipe descriptor. Contains global parameters, delay-line queue, and the
 274  * flow_set used for fixed-rate queues.
 275  *
 276  * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
 277  *  + not_eligible_heap, for queues whose start time is higher than the
 278  *    virtual time. Sorted by start time.
 279  *  + scheduler_heap, for queues eligible for scheduling.  Sorted by finish
 280  *    time.
 281  *  + idle_heap, all flows that are idle and can be removed.  We do that on
 282  *    each tick so we do not slow down too much operations during forwarding.
 283  */
 284 struct dn_pipe {                /* a pipe */
 285     struct dn_pipe *next;
 286
 287     int pipe_nr;                /* number */
 288     int bandwidth;              /* really, bytes/tick. */
 289     int delay;                  /* really, ticks */
 290
 291     struct dn_pkt *head, *tail; /* packets in delay line */
 292
 293     /* WF2Q+ */
 294     struct dn_heap scheduler_heap; /* top extract - key Finish time*/
 295     struct dn_heap not_eligible_heap; /* top extract- key Start time */
 296     struct dn_heap idle_heap;   /* random extract - key Start=Finish time */
 297
 298     dn_key V;                   /* virtual time */
 299     int sum;                    /* sum of weights of all active sessions */
 300     int numbytes;               /* bits I can transmit (more or less). */
 301
 302     dn_key sched_time;          /* time pipe was scheduled in ready_heap */
 303
 304     struct dn_flow_set fs;      /* used with fixed-rate flows */
 305 };
 306
 307 typedef int     ip_dn_ctl_t(struct sockopt *);  /* raw_ip.c */
 308 typedef void    ip_dn_ruledel_t(void *);        /* ip_fw2.c */
 309 typedef int     ip_dn_io_t(struct mbuf *, int, int, struct ip_fw_args *);
 310
 311 extern ip_dn_ctl_t      *ip_dn_ctl_ptr;
 312 extern ip_dn_ruledel_t  *ip_dn_ruledel_ptr;
 313 extern ip_dn_io_t       *ip_dn_io_ptr;
 314
 315 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
 316
 317 #endif  /* _KERNEL */
 318
 319 struct dn_ioc_flowid {
 320     uint16_t type;      /* ETHERTYPE_ */
 321     uint16_t pad;
 322     union {
 323         struct {
 324             uint32_t dst_ip;
 325             uint32_t src_ip;
 326             uint16_t dst_port;
 327             uint16_t src_port;
 328             uint8_t proto;
 329             uint8_t flags;
 330         } ip;
 331         uint8_t pad[64];
 332     } u;
 333 };
 334
 335 struct dn_ioc_flowqueue {
 336     u_int len;
 337     u_int len_bytes;
 338
 339     uint64_t tot_pkts;
 340     uint64_t tot_bytes;
 341     uint32_t drops;
 342
 343     int hash_slot;              /* debugging/diagnostic */
 344     dn_key S;                   /* virtual start time */
 345     dn_key F;                   /* virtual finish time */
 346
 347     struct dn_ioc_flowid id;
 348     uint8_t reserved[16];
 349 };
 350
 351 struct dn_ioc_flowset {
 352     u_short fs_type;            /* DN_IS_{QUEUE,PIPE}, MUST be first */
 353
 354     u_short fs_nr;              /* flow_set number */
 355     u_short flags_fs;           /* see 'Flow set flags' */
 356     u_short parent_nr;          /* parent pipe#, 0 if local to a pipe */
 357
 358     int weight;                 /* WFQ queue weight */
 359     int qsize;                  /* queue size in slots or bytes */
 360     int plr;                    /* pkt loss rate (2^31-1 means 100%) */
 361
 362     /* Hash table information */
 363     int rq_size;                /* number of slots */
 364     int rq_elements;            /* active elements */
 365
 366     /* RED parameters */
 367     int w_q;                    /* queue weight (scaled) */
 368     int max_th;                 /* maximum threshold for queue (scaled) */
 369     int min_th;                 /* minimum threshold for queue (scaled) */
 370     int max_p;                  /* maximum value for p_b (scaled) */
 371     int lookup_step;            /* granularity inside the lookup table */
 372     int lookup_weight;          /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 373
 374     struct dn_ioc_flowid flow_mask;
 375     uint8_t reserved[16];
 376 };
 377
 378 struct dn_ioc_pipe {
 379     struct dn_ioc_flowset fs;   /* MUST be first */
 380
 381     int pipe_nr;                /* pipe number */
 382     int bandwidth;              /* bit/second */
 383     int delay;                  /* milliseconds */
 384
 385     dn_key V;                   /* virtual time */
 386
 387     uint8_t reserved[16];
 388 };
 389
 390 /*
 391  * Flow set flags
 392  */
 393 #define DN_HAVE_FLOW_MASK       0x0001
 394 #define DN_IS_RED               0x0002
 395 #define DN_IS_GENTLE_RED        0x0004
 396 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 397 #define DN_NOERROR              0x0010  /* do not report ENOBUFS on drops */
 398 #define DN_IS_PIPE              0x4000
 399 #define DN_IS_QUEUE             0x8000
 400
 401 /*
 402  * Macros for RED
 403  */
 404 #define SCALE_RED               16
 405 #define SCALE(x)                ((x) << SCALE_RED)
 406 #define SCALE_VAL(x)            ((x) >> SCALE_RED)
 407 #define SCALE_MUL(x, y)         (((x) * (y)) >> SCALE_RED)
 408
 409 #endif /* !_IP_DUMMYNET_H */