bsd/netinet/ip_dummynet.h

   1 /*
   2  * Copyright (c) 2000-2013 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /*
  29  * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
  30  * Portions Copyright (c) 2000 Akamba Corp.
  31  * All rights reserved
  32  *
  33  * Redistribution and use in source and binary forms, with or without
  34  * modification, are permitted provided that the following conditions
  35  * are met:
  36  * 1. Redistributions of source code must retain the above copyright
  37  *    notice, this list of conditions and the following disclaimer.
  38  * 2. Redistributions in binary form must reproduce the above copyright
  39  *    notice, this list of conditions and the following disclaimer in the
  40  *    documentation and/or other materials provided with the distribution.
  41  *
  42  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  43  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  44  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  45  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  46  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  47  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  48  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  49  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  50  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  51  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  52  * SUCH DAMAGE.
  53  *
  54  * $FreeBSD: src/sys/netinet/ip_dummynet.h,v 1.32 2004/08/17 22:05:54 andre Exp $
  55  */
  56
  57 #ifndef _IP_DUMMYNET_H
  58 #define _IP_DUMMYNET_H
  59
  60 #include <sys/appleapiopts.h>
  61
  62 #ifdef PRIVATE
  63 #include <netinet/ip_flowid.h>
  64
  65 /* Apply ipv6 mask on ipv6 addr */
  66 #define APPLY_MASK(addr, mask)                          \
  67     (addr)->__u6_addr.__u6_addr32[0] &= (mask)->__u6_addr.__u6_addr32[0]; \
  68     (addr)->__u6_addr.__u6_addr32[1] &= (mask)->__u6_addr.__u6_addr32[1]; \
  69     (addr)->__u6_addr.__u6_addr32[2] &= (mask)->__u6_addr.__u6_addr32[2]; \
  70     (addr)->__u6_addr.__u6_addr32[3] &= (mask)->__u6_addr.__u6_addr32[3];
  71
  72 /*
  73  * Definition of dummynet data structures. In the structures, I decided
  74  * not to use the macros in <sys/queue.h> in the hope of making the code
  75  * easier to port to other architectures. The type of lists and queue we
  76  * use here is pretty simple anyways.
  77  */
  78
  79 /*
  80  * We start with a heap, which is used in the scheduler to decide when
  81  * to transmit packets etc.
  82  *
  83  * The key for the heap is used for two different values:
  84  *
  85  * 1. timer ticks- max 10K/second, so 32 bits are enough;
  86  *
  87  * 2. virtual times. These increase in steps of len/x, where len is the
  88  *    packet length, and x is either the weight of the flow, or the
  89  *    sum of all weights.
  90  *    If we limit to max 1000 flows and a max weight of 100, then
  91  *    x needs 17 bits. The packet size is 16 bits, so we can easily
  92  *    overflow if we do not allow errors.
  93  * So we use a key "dn_key" which is 64 bits. Some macros are used to
  94  * compare key values and handle wraparounds.
  95  * MAX64 returns the largest of two key values.
  96  * MY_M is used as a shift count when doing fixed point arithmetic
  97  * (a better name would be useful...).
  98  */
  99 typedef u_int64_t dn_key;       /* sorting key */
 100 #define DN_KEY_LT(a, b)     ((int64_t)((a)-(b)) < 0)
 101 #define DN_KEY_LEQ(a, b)    ((int64_t)((a)-(b)) <= 0)
 102 #define DN_KEY_GT(a, b)     ((int64_t)((a)-(b)) > 0)
 103 #define DN_KEY_GEQ(a, b)    ((int64_t)((a)-(b)) >= 0)
 104 #define MAX64(x, y)  (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
 105 #define MY_M    16 /* number of left shift to obtain a larger precision */
 106
 107 /*
 108  * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
 109  * virtual time wraps every 15 days.
 110  */
 111
 112 /*
 113  * The maximum hash table size for queues.  This value must be a power
 114  * of 2.
 115  */
 116 #define DN_MAX_HASH_SIZE 65536
 117
 118 /*
 119  * A heap entry is made of a key and a pointer to the actual
 120  * object stored in the heap.
 121  * The heap is an array of dn_heap_entry entries, dynamically allocated.
 122  * Current size is "size", with "elements" actually in use.
 123  * The heap normally supports only ordered insert and extract from the top.
 124  * If we want to extract an object from the middle of the heap, we
 125  * have to know where the object itself is located in the heap (or we
 126  * need to scan the whole array). To this purpose, an object has a
 127  * field (int) which contains the index of the object itself into the
 128  * heap. When the object is moved, the field must also be updated.
 129  * The offset of the index in the object is stored in the 'offset'
 130  * field in the heap descriptor. The assumption is that this offset
 131  * is non-zero if we want to support extract from the middle.
 132  */
 133 struct dn_heap_entry {
 134         dn_key key;     /* sorting key. Topmost element is smallest one */
 135         void *object;   /* object pointer */
 136 };
 137
 138 struct dn_heap {
 139         int size;
 140         int elements;
 141         int offset; /* XXX if > 0 this is the offset of direct ptr to obj */
 142         struct dn_heap_entry *p; /* really an array of "size" entries */
 143 };
 144
 145 /*
 146  * Packets processed by dummynet have an mbuf tag associated with
 147  * them that carries their dummynet state.  This is used within
 148  * the dummynet code as well as outside when checking for special
 149  * processing requirements.
 150  */
 151 #ifdef KERNEL
 152 #include <net/if_var.h>
 153 #include <net/route.h>
 154 #include <netinet/ip_var.h>     /* for ip_out_args */
 155 #include <netinet/ip6.h>        /* for ip6_out_args */
 156 #include <netinet/in.h>
 157 #include <netinet6/ip6_var.h>   /* for ip6_out_args */
 158
 159 struct dn_pkt_tag {
 160         struct ip_fw        *dn_ipfw_rule;      /* matching IPFW rule */
 161         void                *dn_pf_rule;        /* matching PF rule */
 162         int                 dn_dir;             /* action when packet comes out. */
 163 #define DN_TO_IP_OUT    1
 164 #define DN_TO_IP_IN     2
 165 #define DN_TO_BDG_FWD   3
 166 #define DN_TO_IP6_IN    4
 167 #define DN_TO_IP6_OUT   5
 168         dn_key              dn_output_time;     /* when the pkt is due for delivery     */
 169         struct ifnet        *dn_ifp;            /* interface, for ip[6]_output          */
 170         union {
 171                 struct sockaddr_in      _dn_dst;
 172                 struct sockaddr_in6     _dn_dst6;
 173         }                   dn_dst_;
 174 #define dn_dst dn_dst_._dn_dst
 175 #define dn_dst6 dn_dst_._dn_dst6
 176         union {
 177                 struct route            _dn_ro; /* route, for ip_output. MUST COPY      */
 178                 struct route_in6        _dn_ro6;/* route, for ip6_output. MUST COPY     */
 179         }               dn_ro_;
 180 #define dn_ro dn_ro_._dn_ro
 181 #define dn_ro6 dn_ro_._dn_ro6
 182         struct route_in6    dn_ro6_pmtu;        /* for ip6_output */
 183         struct ifnet        *dn_origifp;        /* for ip6_output */
 184         u_int32_t           dn_mtu;             /* for ip6_output */
 185         u_int32_t           dn_unfragpartlen;   /* for ip6_output */
 186         struct ip6_exthdrs  dn_exthdrs;         /* for ip6_output */
 187         int                 dn_flags;           /* flags, for ip[6]_output */
 188         int                 dn_client;
 189 #define DN_CLIENT_IPFW  1
 190 #define DN_CLIENT_PF    2
 191         union {
 192                 struct ip_out_args      _dn_ipoa;/* output args, for ip_output. MUST COPY */
 193                 struct ip6_out_args     _dn_ip6oa;/* output args, for ip_output. MUST COPY */
 194         }                   dn_ipoa_;
 195 #define dn_ipoa dn_ipoa_._dn_ipoa
 196 #define dn_ip6oa dn_ipoa_._dn_ip6oa
 197 };
 198 #else
 199 struct dn_pkt;
 200 #endif /* KERNEL */
 201
 202 /*
 203  * Overall structure of dummynet (with WF2Q+):
 204  *
 205  *  In dummynet, packets are selected with the firewall rules, and passed
 206  *  to two different objects: PIPE or QUEUE.
 207  *
 208  *  A QUEUE is just a queue with configurable size and queue management
 209  *  policy. It is also associated with a mask (to discriminate among
 210  *  different flows), a weight (used to give different shares of the
 211  *  bandwidth to different flows) and a "pipe", which essentially
 212  *  supplies the transmit clock for all queues associated with that
 213  *  pipe.
 214  *
 215  *  A PIPE emulates a fixed-bandwidth link, whose bandwidth is
 216  *  configurable.  The "clock" for a pipe can come from either an
 217  *  internal timer, or from the transmit interrupt of an interface.
 218  *  A pipe is also associated with one (or more, if masks are used)
 219  *  queue, where all packets for that pipe are stored.
 220  *
 221  *  The bandwidth available on the pipe is shared by the queues
 222  *  associated with that pipe (only one in case the packet is sent
 223  *  to a PIPE) according to the WF2Q+ scheduling algorithm and the
 224  *  configured weights.
 225  *
 226  *  In general, incoming packets are stored in the appropriate queue,
 227  *  which is then placed into one of a few heaps managed by a scheduler
 228  *  to decide when the packet should be extracted.
 229  *  The scheduler (a function called dummynet()) is run at every timer
 230  *  tick, and grabs queues from the head of the heaps when they are
 231  *  ready for processing.
 232  *
 233  *  There are three data structures definining a pipe and associated queues:
 234  *
 235  + dn_pipe, which contains the main configuration parameters related
 236  +  to delay and bandwidth;
 237  + dn_flow_set, which contains WF2Q+ configuration, flow
 238  +  masks, plr and RED configuration;
 239  + dn_flow_queue, which is the per-flow queue (containing the packets)
 240  +
 241  +  Multiple dn_flow_set can be linked to the same pipe, and multiple
 242  +  dn_flow_queue can be linked to the same dn_flow_set.
 243  +  All data structures are linked in a linear list which is used for
 244  +  housekeeping purposes.
 245  +
 246  +  During configuration, we create and initialize the dn_flow_set
 247  +  and dn_pipe structures (a dn_pipe also contains a dn_flow_set).
 248  +
 249  +  At runtime: packets are sent to the appropriate dn_flow_set (either
 250  +  WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows),
 251  +  which in turn dispatches them to the appropriate dn_flow_queue
 252  +  (created dynamically according to the masks).
 253  +
 254  +  The transmit clock for fixed rate flows (ready_event()) selects the
 255  +  dn_flow_queue to be used to transmit the next packet. For WF2Q,
 256  +  wfq_ready_event() extract a pipe which in turn selects the right
 257  +  flow using a number of heaps defined into the pipe itself.
 258  +
 259  *
 260  */
 261
 262 /*
 263  * per flow queue. This contains the flow identifier, the queue
 264  * of packets, counters, and parameters used to support both RED and
 265  * WF2Q+.
 266  *
 267  * A dn_flow_queue is created and initialized whenever a packet for
 268  * a new flow arrives.
 269  */
 270 struct dn_flow_queue {
 271         struct dn_flow_queue *next;
 272         struct ip_flow_id id;
 273
 274         struct mbuf *head, *tail; /* queue of packets */
 275         u_int len;
 276         u_int len_bytes;
 277         u_int32_t numbytes;             /* credit for transmission (dynamic queues) */
 278
 279         u_int64_t tot_pkts;     /* statistics counters  */
 280         u_int64_t tot_bytes;
 281         u_int32_t drops;
 282
 283         int hash_slot;          /* debugging/diagnostic */
 284
 285         /* RED parameters */
 286         int avg;                /* average queue length est. (scaled) */
 287         int count;              /* arrivals since last RED drop */
 288         int random;             /* random value (scaled) */
 289         u_int32_t q_time;       /* start of queue idle time */
 290
 291         /* WF2Q+ support */
 292         struct dn_flow_set *fs; /* parent flow set */
 293         int heap_pos;           /* position (index) of struct in heap */
 294         dn_key sched_time;      /* current time when queue enters ready_heap */
 295
 296         dn_key S, F;            /* start time, finish time */
 297         /*
 298          * Setting F < S means the timestamp is invalid. We only need
 299          * to test this when the queue is empty.
 300          */
 301 };
 302
 303 /*
 304  * flow_set descriptor. Contains the "template" parameters for the
 305  * queue configuration, and pointers to the hash table of dn_flow_queue's.
 306  *
 307  * The hash table is an array of lists -- we identify the slot by
 308  * hashing the flow-id, then scan the list looking for a match.
 309  * The size of the hash table (buckets) is configurable on a per-queue
 310  * basis.
 311  *
 312  * A dn_flow_set is created whenever a new queue or pipe is created (in the
 313  * latter case, the structure is located inside the struct dn_pipe).
 314  */
 315 struct dn_flow_set {
 316         SLIST_ENTRY(dn_flow_set)    next;/* linked list in a hash slot */
 317
 318         u_short fs_nr;          /* flow_set number       */
 319         u_short flags_fs;
 320 #define DN_HAVE_FLOW_MASK       0x0001
 321 #define DN_IS_RED               0x0002
 322 #define DN_IS_GENTLE_RED        0x0004
 323 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 324 #define DN_NOERROR              0x0010  /* do not report ENOBUFS on drops  */
 325 #define DN_IS_PIPE              0x4000
 326 #define DN_IS_QUEUE             0x8000
 327
 328         struct dn_pipe *pipe;   /* pointer to parent pipe */
 329         u_short parent_nr;      /* parent pipe#, 0 if local to a pipe */
 330
 331         int weight;             /* WFQ queue weight */
 332         int qsize;              /* queue size in slots or bytes */
 333         int plr;                /* pkt loss rate (2^31-1 means 100%) */
 334
 335         struct ip_flow_id flow_mask;
 336
 337         /* hash table of queues onto this flow_set */
 338         int rq_size;            /* number of slots */
 339         int rq_elements;        /* active elements */
 340         struct dn_flow_queue **rq; /* array of rq_size entries */
 341
 342         u_int32_t last_expired; /* do not expire too frequently */
 343         int backlogged;         /* #active queues for this flowset */
 344
 345         /* RED parameters */
 346 #define SCALE_RED               16
 347 #define SCALE(x)                ( (x) << SCALE_RED )
 348 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 349 #define SCALE_MUL(x, y)          ( ( (x) * (y) ) >> SCALE_RED )
 350         int w_q;                /* queue weight (scaled) */
 351         int max_th;             /* maximum threshold for queue (scaled) */
 352         int min_th;             /* minimum threshold for queue (scaled) */
 353         int max_p;              /* maximum value for p_b (scaled) */
 354         u_int c_1;              /* max_p/(max_th-min_th) (scaled) */
 355         u_int c_2;              /* max_p*min_th/(max_th-min_th) (scaled) */
 356         u_int c_3;              /* for GRED, (1-max_p)/max_th (scaled) */
 357         u_int c_4;              /* for GRED, 1 - 2*max_p (scaled) */
 358         u_int * w_q_lookup;     /* lookup table for computing (1-w_q)^t */
 359         u_int lookup_depth;     /* depth of lookup table */
 360         int lookup_step;        /* granularity inside the lookup table */
 361         int lookup_weight;      /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 362         int avg_pkt_size;       /* medium packet size */
 363         int max_pkt_size;       /* max packet size */
 364 };
 365
 366 SLIST_HEAD(dn_flow_set_head, dn_flow_set);
 367
 368 /*
 369  * Pipe descriptor. Contains global parameters, delay-line queue,
 370  * and the flow_set used for fixed-rate queues.
 371  *
 372  * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
 373  *   not_eligible_heap, for queues whose start time is higher
 374  *      than the virtual time. Sorted by start time.
 375  *   scheduler_heap, for queues eligible for scheduling. Sorted by
 376  *      finish time.
 377  *   idle_heap, all flows that are idle and can be removed. We
 378  *      do that on each tick so we do not slow down too much
 379  *      operations during forwarding.
 380  *
 381  */
 382 struct dn_pipe {                /* a pipe */
 383         SLIST_ENTRY(dn_pipe)        next;/* linked list in a hash slot */
 384
 385         int pipe_nr;            /* number       */
 386         int bandwidth;          /* really, bytes/tick.  */
 387         int delay;              /* really, ticks        */
 388
 389         struct      mbuf *head, *tail;  /* packets in delay line */
 390
 391         /* WF2Q+ */
 392         struct dn_heap scheduler_heap; /* top extract - key Finish time*/
 393         struct dn_heap not_eligible_heap; /* top extract- key Start time */
 394         struct dn_heap idle_heap; /* random extract - key Start=Finish time */
 395
 396         dn_key V;               /* virtual time */
 397         int sum;                /* sum of weights of all active sessions */
 398         int numbytes;           /* bits I can transmit (more or less). */
 399
 400         dn_key sched_time;      /* time pipe was scheduled in ready_heap */
 401
 402         /*
 403          * When the tx clock come from an interface (if_name[0] != '\0'), its name
 404          * is stored below, whereas the ifp is filled when the rule is configured.
 405          */
 406         char if_name[IFNAMSIZ];
 407         struct ifnet *ifp;
 408         int ready; /* set if ifp != NULL and we got a signal from it */
 409
 410         struct dn_flow_set fs; /* used with fixed-rate flows */
 411 };
 412
 413 SLIST_HEAD(dn_pipe_head, dn_pipe);
 414
 415 #ifdef BSD_KERNEL_PRIVATE
 416 extern uint32_t my_random(void);
 417 void ip_dn_init(void); /* called from raw_ip.c:load_ipfw() */
 418
 419 typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */
 420 typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir,
 421     struct ip_fw_args *fwa, int );
 422 extern  ip_dn_ctl_t *ip_dn_ctl_ptr;
 423 extern  ip_dn_io_t *ip_dn_io_ptr;
 424 void dn_ipfw_rule_delete(void *);
 425 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
 426
 427 #pragma pack(4)
 428
 429 struct dn_heap_32 {
 430         int size;
 431         int elements;
 432         int offset; /* XXX if > 0 this is the offset of direct ptr to obj */
 433         user32_addr_t p; /* really an array of "size" entries */
 434 };
 435
 436 struct dn_flow_queue_32 {
 437         user32_addr_t next;
 438         struct ip_flow_id id;
 439
 440         user32_addr_t head, tail; /* queue of packets */
 441         u_int len;
 442         u_int len_bytes;
 443         u_int32_t numbytes;     /* credit for transmission (dynamic queues) */
 444
 445         u_int64_t tot_pkts;     /* statistics counters  */
 446         u_int64_t tot_bytes;
 447         u_int32_t drops;
 448
 449         int hash_slot;                  /* debugging/diagnostic */
 450
 451         /* RED parameters */
 452         int avg;                /* average queue length est. (scaled) */
 453         int count;              /* arrivals since last RED drop */
 454         int random;             /* random value (scaled) */
 455         u_int32_t q_time;       /* start of queue idle time */
 456
 457         /* WF2Q+ support */
 458         user32_addr_t fs; /* parent flow set */
 459         int heap_pos;           /* position (index) of struct in heap */
 460         dn_key sched_time;      /* current time when queue enters ready_heap */
 461
 462         dn_key S, F;            /* start time, finish time */
 463         /*
 464          * Setting F < S means the timestamp is invalid. We only need
 465          * to test this when the queue is empty.
 466          */
 467 };
 468
 469 struct dn_flow_set_32 {
 470         user32_addr_t       next;/* next flow set in all_flow_sets list */
 471
 472         u_short fs_nr;                  /* flow_set number       */
 473         u_short flags_fs;
 474 #define DN_HAVE_FLOW_MASK       0x0001
 475 #define DN_IS_RED               0x0002
 476 #define DN_IS_GENTLE_RED        0x0004
 477 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 478 #define DN_NOERROR              0x0010          /* do not report ENOBUFS on drops  */
 479 #define DN_IS_PIPE              0x4000
 480 #define DN_IS_QUEUE             0x8000
 481
 482         user32_addr_t pipe;     /* pointer to parent pipe */
 483         u_short parent_nr;      /* parent pipe#, 0 if local to a pipe */
 484
 485         int weight;             /* WFQ queue weight */
 486         int qsize;              /* queue size in slots or bytes */
 487         int plr;                /* pkt loss rate (2^31-1 means 100%) */
 488
 489         struct ip_flow_id flow_mask;
 490
 491         /* hash table of queues onto this flow_set */
 492         int rq_size;            /* number of slots */
 493         int rq_elements; /* active elements */
 494         user32_addr_t rq; /* array of rq_size entries */
 495
 496         u_int32_t last_expired; /* do not expire too frequently */
 497         int backlogged;                 /* #active queues for this flowset */
 498
 499         /* RED parameters */
 500 #define SCALE_RED               16
 501 #define SCALE(x)                ( (x) << SCALE_RED )
 502 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 503 #define SCALE_MUL(x, y)          ( ( (x) * (y) ) >> SCALE_RED )
 504         int w_q;                /* queue weight (scaled) */
 505         int max_th;             /* maximum threshold for queue (scaled) */
 506         int min_th;             /* minimum threshold for queue (scaled) */
 507         int max_p;              /* maximum value for p_b (scaled) */
 508         u_int c_1;              /* max_p/(max_th-min_th) (scaled) */
 509         u_int c_2;              /* max_p*min_th/(max_th-min_th) (scaled) */
 510         u_int c_3;              /* for GRED, (1-max_p)/max_th (scaled) */
 511         u_int c_4;              /* for GRED, 1 - 2*max_p (scaled) */
 512         user32_addr_t w_q_lookup; /* lookup table for computing (1-w_q)^t */
 513         u_int lookup_depth;     /* depth of lookup table */
 514         int lookup_step;        /* granularity inside the lookup table */
 515         int lookup_weight;      /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 516         int avg_pkt_size;       /* medium packet size */
 517         int max_pkt_size;       /* max packet size */
 518 };
 519
 520 struct dn_pipe_32 {             /* a pipe */
 521         user32_addr_t       next;
 522
 523         int pipe_nr;            /* number       */
 524         int bandwidth;          /* really, bytes/tick.  */
 525         int delay;              /* really, ticks        */
 526
 527         user32_addr_t head, tail; /* packets in delay line */
 528
 529         /* WF2Q+ */
 530         struct dn_heap_32 scheduler_heap; /* top extract - key Finish time*/
 531         struct dn_heap_32 not_eligible_heap; /* top extract- key Start time */
 532         struct dn_heap_32 idle_heap; /* random extract - key Start=Finish time */
 533
 534         dn_key V;               /* virtual time */
 535         int sum;                /* sum of weights of all active sessions */
 536         int numbytes;           /* bits I can transmit (more or less). */
 537
 538         dn_key sched_time; /* time pipe was scheduled in ready_heap */
 539
 540         /*
 541          * When the tx clock come from an interface (if_name[0] != '\0'), its name
 542          * is stored below, whereas the ifp is filled when the rule is configured.
 543          */
 544         char if_name[IFNAMSIZ];
 545         user32_addr_t ifp;
 546         int ready;              /* set if ifp != NULL and we got a signal from it */
 547
 548         struct dn_flow_set_32 fs; /* used with fixed-rate flows */
 549 };
 550 #pragma pack()
 551
 552
 553 struct dn_heap_64 {
 554         int size;
 555         int elements;
 556         int offset; /* XXX if > 0 this is the offset of direct ptr to obj */
 557         user64_addr_t p; /* really an array of "size" entries */
 558 };
 559
 560
 561 struct dn_flow_queue_64 {
 562         user64_addr_t next;
 563         struct ip_flow_id id;
 564
 565         user64_addr_t head, tail; /* queue of packets */
 566         u_int len;
 567         u_int len_bytes;
 568         u_int32_t numbytes;             /* credit for transmission (dynamic queues) */
 569
 570         u_int64_t tot_pkts;             /* statistics counters  */
 571         u_int64_t tot_bytes;
 572         u_int32_t drops;
 573
 574         int hash_slot;                          /* debugging/diagnostic */
 575
 576         /* RED parameters */
 577         int avg;                /* average queue length est. (scaled) */
 578         int count;              /* arrivals since last RED drop */
 579         int random;             /* random value (scaled) */
 580         u_int32_t q_time;       /* start of queue idle time */
 581
 582         /* WF2Q+ support */
 583         user64_addr_t fs;               /* parent flow set */
 584         int heap_pos;                           /* position (index) of struct in heap */
 585         dn_key sched_time;              /* current time when queue enters ready_heap */
 586
 587         dn_key S, F;                            /* start time, finish time */
 588         /*
 589          * Setting F < S means the timestamp is invalid. We only need
 590          * to test this when the queue is empty.
 591          */
 592 };
 593
 594 struct dn_flow_set_64 {
 595         user64_addr_t next;             /* next flow set in all_flow_sets list */
 596
 597         u_short fs_nr;          /* flow_set number       */
 598         u_short flags_fs;
 599 #define DN_HAVE_FLOW_MASK       0x0001
 600 #define DN_IS_RED               0x0002
 601 #define DN_IS_GENTLE_RED        0x0004
 602 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 603 #define DN_NOERROR              0x0010          /* do not report ENOBUFS on drops  */
 604 #define DN_IS_PIPE              0x4000
 605 #define DN_IS_QUEUE             0x8000
 606
 607         user64_addr_t pipe;     /* pointer to parent pipe */
 608         u_short parent_nr;      /* parent pipe#, 0 if local to a pipe */
 609
 610         int weight;             /* WFQ queue weight */
 611         int qsize;              /* queue size in slots or bytes */
 612         int plr;                /* pkt loss rate (2^31-1 means 100%) */
 613
 614         struct ip_flow_id flow_mask;
 615
 616         /* hash table of queues onto this flow_set */
 617         int rq_size;            /* number of slots */
 618         int rq_elements; /* active elements */
 619         user64_addr_t rq; /* array of rq_size entries */
 620
 621         u_int32_t last_expired; /* do not expire too frequently */
 622         int backlogged;                 /* #active queues for this flowset */
 623
 624         /* RED parameters */
 625 #define SCALE_RED               16
 626 #define SCALE(x)                ( (x) << SCALE_RED )
 627 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 628 #define SCALE_MUL(x, y)          ( ( (x) * (y) ) >> SCALE_RED )
 629         int w_q;                /* queue weight (scaled) */
 630         int max_th;             /* maximum threshold for queue (scaled) */
 631         int min_th;             /* minimum threshold for queue (scaled) */
 632         int max_p;              /* maximum value for p_b (scaled) */
 633         u_int c_1;              /* max_p/(max_th-min_th) (scaled) */
 634         u_int c_2;              /* max_p*min_th/(max_th-min_th) (scaled) */
 635         u_int c_3;              /* for GRED, (1-max_p)/max_th (scaled) */
 636         u_int c_4;              /* for GRED, 1 - 2*max_p (scaled) */
 637         user64_addr_t w_q_lookup; /* lookup table for computing (1-w_q)^t */
 638         u_int lookup_depth;     /* depth of lookup table */
 639         int lookup_step;        /* granularity inside the lookup table */
 640         int lookup_weight;      /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 641         int avg_pkt_size;       /* medium packet size */
 642         int max_pkt_size;       /* max packet size */
 643 };
 644
 645 struct dn_pipe_64 {             /* a pipe */
 646         user64_addr_t       next;
 647
 648         int pipe_nr;            /* number       */
 649         int bandwidth;          /* really, bytes/tick.  */
 650         int delay;              /* really, ticks        */
 651
 652         user64_addr_t head, tail; /* packets in delay line */
 653
 654         /* WF2Q+ */
 655         struct dn_heap_64 scheduler_heap;       /* top extract - key Finish time*/
 656         struct dn_heap_64 not_eligible_heap;    /* top extract- key Start time */
 657         struct dn_heap_64 idle_heap;                    /* random extract - key Start=Finish time */
 658
 659         dn_key V;               /* virtual time */
 660         int sum;                /* sum of weights of all active sessions */
 661         int numbytes;           /* bits I can transmit (more or less). */
 662
 663         dn_key sched_time; /* time pipe was scheduled in ready_heap */
 664
 665         /*
 666          * When the tx clock come from an interface (if_name[0] != '\0'), its name
 667          * is stored below, whereas the ifp is filled when the rule is configured.
 668          */
 669         char if_name[IFNAMSIZ];
 670         user64_addr_t ifp;
 671         int ready; /* set if ifp != NULL and we got a signal from it */
 672
 673         struct dn_flow_set_64 fs; /* used with fixed-rate flows */
 674 };
 675
 676 /*
 677  * Return the IPFW rule associated with the dummynet tag; if any.
 678  * Make sure that the dummynet tag is not reused by lower layers.
 679  */
 680 static __inline struct ip_fw *
 681 ip_dn_claim_rule(struct mbuf *m)
 682 {
 683         struct m_tag *mtag = m_tag_locate(m, KERNEL_MODULE_TAG_ID,
 684             KERNEL_TAG_TYPE_DUMMYNET, NULL);
 685         if (mtag != NULL) {
 686                 mtag->m_tag_type = KERNEL_TAG_TYPE_NONE;
 687                 return ((struct dn_pkt_tag *)(mtag + 1))->dn_ipfw_rule;
 688         } else {
 689                 return NULL;
 690         }
 691 }
 692
 693 #include <sys/eventhandler.h>
 694 /* Dummynet event handling declarations */
 695 extern struct eventhandler_lists_ctxt dummynet_evhdlr_ctxt;
 696 extern void dummynet_init(void);
 697
 698 struct dn_pipe_mini_config {
 699         uint32_t bandwidth;
 700         uint32_t delay;
 701         uint32_t plr;
 702 };
 703
 704 struct dn_rule_mini_config {
 705         uint32_t dir;
 706         uint32_t af;
 707         uint32_t proto;
 708         /*
 709          * XXX PF rules actually define ranges of ports and
 710          * along with range goes an opcode ((not) equal to, less than
 711          * greater than, etc.
 712          * For now the following works assuming there's no port range
 713          * and the rule is for specific port.
 714          * Also the operation is assumed as equal to.
 715          */
 716         uint32_t src_port;
 717         uint32_t dst_port;
 718         char ifname[IFXNAMSIZ];
 719 };
 720
 721 struct dummynet_event {
 722         uint32_t dn_event_code;
 723         union {
 724                 struct dn_pipe_mini_config _dnev_pipe_config;
 725                 struct dn_rule_mini_config _dnev_rule_config;
 726         } dn_event;
 727 };
 728
 729 #define dn_event_pipe_config    dn_event._dnev_pipe_config
 730 #define dn_event_rule_config    dn_event._dnev_rule_config
 731
 732 extern void dummynet_event_enqueue_nwk_wq_entry(struct dummynet_event *);
 733
 734 enum {
 735         DUMMYNET_RULE_CONFIG,
 736         DUMMYNET_RULE_DELETE,
 737         DUMMYNET_PIPE_CONFIG,
 738         DUMMYNET_PIPE_DELETE,
 739         DUMMYNET_NLC_DISABLED,
 740 };
 741
 742 enum    { DN_INOUT, DN_IN, DN_OUT };
 743 /*
 744  * The signature for the callback is:
 745  * eventhandler_entry_arg       __unused
 746  * dummynet_event               pointer to dummynet event object
 747  */
 748 typedef void (*dummynet_event_fn) (struct eventhandler_entry_arg, struct dummynet_event *);
 749 EVENTHANDLER_DECLARE(dummynet_event, dummynet_event_fn);
 750 #endif /* BSD_KERNEL_PRIVATE */
 751 #endif /* PRIVATE */
 752 #endif /* _IP_DUMMYNET_H */