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
  64 #include <netinet/ip_flowid.h>
  65
  66 /* Apply ipv6 mask on ipv6 addr */
  67 #define APPLY_MASK(addr,mask)                          \
  68     (addr)->__u6_addr.__u6_addr32[0] &= (mask)->__u6_addr.__u6_addr32[0]; \
  69     (addr)->__u6_addr.__u6_addr32[1] &= (mask)->__u6_addr.__u6_addr32[1]; \
  70     (addr)->__u6_addr.__u6_addr32[2] &= (mask)->__u6_addr.__u6_addr32[2]; \
  71     (addr)->__u6_addr.__u6_addr32[3] &= (mask)->__u6_addr.__u6_addr32[3];
  72
  73 /*
  74  * Definition of dummynet data structures. In the structures, I decided
  75  * not to use the macros in <sys/queue.h> in the hope of making the code
  76  * easier to port to other architectures. The type of lists and queue we
  77  * use here is pretty simple anyways.
  78  */
  79
  80 /*
  81  * We start with a heap, which is used in the scheduler to decide when
  82  * to transmit packets etc.
  83  *
  84  * The key for the heap is used for two different values:
  85  *
  86  * 1. timer ticks- max 10K/second, so 32 bits are enough;
  87  *
  88  * 2. virtual times. These increase in steps of len/x, where len is the
  89  *    packet length, and x is either the weight of the flow, or the
  90  *    sum of all weights.
  91  *    If we limit to max 1000 flows and a max weight of 100, then
  92  *    x needs 17 bits. The packet size is 16 bits, so we can easily
  93  *    overflow if we do not allow errors.
  94  * So we use a key "dn_key" which is 64 bits. Some macros are used to
  95  * compare key values and handle wraparounds.
  96  * MAX64 returns the largest of two key values.
  97  * MY_M is used as a shift count when doing fixed point arithmetic
  98  * (a better name would be useful...).
  99  */
 100 typedef u_int64_t dn_key ;      /* sorting key */
 101 #define DN_KEY_LT(a,b)     ((int64_t)((a)-(b)) < 0)
 102 #define DN_KEY_LEQ(a,b)    ((int64_t)((a)-(b)) <= 0)
 103 #define DN_KEY_GT(a,b)     ((int64_t)((a)-(b)) > 0)
 104 #define DN_KEY_GEQ(a,b)    ((int64_t)((a)-(b)) >= 0)
 105 #define MAX64(x,y)  (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
 106 #define MY_M    16 /* number of left shift to obtain a larger precision */
 107
 108 /*
 109  * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
 110  * virtual time wraps every 15 days.
 111  */
 112
 113 /*
 114  * The OFFSET_OF macro is used to return the offset of a field within
 115  * a structure. It is used by the heap management routines.
 116  */
 117 #define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) )
 118
 119 /*
 120  * The maximum hash table size for queues.  This value must be a power
 121  * of 2.
 122  */
 123 #define DN_MAX_HASH_SIZE 65536
 124
 125 /*
 126  * A heap entry is made of a key and a pointer to the actual
 127  * object stored in the heap.
 128  * The heap is an array of dn_heap_entry entries, dynamically allocated.
 129  * Current size is "size", with "elements" actually in use.
 130  * The heap normally supports only ordered insert and extract from the top.
 131  * If we want to extract an object from the middle of the heap, we
 132  * have to know where the object itself is located in the heap (or we
 133  * need to scan the whole array). To this purpose, an object has a
 134  * field (int) which contains the index of the object itself into the
 135  * heap. When the object is moved, the field must also be updated.
 136  * The offset of the index in the object is stored in the 'offset'
 137  * field in the heap descriptor. The assumption is that this offset
 138  * is non-zero if we want to support extract from the middle.
 139  */
 140 struct dn_heap_entry {
 141     dn_key key ;        /* sorting key. Topmost element is smallest one */
 142     void *object ;      /* object pointer */
 143 } ;
 144
 145 struct dn_heap {
 146     int size ;
 147     int elements ;
 148     int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */
 149     struct dn_heap_entry *p ;   /* really an array of "size" entries */
 150 } ;
 151
 152 /*
 153  * Packets processed by dummynet have an mbuf tag associated with
 154  * them that carries their dummynet state.  This is used within
 155  * the dummynet code as well as outside when checking for special
 156  * processing requirements.
 157  */
 158 #ifdef KERNEL
 159 #include <netinet/ip_var.h>     /* for ip_out_args */
 160 #include <netinet/ip6.h>        /* for ip6_out_args */
 161 #include <netinet6/ip6_var.h>   /* for ip6_out_args */
 162
 163 struct dn_pkt_tag {
 164     struct ip_fw        *dn_ipfw_rule;          /* matching IPFW rule */
 165     void                *dn_pf_rule;            /* matching PF rule */
 166     int                 dn_dir;                 /* action when packet comes out. */
 167 #define DN_TO_IP_OUT    1
 168 #define DN_TO_IP_IN     2
 169 #define DN_TO_BDG_FWD   3
 170 #define DN_TO_IP6_IN    4
 171 #define DN_TO_IP6_OUT   5
 172     dn_key              dn_output_time;         /* when the pkt is due for delivery     */
 173     struct ifnet        *dn_ifp;                /* interface, for ip[6]_output          */
 174     union {
 175         struct sockaddr_in      _dn_dst;
 176         struct sockaddr_in6     _dn_dst6 ;
 177     }                   dn_dst_;
 178 #define dn_dst dn_dst_._dn_dst
 179 #define dn_dst6 dn_dst_._dn_dst6
 180     union {
 181         struct route            _dn_ro;         /* route, for ip_output. MUST COPY      */
 182         struct route_in6        _dn_ro6;        /* route, for ip6_output. MUST COPY     */
 183         }               dn_ro_;
 184 #define dn_ro dn_ro_._dn_ro
 185 #define dn_ro6 dn_ro_._dn_ro6
 186     struct route_in6    dn_ro6_pmtu;            /* for ip6_output */
 187     struct ifnet        *dn_origifp;            /* for ip6_output */
 188     u_int32_t           dn_mtu;                 /* for ip6_output */
 189     int                 dn_alwaysfrag;          /* for ip6_output */
 190     u_int32_t           dn_unfragpartlen;       /* for ip6_output */
 191     struct ip6_exthdrs  dn_exthdrs;             /* for ip6_output */
 192     int                 dn_flags ;              /* flags, for ip[6]_output */
 193     int                 dn_client;
 194 #define DN_CLIENT_IPFW  1
 195 #define DN_CLIENT_PF    2
 196     union {
 197         struct ip_out_args      _dn_ipoa;       /* output args, for ip_output. MUST COPY */
 198         struct ip6_out_args     _dn_ip6oa;      /* output args, for ip_output. MUST COPY */
 199     }                   dn_ipoa_;
 200 #define dn_ipoa dn_ipoa_._dn_ipoa
 201 #define dn_ip6oa dn_ipoa_._dn_ip6oa
 202 };
 203 #else
 204 struct dn_pkt;
 205 #endif /* KERNEL */
 206
 207 /*
 208  * Overall structure of dummynet (with WF2Q+):
 209
 210 In dummynet, packets are selected with the firewall rules, and passed
 211 to two different objects: PIPE or QUEUE.
 212
 213 A QUEUE is just a queue with configurable size and queue management
 214 policy. It is also associated with a mask (to discriminate among
 215 different flows), a weight (used to give different shares of the
 216 bandwidth to different flows) and a "pipe", which essentially
 217 supplies the transmit clock for all queues associated with that
 218 pipe.
 219
 220 A PIPE emulates a fixed-bandwidth link, whose bandwidth is
 221 configurable.  The "clock" for a pipe can come from either an
 222 internal timer, or from the transmit interrupt of an interface.
 223 A pipe is also associated with one (or more, if masks are used)
 224 queue, where all packets for that pipe are stored.
 225
 226 The bandwidth available on the pipe is shared by the queues
 227 associated with that pipe (only one in case the packet is sent
 228 to a PIPE) according to the WF2Q+ scheduling algorithm and the
 229 configured weights.
 230
 231 In general, incoming packets are stored in the appropriate queue,
 232 which is then placed into one of a few heaps managed by a scheduler
 233 to decide when the packet should be extracted.
 234 The scheduler (a function called dummynet()) is run at every timer
 235 tick, and grabs queues from the head of the heaps when they are
 236 ready for processing.
 237
 238 There are three data structures definining a pipe and associated queues:
 239
 240  + dn_pipe, which contains the main configuration parameters related
 241    to delay and bandwidth;
 242  + dn_flow_set, which contains WF2Q+ configuration, flow
 243    masks, plr and RED configuration;
 244  + dn_flow_queue, which is the per-flow queue (containing the packets)
 245
 246 Multiple dn_flow_set can be linked to the same pipe, and multiple
 247 dn_flow_queue can be linked to the same dn_flow_set.
 248 All data structures are linked in a linear list which is used for
 249 housekeeping purposes.
 250
 251 During configuration, we create and initialize the dn_flow_set
 252 and dn_pipe structures (a dn_pipe also contains a dn_flow_set).
 253
 254 At runtime: packets are sent to the appropriate dn_flow_set (either
 255 WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows),
 256 which in turn dispatches them to the appropriate dn_flow_queue
 257 (created dynamically according to the masks).
 258
 259 The transmit clock for fixed rate flows (ready_event()) selects the
 260 dn_flow_queue to be used to transmit the next packet. For WF2Q,
 261 wfq_ready_event() extract a pipe which in turn selects the right
 262 flow using a number of heaps defined into the pipe itself.
 263
 264  *
 265  */
 266
 267 /*
 268  * per flow queue. This contains the flow identifier, the queue
 269  * of packets, counters, and parameters used to support both RED and
 270  * WF2Q+.
 271  *
 272  * A dn_flow_queue is created and initialized whenever a packet for
 273  * a new flow arrives.
 274  */
 275 struct dn_flow_queue {
 276     struct dn_flow_queue *next ;
 277     struct ip_flow_id id ;
 278
 279     struct mbuf *head, *tail ;  /* queue of packets */
 280     u_int len ;
 281     u_int len_bytes ;
 282     u_int32_t numbytes ;                /* credit for transmission (dynamic queues) */
 283
 284     u_int64_t tot_pkts ;        /* statistics counters  */
 285     u_int64_t tot_bytes ;
 286     u_int32_t drops ;
 287
 288     int hash_slot ;             /* debugging/diagnostic */
 289
 290     /* RED parameters */
 291     int avg ;                   /* average queue length est. (scaled) */
 292     int count ;                 /* arrivals since last RED drop */
 293     int random ;                /* random value (scaled) */
 294     u_int32_t q_time ;          /* start of queue idle time */
 295
 296     /* WF2Q+ support */
 297     struct dn_flow_set *fs ;    /* parent flow set */
 298     int heap_pos ;              /* position (index) of struct in heap */
 299     dn_key sched_time ;         /* current time when queue enters ready_heap */
 300
 301     dn_key S,F ;                /* start time, finish time */
 302     /*
 303      * Setting F < S means the timestamp is invalid. We only need
 304      * to test this when the queue is empty.
 305      */
 306 } ;
 307
 308 /*
 309  * flow_set descriptor. Contains the "template" parameters for the
 310  * queue configuration, and pointers to the hash table of dn_flow_queue's.
 311  *
 312  * The hash table is an array of lists -- we identify the slot by
 313  * hashing the flow-id, then scan the list looking for a match.
 314  * The size of the hash table (buckets) is configurable on a per-queue
 315  * basis.
 316  *
 317  * A dn_flow_set is created whenever a new queue or pipe is created (in the
 318  * latter case, the structure is located inside the struct dn_pipe).
 319  */
 320 struct dn_flow_set {
 321     SLIST_ENTRY(dn_flow_set)    next;   /* linked list in a hash slot */
 322
 323     u_short fs_nr ;             /* flow_set number       */
 324     u_short flags_fs;
 325 #define DN_HAVE_FLOW_MASK       0x0001
 326 #define DN_IS_RED               0x0002
 327 #define DN_IS_GENTLE_RED        0x0004
 328 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 329 #define DN_NOERROR              0x0010  /* do not report ENOBUFS on drops  */
 330 #define DN_IS_PIPE              0x4000
 331 #define DN_IS_QUEUE             0x8000
 332
 333     struct dn_pipe *pipe ;      /* pointer to parent pipe */
 334     u_short parent_nr ;         /* parent pipe#, 0 if local to a pipe */
 335
 336     int weight ;                /* WFQ queue weight */
 337     int qsize ;                 /* queue size in slots or bytes */
 338     int plr ;                   /* pkt loss rate (2^31-1 means 100%) */
 339
 340     struct ip_flow_id flow_mask ;
 341
 342     /* hash table of queues onto this flow_set */
 343     int rq_size ;               /* number of slots */
 344     int rq_elements ;           /* active elements */
 345     struct dn_flow_queue **rq;  /* array of rq_size entries */
 346
 347     u_int32_t last_expired ;    /* do not expire too frequently */
 348     int backlogged ;            /* #active queues for this flowset */
 349
 350         /* RED parameters */
 351 #define SCALE_RED               16
 352 #define SCALE(x)                ( (x) << SCALE_RED )
 353 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 354 #define SCALE_MUL(x,y)          ( ( (x) * (y) ) >> SCALE_RED )
 355     int w_q ;                   /* queue weight (scaled) */
 356     int max_th ;                /* maximum threshold for queue (scaled) */
 357     int min_th ;                /* minimum threshold for queue (scaled) */
 358     int max_p ;                 /* maximum value for p_b (scaled) */
 359     u_int c_1 ;                 /* max_p/(max_th-min_th) (scaled) */
 360     u_int c_2 ;                 /* max_p*min_th/(max_th-min_th) (scaled) */
 361     u_int c_3 ;                 /* for GRED, (1-max_p)/max_th (scaled) */
 362     u_int c_4 ;                 /* for GRED, 1 - 2*max_p (scaled) */
 363     u_int * w_q_lookup ;        /* lookup table for computing (1-w_q)^t */
 364     u_int lookup_depth ;        /* depth of lookup table */
 365     int lookup_step ;           /* granularity inside the lookup table */
 366     int lookup_weight ;         /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 367     int avg_pkt_size ;          /* medium packet size */
 368     int max_pkt_size ;          /* max packet size */
 369 } ;
 370
 371 SLIST_HEAD(dn_flow_set_head, dn_flow_set);
 372
 373 /*
 374  * Pipe descriptor. Contains global parameters, delay-line queue,
 375  * and the flow_set used for fixed-rate queues.
 376  *
 377  * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
 378  *   not_eligible_heap, for queues whose start time is higher
 379  *      than the virtual time. Sorted by start time.
 380  *   scheduler_heap, for queues eligible for scheduling. Sorted by
 381  *      finish time.
 382  *   idle_heap, all flows that are idle and can be removed. We
 383  *      do that on each tick so we do not slow down too much
 384  *      operations during forwarding.
 385  *
 386  */
 387 struct dn_pipe {                /* a pipe */
 388     SLIST_ENTRY(dn_pipe)        next;   /* linked list in a hash slot */
 389
 390     int pipe_nr ;               /* number       */
 391     int bandwidth;              /* really, bytes/tick.  */
 392     int delay ;                 /* really, ticks        */
 393
 394     struct      mbuf *head, *tail ;     /* packets in delay line */
 395
 396     /* WF2Q+ */
 397     struct dn_heap scheduler_heap ; /* top extract - key Finish time*/
 398     struct dn_heap not_eligible_heap; /* top extract- key Start time */
 399     struct dn_heap idle_heap ; /* random extract - key Start=Finish time */
 400
 401     dn_key V ;                  /* virtual time */
 402     int sum;                    /* sum of weights of all active sessions */
 403     int numbytes;               /* bits I can transmit (more or less). */
 404
 405     dn_key sched_time ;         /* time pipe was scheduled in ready_heap */
 406
 407     /*
 408      * When the tx clock come from an interface (if_name[0] != '\0'), its name
 409      * is stored below, whereas the ifp is filled when the rule is configured.
 410      */
 411     char if_name[IFNAMSIZ];
 412     struct ifnet *ifp ;
 413     int ready ; /* set if ifp != NULL and we got a signal from it */
 414
 415     struct dn_flow_set fs ; /* used with fixed-rate flows */
 416 };
 417
 418 SLIST_HEAD(dn_pipe_head, dn_pipe);
 419
 420 #ifdef BSD_KERNEL_PRIVATE
 421
 422 void ip_dn_init(void); /* called from raw_ip.c:load_ipfw() */
 423
 424 typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */
 425 typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir,
 426         struct ip_fw_args *fwa, int );
 427 extern  ip_dn_ctl_t *ip_dn_ctl_ptr;
 428 extern  ip_dn_io_t *ip_dn_io_ptr;
 429 void dn_ipfw_rule_delete(void *);
 430 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
 431
 432 #pragma pack(4)
 433
 434 struct dn_heap_32 {
 435     int size ;
 436     int elements ;
 437     int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */
 438     user32_addr_t p ;   /* really an array of "size" entries */
 439 } ;
 440
 441 struct dn_flow_queue_32 {
 442     user32_addr_t next ;
 443     struct ip_flow_id id ;
 444
 445     user32_addr_t head, tail ;  /* queue of packets */
 446     u_int len ;
 447     u_int len_bytes ;
 448     u_int32_t numbytes ;        /* credit for transmission (dynamic queues) */
 449
 450     u_int64_t tot_pkts ;        /* statistics counters  */
 451     u_int64_t tot_bytes ;
 452     u_int32_t drops ;
 453
 454     int hash_slot ;                     /* debugging/diagnostic */
 455
 456     /* RED parameters */
 457     int avg ;                   /* average queue length est. (scaled) */
 458     int count ;                 /* arrivals since last RED drop */
 459     int random ;                /* random value (scaled) */
 460     u_int32_t q_time ;          /* start of queue idle time */
 461
 462     /* WF2Q+ support */
 463     user32_addr_t fs ;  /* parent flow set */
 464     int heap_pos ;              /* position (index) of struct in heap */
 465     dn_key sched_time ;         /* current time when queue enters ready_heap */
 466
 467     dn_key S,F ;                /* start time, finish time */
 468     /*
 469      * Setting F < S means the timestamp is invalid. We only need
 470      * to test this when the queue is empty.
 471      */
 472 } ;
 473
 474 struct dn_flow_set_32 {
 475     user32_addr_t       next; /* next flow set in all_flow_sets list */
 476
 477     u_short fs_nr ;                     /* flow_set number       */
 478     u_short flags_fs;
 479 #define DN_HAVE_FLOW_MASK       0x0001
 480 #define DN_IS_RED               0x0002
 481 #define DN_IS_GENTLE_RED        0x0004
 482 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 483 #define DN_NOERROR              0x0010          /* do not report ENOBUFS on drops  */
 484 #define DN_IS_PIPE              0x4000
 485 #define DN_IS_QUEUE             0x8000
 486
 487     user32_addr_t pipe ;        /* pointer to parent pipe */
 488     u_short parent_nr ;         /* parent pipe#, 0 if local to a pipe */
 489
 490     int weight ;                /* WFQ queue weight */
 491     int qsize ;                 /* queue size in slots or bytes */
 492     int plr ;                   /* pkt loss rate (2^31-1 means 100%) */
 493
 494     struct ip_flow_id flow_mask ;
 495
 496     /* hash table of queues onto this flow_set */
 497     int rq_size ;               /* number of slots */
 498     int rq_elements ;   /* active elements */
 499     user32_addr_t rq;   /* array of rq_size entries */
 500
 501     u_int32_t last_expired ;    /* do not expire too frequently */
 502     int backlogged ;                    /* #active queues for this flowset */
 503
 504         /* RED parameters */
 505 #define SCALE_RED               16
 506 #define SCALE(x)                ( (x) << SCALE_RED )
 507 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 508 #define SCALE_MUL(x,y)          ( ( (x) * (y) ) >> SCALE_RED )
 509     int w_q ;                   /* queue weight (scaled) */
 510     int max_th ;                /* maximum threshold for queue (scaled) */
 511     int min_th ;                /* minimum threshold for queue (scaled) */
 512     int max_p ;                 /* maximum value for p_b (scaled) */
 513     u_int c_1 ;                 /* max_p/(max_th-min_th) (scaled) */
 514     u_int c_2 ;                 /* max_p*min_th/(max_th-min_th) (scaled) */
 515     u_int c_3 ;                 /* for GRED, (1-max_p)/max_th (scaled) */
 516     u_int c_4 ;                 /* for GRED, 1 - 2*max_p (scaled) */
 517     user32_addr_t w_q_lookup ;  /* lookup table for computing (1-w_q)^t */
 518     u_int lookup_depth ;        /* depth of lookup table */
 519     int lookup_step ;           /* granularity inside the lookup table */
 520     int lookup_weight ;         /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 521     int avg_pkt_size ;          /* medium packet size */
 522     int max_pkt_size ;          /* max packet size */
 523 } ;
 524
 525 struct dn_pipe_32 {             /* a pipe */
 526     user32_addr_t       next ;
 527
 528     int pipe_nr ;               /* number       */
 529     int bandwidth;              /* really, bytes/tick.  */
 530     int delay ;                 /* really, ticks        */
 531
 532     user32_addr_t head, tail ;  /* packets in delay line */
 533
 534     /* WF2Q+ */
 535     struct dn_heap_32 scheduler_heap ; /* top extract - key Finish time*/
 536     struct dn_heap_32 not_eligible_heap; /* top extract- key Start time */
 537     struct dn_heap_32 idle_heap ; /* random extract - key Start=Finish time */
 538
 539     dn_key V ;                  /* virtual time */
 540     int sum;                    /* sum of weights of all active sessions */
 541     int numbytes;               /* bits I can transmit (more or less). */
 542
 543     dn_key sched_time ; /* time pipe was scheduled in ready_heap */
 544
 545     /*
 546      * When the tx clock come from an interface (if_name[0] != '\0'), its name
 547      * is stored below, whereas the ifp is filled when the rule is configured.
 548      */
 549     char if_name[IFNAMSIZ];
 550     user32_addr_t ifp ;
 551     int ready ;                 /* set if ifp != NULL and we got a signal from it */
 552
 553     struct dn_flow_set_32 fs ; /* used with fixed-rate flows */
 554 };
 555 #pragma pack()
 556
 557
 558 struct dn_heap_64 {
 559     int size ;
 560     int elements ;
 561     int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */
 562     user64_addr_t p ;   /* really an array of "size" entries */
 563 } ;
 564
 565
 566 struct dn_flow_queue_64 {
 567     user64_addr_t next ;
 568     struct ip_flow_id id ;
 569
 570     user64_addr_t head, tail ;  /* queue of packets */
 571     u_int len ;
 572     u_int len_bytes ;
 573     u_int32_t numbytes ;                /* credit for transmission (dynamic queues) */
 574
 575     u_int64_t tot_pkts ;                /* statistics counters  */
 576     u_int64_t tot_bytes ;
 577     u_int32_t drops ;
 578
 579     int hash_slot ;                             /* debugging/diagnostic */
 580
 581     /* RED parameters */
 582     int avg ;                   /* average queue length est. (scaled) */
 583     int count ;                 /* arrivals since last RED drop */
 584     int random ;                /* random value (scaled) */
 585     u_int32_t q_time ;          /* start of queue idle time */
 586
 587     /* WF2Q+ support */
 588     user64_addr_t fs ;                  /* parent flow set */
 589     int heap_pos ;                              /* position (index) of struct in heap */
 590     dn_key sched_time ;                 /* current time when queue enters ready_heap */
 591
 592     dn_key S,F ;                                /* start time, finish time */
 593     /*
 594      * Setting F < S means the timestamp is invalid. We only need
 595      * to test this when the queue is empty.
 596      */
 597 } ;
 598
 599 struct dn_flow_set_64 {
 600     user64_addr_t next;                 /* next flow set in all_flow_sets list */
 601
 602     u_short fs_nr ;             /* flow_set number       */
 603     u_short flags_fs;
 604 #define DN_HAVE_FLOW_MASK       0x0001
 605 #define DN_IS_RED               0x0002
 606 #define DN_IS_GENTLE_RED        0x0004
 607 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 608 #define DN_NOERROR              0x0010          /* do not report ENOBUFS on drops  */
 609 #define DN_IS_PIPE              0x4000
 610 #define DN_IS_QUEUE             0x8000
 611
 612     user64_addr_t pipe ;        /* pointer to parent pipe */
 613     u_short parent_nr ;         /* parent pipe#, 0 if local to a pipe */
 614
 615     int weight ;                /* WFQ queue weight */
 616     int qsize ;                 /* queue size in slots or bytes */
 617     int plr ;                   /* pkt loss rate (2^31-1 means 100%) */
 618
 619     struct ip_flow_id flow_mask ;
 620
 621     /* hash table of queues onto this flow_set */
 622     int rq_size ;               /* number of slots */
 623     int rq_elements ;   /* active elements */
 624     user64_addr_t rq;   /* array of rq_size entries */
 625
 626     u_int32_t last_expired ;    /* do not expire too frequently */
 627     int backlogged ;                    /* #active queues for this flowset */
 628
 629         /* RED parameters */
 630 #define SCALE_RED               16
 631 #define SCALE(x)                ( (x) << SCALE_RED )
 632 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 633 #define SCALE_MUL(x,y)          ( ( (x) * (y) ) >> SCALE_RED )
 634     int w_q ;                   /* queue weight (scaled) */
 635     int max_th ;                /* maximum threshold for queue (scaled) */
 636     int min_th ;                /* minimum threshold for queue (scaled) */
 637     int max_p ;                 /* maximum value for p_b (scaled) */
 638     u_int c_1 ;                 /* max_p/(max_th-min_th) (scaled) */
 639     u_int c_2 ;                 /* max_p*min_th/(max_th-min_th) (scaled) */
 640     u_int c_3 ;                 /* for GRED, (1-max_p)/max_th (scaled) */
 641     u_int c_4 ;                 /* for GRED, 1 - 2*max_p (scaled) */
 642     user64_addr_t w_q_lookup ;  /* lookup table for computing (1-w_q)^t */
 643     u_int lookup_depth ;        /* depth of lookup table */
 644     int lookup_step ;           /* granularity inside the lookup table */
 645     int lookup_weight ;         /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 646     int avg_pkt_size ;          /* medium packet size */
 647     int max_pkt_size ;          /* max packet size */
 648 } ;
 649
 650 struct dn_pipe_64 {             /* a pipe */
 651     user64_addr_t       next ;
 652
 653     int pipe_nr ;               /* number       */
 654     int bandwidth;              /* really, bytes/tick.  */
 655     int delay ;                 /* really, ticks        */
 656
 657     user64_addr_t head, tail ;  /* packets in delay line */
 658
 659     /* WF2Q+ */
 660     struct dn_heap_64 scheduler_heap ;          /* top extract - key Finish time*/
 661     struct dn_heap_64 not_eligible_heap;        /* top extract- key Start time */
 662     struct dn_heap_64 idle_heap ;                       /* random extract - key Start=Finish time */
 663
 664     dn_key V ;                  /* virtual time */
 665     int sum;                    /* sum of weights of all active sessions */
 666     int numbytes;               /* bits I can transmit (more or less). */
 667
 668     dn_key sched_time ; /* time pipe was scheduled in ready_heap */
 669
 670     /*
 671      * When the tx clock come from an interface (if_name[0] != '\0'), its name
 672      * is stored below, whereas the ifp is filled when the rule is configured.
 673      */
 674     char if_name[IFNAMSIZ];
 675     user64_addr_t ifp ;
 676     int ready ; /* set if ifp != NULL and we got a signal from it */
 677
 678     struct dn_flow_set_64 fs ; /* used with fixed-rate flows */
 679 };
 680
 681
 682
 683 /*
 684  * Return the IPFW rule associated with the dummynet tag; if any.
 685  * Make sure that the dummynet tag is not reused by lower layers.
 686  */
 687 static __inline struct ip_fw *
 688 ip_dn_claim_rule(struct mbuf *m)
 689 {
 690         struct m_tag *mtag = m_tag_locate(m, KERNEL_MODULE_TAG_ID,
 691                                                                           KERNEL_TAG_TYPE_DUMMYNET, NULL);
 692         if (mtag != NULL) {
 693                 mtag->m_tag_type = KERNEL_TAG_TYPE_NONE;
 694                 return (((struct dn_pkt_tag *)(mtag+1))->dn_ipfw_rule);
 695         } else
 696                 return (NULL);
 697 }
 698 #endif /* BSD_KERNEL_PRIVATE */
 699 #endif /* PRIVATE */
 700 #endif /* _IP_DUMMYNET_H */