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