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.11 2007/11/03 13:14:29 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
  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 uint64_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 maximum/minimum hash table size for queues.
  76  * These values must be a power of 2.
  77  */
  78 #define DN_MIN_HASH_SIZE        4
  79 #define DN_MAX_HASH_SIZE        65536
  80
  81 /*
  82  * A heap entry is made of a key and a pointer to the actual
  83  * object stored in the heap.
  84  * The heap is an array of dn_heap_entry entries, dynamically allocated.
  85  * Current size is "size", with "elements" actually in use.
  86  * The heap normally supports only ordered insert and extract from the top.
  87  * If we want to extract an object from the middle of the heap, we
  88  * have to know where the object itself is located in the heap (or we
  89  * need to scan the whole array). To this purpose, an object has a
  90  * field (int) which contains the index of the object itself into the
  91  * heap. When the object is moved, the field must also be updated.
  92  * The offset of the index in the object is stored in the 'offset'
  93  * field in the heap descriptor. The assumption is that this offset
  94  * is non-zero if we want to support extract from the middle.
  95  */
  96 struct dn_heap_entry {
  97     dn_key key;         /* sorting key. Topmost element is smallest one */
  98     void *object;       /* object pointer */
  99 };
 100
 101 struct dn_heap {
 102     int size;
 103     int elements;
 104     int offset; /* XXX if > 0 this is the offset of direct ptr to obj */
 105     struct dn_heap_entry *p;    /* really an array of "size" entries */
 106 };
 107
 108 #ifdef _KERNEL
 109
 110 /*
 111  * struct dn_pkt identifies a packet in the dummynet queue, but
 112  * is also used to tag packets passed back to the various destinations
 113  * (ip_input(), ip_output()  and so on).
 114  * It is a tag(PACKET_TAG_DUMMYNET) associated with the actual mbuf.
 115  */
 116 struct dn_pkt {
 117     struct mbuf *dn_m;
 118     struct dn_pkt *dn_next;
 119
 120     struct ip_fw *rule;         /* matching rule */
 121     int dn_dir;                 /* action when packet comes out. */
 122 #define DN_TO_IP_OUT    1
 123 #define DN_TO_IP_IN     2
 124 #define DN_TO_ETH_DEMUX 4
 125 #define DN_TO_ETH_OUT   5
 126
 127     dn_key output_time;         /* when the pkt is due for delivery */
 128     struct ifnet *ifp;          /* interface, for ip_output */
 129     struct sockaddr_in *dn_dst;
 130     struct route ro;            /* route, for ip_output. MUST COPY */
 131     int flags;                  /* flags, for ip_output (IPv6 ?) */
 132 };
 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  * per flow queue. This contains the flow identifier, the queue
 194  * of packets, counters, and parameters used to support both RED and
 195  * WF2Q+.
 196  *
 197  * A dn_flow_queue is created and initialized whenever a packet for
 198  * a new flow arrives.
 199  */
 200 struct dn_flow_queue {
 201     struct dn_flow_queue *next;
 202     struct ipfw_flow_id id;
 203
 204     struct dn_pkt *head, *tail; /* queue of packets */
 205     u_int len;
 206     u_int len_bytes;
 207     u_long numbytes;            /* credit for transmission (dynamic queues) */
 208
 209     uint64_t tot_pkts;          /* statistics counters */
 210     uint64_t tot_bytes;
 211     uint32_t drops;
 212
 213     int hash_slot;              /* debugging/diagnostic */
 214
 215     /* RED parameters */
 216     int avg;                    /* average queue length est. (scaled) */
 217     int count;                  /* arrivals since last RED drop */
 218     int random;                 /* random value (scaled) */
 219     uint32_t q_time;            /* start of queue idle time */
 220
 221     /* WF2Q+ support */
 222     struct dn_flow_set *fs;     /* parent flow set */
 223     int heap_pos;               /* position (index) of struct in heap */
 224     dn_key sched_time;          /* current time when queue enters ready_heap */
 225
 226     dn_key S, F;                /* start time, finish time */
 227     /*
 228      * Setting F < S means the timestamp is invalid. We only need
 229      * to test this when the queue is empty.
 230      */
 231 };
 232
 233 /*
 234  * flow_set descriptor. Contains the "template" parameters for the
 235  * queue configuration, and pointers to the hash table of dn_flow_queue's.
 236  *
 237  * The hash table is an array of lists -- we identify the slot by
 238  * hashing the flow-id, then scan the list looking for a match.
 239  * The size of the hash table (buckets) is configurable on a per-queue
 240  * basis.
 241  *
 242  * A dn_flow_set is created whenever a new queue or pipe is created (in the
 243  * latter case, the structure is located inside the struct dn_pipe).
 244  */
 245 struct dn_flow_set {
 246     struct dn_flow_set *next;   /* next flow set in all_flow_sets list */
 247
 248     u_short fs_nr;              /* flow_set number */
 249     u_short flags_fs;           /* see 'Flow set flags' */
 250
 251     struct dn_pipe *pipe;       /* pointer to parent pipe */
 252     u_short parent_nr;          /* parent pipe#, 0 if local to a pipe */
 253
 254     int weight;                 /* WFQ queue weight */
 255     int qsize;                  /* queue size in slots or bytes */
 256     int plr;                    /* pkt loss rate (2^31-1 means 100%) */
 257
 258     struct ipfw_flow_id flow_mask;
 259
 260     /* hash table of queues onto this flow_set */
 261     int rq_size;                /* number of slots */
 262     int rq_elements;            /* active elements */
 263     struct dn_flow_queue **rq;  /* array of rq_size entries */
 264
 265     uint32_t last_expired;      /* do not expire too frequently */
 266     int backlogged;             /* #active queues for this flowset */
 267
 268     /* RED parameters */
 269     int w_q;                    /* queue weight (scaled) */
 270     int max_th;                 /* maximum threshold for queue (scaled) */
 271     int min_th;                 /* minimum threshold for queue (scaled) */
 272     int max_p;                  /* maximum value for p_b (scaled) */
 273     u_int c_1;                  /* max_p/(max_th-min_th) (scaled) */
 274     u_int c_2;                  /* max_p*min_th/(max_th-min_th) (scaled) */
 275     u_int c_3;                  /* for GRED, (1-max_p)/max_th (scaled) */
 276     u_int c_4;                  /* for GRED, 1 - 2*max_p (scaled) */
 277     u_int *w_q_lookup;          /* lookup table for computing (1-w_q)^t */
 278     u_int lookup_depth;         /* depth of lookup table */
 279     int lookup_step;            /* granularity inside the lookup table */
 280     int lookup_weight;          /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 281     int avg_pkt_size;           /* medium packet size */
 282     int max_pkt_size;           /* max packet size */
 283 };
 284
 285 /*
 286  * Pipe descriptor. Contains global parameters, delay-line queue,
 287  * and the flow_set used for fixed-rate queues.
 288  *
 289  * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
 290  *   not_eligible_heap, for queues whose start time is higher
 291  *      than the virtual time. Sorted by start time.
 292  *   scheduler_heap, for queues eligible for scheduling. Sorted by
 293  *      finish time.
 294  *   idle_heap, all flows that are idle and can be removed. We
 295  *      do that on each tick so we do not slow down too much
 296  *      operations during forwarding.
 297  *
 298  */
 299 struct dn_pipe {                /* a pipe */
 300     struct dn_pipe *next;
 301
 302     int pipe_nr;                /* number */
 303     int bandwidth;              /* really, bytes/tick. */
 304     int delay;                  /* really, ticks */
 305
 306     struct dn_pkt *head, *tail; /* packets in delay line */
 307
 308     /* WF2Q+ */
 309     struct dn_heap scheduler_heap; /* top extract - key Finish time*/
 310     struct dn_heap not_eligible_heap; /* top extract- key Start time */
 311     struct dn_heap idle_heap;   /* random extract - key Start=Finish time */
 312
 313     dn_key V;                   /* virtual time */
 314     int sum;                    /* sum of weights of all active sessions */
 315     int numbytes;               /* bits I can transmit (more or less). */
 316
 317     dn_key sched_time;          /* time pipe was scheduled in ready_heap */
 318
 319     struct dn_flow_set fs;      /* used with fixed-rate flows */
 320 };
 321
 322 typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */
 323 typedef void ip_dn_ruledel_t(void *); /* ip_fw2.c */
 324 typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir,
 325         struct ip_fw_args *fwa);
 326 extern  ip_dn_ctl_t *ip_dn_ctl_ptr;
 327 extern  ip_dn_ruledel_t *ip_dn_ruledel_ptr;
 328 extern  ip_dn_io_t *ip_dn_io_ptr;
 329 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
 330
 331 #endif  /* _KERNEL */
 332
 333 struct dn_ioc_flowid {
 334     uint16_t type;      /* ETHERTYPE_ */
 335     uint16_t pad;
 336     union {
 337         struct {
 338             uint32_t dst_ip;
 339             uint32_t src_ip;
 340             uint16_t dst_port;
 341             uint16_t src_port;
 342             uint8_t proto;
 343             uint8_t flags;
 344         } ip;
 345         uint8_t pad[64];
 346     } u;
 347 };
 348
 349 struct dn_ioc_flowqueue {
 350     u_int len;
 351     u_int len_bytes;
 352
 353     uint64_t tot_pkts;
 354     uint64_t tot_bytes;
 355     uint32_t drops;
 356
 357     int hash_slot;              /* debugging/diagnostic */
 358     dn_key S;                   /* virtual start time */
 359     dn_key F;                   /* virtual finish time */
 360
 361     struct dn_ioc_flowid id;
 362     uint8_t reserved[16];
 363 };
 364
 365 struct dn_ioc_flowset {
 366     u_short fs_type;            /* DN_IS_{QUEUE,PIPE}, MUST be first */
 367
 368     u_short fs_nr;              /* flow_set number */
 369     u_short flags_fs;           /* see 'Flow set flags' */
 370     u_short parent_nr;          /* parent pipe#, 0 if local to a pipe */
 371
 372     int weight;                 /* WFQ queue weight */
 373     int qsize;                  /* queue size in slots or bytes */
 374     int plr;                    /* pkt loss rate (2^31-1 means 100%) */
 375
 376     /* Hash table information */
 377     int rq_size;                /* number of slots */
 378     int rq_elements;            /* active elements */
 379
 380     /* RED parameters */
 381     int w_q;                    /* queue weight (scaled) */
 382     int max_th;                 /* maximum threshold for queue (scaled) */
 383     int min_th;                 /* minimum threshold for queue (scaled) */
 384     int max_p;                  /* maximum value for p_b (scaled) */
 385     int lookup_step;            /* granularity inside the lookup table */
 386     int lookup_weight;          /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 387
 388     struct dn_ioc_flowid flow_mask;
 389     uint8_t reserved[16];
 390 };
 391
 392 struct dn_ioc_pipe {
 393     struct dn_ioc_flowset fs;   /* MUST be first */
 394
 395     int pipe_nr;                /* pipe number */
 396     int bandwidth;              /* bit/second */
 397     int delay;                  /* milliseconds */
 398
 399     dn_key V;                   /* virtual time */
 400
 401     uint8_t reserved[16];
 402 };
 403
 404 /*
 405  * Flow set flags
 406  */
 407 #define DN_HAVE_FLOW_MASK       0x0001
 408 #define DN_IS_RED               0x0002
 409 #define DN_IS_GENTLE_RED        0x0004
 410 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 411 #define DN_NOERROR              0x0010  /* do not report ENOBUFS on drops */
 412 #define DN_IS_PIPE              0x4000
 413 #define DN_IS_QUEUE             0x8000
 414
 415 /*
 416  * Macros for RED
 417  */
 418 #define SCALE_RED               16
 419 #define SCALE(x)                ((x) << SCALE_RED)
 420 #define SCALE_VAL(x)            ((x) >> SCALE_RED)
 421 #define SCALE_MUL(x, y)         (((x) * (y)) >> SCALE_RED)
 422
 423 #endif /* !_IP_DUMMYNET_H */