bsd/netinet/ip_dummynet.h

   1 /*
   2  * Copyright (c) 2000-2019 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         void                *dn_pf_rule;        /* matching PF rule */
 161         int                 dn_dir;             /* action when packet comes out. */
 162 #define DN_TO_IP_OUT    1
 163 #define DN_TO_IP_IN     2
 164 #define DN_TO_BDG_FWD   3
 165 #define DN_TO_IP6_IN    4
 166 #define DN_TO_IP6_OUT   5
 167         dn_key              dn_output_time;     /* when the pkt is due for delivery     */
 168         struct ifnet        *dn_ifp;            /* interface, for ip[6]_output          */
 169         union {
 170                 struct sockaddr_in      _dn_dst;
 171                 struct sockaddr_in6     _dn_dst6;
 172         }                   dn_dst_;
 173 #define dn_dst dn_dst_._dn_dst
 174 #define dn_dst6 dn_dst_._dn_dst6
 175         union {
 176                 struct route            _dn_ro; /* route, for ip_output. MUST COPY      */
 177                 struct route_in6        _dn_ro6;/* route, for ip6_output. MUST COPY     */
 178         }               dn_ro_;
 179 #define dn_ro dn_ro_._dn_ro
 180 #define dn_ro6 dn_ro_._dn_ro6
 181         struct route_in6    dn_ro6_pmtu;        /* for ip6_output */
 182         struct ifnet        *dn_origifp;        /* for ip6_output */
 183         u_int32_t           dn_mtu;             /* for ip6_output */
 184         u_int32_t           dn_unfragpartlen;   /* for ip6_output */
 185         struct ip6_exthdrs  dn_exthdrs;         /* for ip6_output */
 186         int                 dn_flags;           /* flags, for ip[6]_output */
 187         union {
 188                 struct ip_out_args      _dn_ipoa;/* output args, for ip_output. MUST COPY */
 189                 struct ip6_out_args     _dn_ip6oa;/* output args, for ip_output. MUST COPY */
 190         }                   dn_ipoa_;
 191 #define dn_ipoa dn_ipoa_._dn_ipoa
 192 #define dn_ip6oa dn_ipoa_._dn_ip6oa
 193 };
 194 #else
 195 struct dn_pkt;
 196 #endif /* KERNEL */
 197
 198 /*
 199  * Overall structure of dummynet (with WF2Q+):
 200  *
 201  *  In dummynet, packets are selected with the firewall rules, and passed
 202  *  to two different objects: PIPE or QUEUE.
 203  *
 204  *  A QUEUE is just a queue with configurable size and queue management
 205  *  policy. It is also associated with a mask (to discriminate among
 206  *  different flows), a weight (used to give different shares of the
 207  *  bandwidth to different flows) and a "pipe", which essentially
 208  *  supplies the transmit clock for all queues associated with that
 209  *  pipe.
 210  *
 211  *  A PIPE emulates a fixed-bandwidth link, whose bandwidth is
 212  *  configurable.  The "clock" for a pipe can come from either an
 213  *  internal timer, or from the transmit interrupt of an interface.
 214  *  A pipe is also associated with one (or more, if masks are used)
 215  *  queue, where all packets for that pipe are stored.
 216  *
 217  *  The bandwidth available on the pipe is shared by the queues
 218  *  associated with that pipe (only one in case the packet is sent
 219  *  to a PIPE) according to the WF2Q+ scheduling algorithm and the
 220  *  configured weights.
 221  *
 222  *  In general, incoming packets are stored in the appropriate queue,
 223  *  which is then placed into one of a few heaps managed by a scheduler
 224  *  to decide when the packet should be extracted.
 225  *  The scheduler (a function called dummynet()) is run at every timer
 226  *  tick, and grabs queues from the head of the heaps when they are
 227  *  ready for processing.
 228  *
 229  *  There are three data structures definining a pipe and associated queues:
 230  *
 231  + dn_pipe, which contains the main configuration parameters related
 232  +  to delay and bandwidth;
 233  + dn_flow_set, which contains WF2Q+ configuration, flow
 234  +  masks, plr and RED configuration;
 235  + dn_flow_queue, which is the per-flow queue (containing the packets)
 236  +
 237  +  Multiple dn_flow_set can be linked to the same pipe, and multiple
 238  +  dn_flow_queue can be linked to the same dn_flow_set.
 239  +  All data structures are linked in a linear list which is used for
 240  +  housekeeping purposes.
 241  +
 242  +  During configuration, we create and initialize the dn_flow_set
 243  +  and dn_pipe structures (a dn_pipe also contains a dn_flow_set).
 244  +
 245  +  At runtime: packets are sent to the appropriate dn_flow_set (either
 246  +  WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows),
 247  +  which in turn dispatches them to the appropriate dn_flow_queue
 248  +  (created dynamically according to the masks).
 249  +
 250  +  The transmit clock for fixed rate flows (ready_event()) selects the
 251  +  dn_flow_queue to be used to transmit the next packet. For WF2Q,
 252  +  wfq_ready_event() extract a pipe which in turn selects the right
 253  +  flow using a number of heaps defined into the pipe itself.
 254  +
 255  *
 256  */
 257
 258 /*
 259  * per flow queue. This contains the flow identifier, the queue
 260  * of packets, counters, and parameters used to support both RED and
 261  * WF2Q+.
 262  *
 263  * A dn_flow_queue is created and initialized whenever a packet for
 264  * a new flow arrives.
 265  */
 266 struct dn_flow_queue {
 267         struct dn_flow_queue *next;
 268         struct ip_flow_id id;
 269
 270         struct mbuf *head, *tail; /* queue of packets */
 271         u_int len;
 272         u_int len_bytes;
 273         u_int32_t numbytes;             /* credit for transmission (dynamic queues) */
 274
 275         u_int64_t tot_pkts;     /* statistics counters  */
 276         u_int64_t tot_bytes;
 277         u_int32_t drops;
 278
 279         int hash_slot;          /* debugging/diagnostic */
 280
 281         /* RED parameters */
 282         int avg;                /* average queue length est. (scaled) */
 283         int count;              /* arrivals since last RED drop */
 284         int random;             /* random value (scaled) */
 285         u_int32_t q_time;       /* start of queue idle time */
 286
 287         /* WF2Q+ support */
 288         struct dn_flow_set *fs; /* parent flow set */
 289         int heap_pos;           /* position (index) of struct in heap */
 290         dn_key sched_time;      /* current time when queue enters ready_heap */
 291
 292         dn_key S, F;            /* start time, finish time */
 293         /*
 294          * Setting F < S means the timestamp is invalid. We only need
 295          * to test this when the queue is empty.
 296          */
 297 };
 298
 299 /*
 300  * flow_set descriptor. Contains the "template" parameters for the
 301  * queue configuration, and pointers to the hash table of dn_flow_queue's.
 302  *
 303  * The hash table is an array of lists -- we identify the slot by
 304  * hashing the flow-id, then scan the list looking for a match.
 305  * The size of the hash table (buckets) is configurable on a per-queue
 306  * basis.
 307  *
 308  * A dn_flow_set is created whenever a new queue or pipe is created (in the
 309  * latter case, the structure is located inside the struct dn_pipe).
 310  */
 311 struct dn_flow_set {
 312         SLIST_ENTRY(dn_flow_set)    next;/* linked list in a hash slot */
 313
 314         u_short fs_nr;          /* flow_set number       */
 315         u_short flags_fs;
 316 #define DN_HAVE_FLOW_MASK       0x0001
 317 #define DN_IS_RED               0x0002
 318 #define DN_IS_GENTLE_RED        0x0004
 319 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 320 #define DN_NOERROR              0x0010  /* do not report ENOBUFS on drops  */
 321 #define DN_IS_PIPE              0x4000
 322 #define DN_IS_QUEUE             0x8000
 323
 324         struct dn_pipe *pipe;   /* pointer to parent pipe */
 325         u_short parent_nr;      /* parent pipe#, 0 if local to a pipe */
 326
 327         int weight;             /* WFQ queue weight */
 328         int qsize;              /* queue size in slots or bytes */
 329         int plr;                /* pkt loss rate (2^31-1 means 100%) */
 330
 331         struct ip_flow_id flow_mask;
 332
 333         /* hash table of queues onto this flow_set */
 334         int rq_size;            /* number of slots */
 335         int rq_elements;        /* active elements */
 336         struct dn_flow_queue **rq; /* array of rq_size entries */
 337
 338         u_int32_t last_expired; /* do not expire too frequently */
 339         int backlogged;         /* #active queues for this flowset */
 340
 341         /* RED parameters */
 342 #define SCALE_RED               16
 343 #define SCALE(x)                ( (x) << SCALE_RED )
 344 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 345 #define SCALE_MUL(x, y)          ( ( (x) * (y) ) >> SCALE_RED )
 346         int w_q;                /* queue weight (scaled) */
 347         int max_th;             /* maximum threshold for queue (scaled) */
 348         int min_th;             /* minimum threshold for queue (scaled) */
 349         int max_p;              /* maximum value for p_b (scaled) */
 350         u_int c_1;              /* max_p/(max_th-min_th) (scaled) */
 351         u_int c_2;              /* max_p*min_th/(max_th-min_th) (scaled) */
 352         u_int c_3;              /* for GRED, (1-max_p)/max_th (scaled) */
 353         u_int c_4;              /* for GRED, 1 - 2*max_p (scaled) */
 354         u_int * w_q_lookup;     /* lookup table for computing (1-w_q)^t */
 355         u_int lookup_depth;     /* depth of lookup table */
 356         int lookup_step;        /* granularity inside the lookup table */
 357         int lookup_weight;      /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 358         int avg_pkt_size;       /* medium packet size */
 359         int max_pkt_size;       /* max packet size */
 360 };
 361
 362 SLIST_HEAD(dn_flow_set_head, dn_flow_set);
 363
 364 /*
 365  * Pipe descriptor. Contains global parameters, delay-line queue,
 366  * and the flow_set used for fixed-rate queues.
 367  *
 368  * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
 369  *   not_eligible_heap, for queues whose start time is higher
 370  *      than the virtual time. Sorted by start time.
 371  *   scheduler_heap, for queues eligible for scheduling. Sorted by
 372  *      finish time.
 373  *   idle_heap, all flows that are idle and can be removed. We
 374  *      do that on each tick so we do not slow down too much
 375  *      operations during forwarding.
 376  *
 377  */
 378 struct dn_pipe {                /* a pipe */
 379         SLIST_ENTRY(dn_pipe)        next;/* linked list in a hash slot */
 380
 381         int pipe_nr;            /* number       */
 382         int bandwidth;          /* really, bytes/tick.  */
 383         int delay;              /* really, ticks        */
 384
 385         struct      mbuf *head, *tail;  /* packets in delay line */
 386
 387         /* WF2Q+ */
 388         struct dn_heap scheduler_heap; /* top extract - key Finish time*/
 389         struct dn_heap not_eligible_heap; /* top extract- key Start time */
 390         struct dn_heap idle_heap; /* random extract - key Start=Finish time */
 391
 392         dn_key V;               /* virtual time */
 393         int sum;                /* sum of weights of all active sessions */
 394         int numbytes;           /* bits I can transmit (more or less). */
 395
 396         dn_key sched_time;      /* time pipe was scheduled in ready_heap */
 397
 398         /*
 399          * When the tx clock come from an interface (if_name[0] != '\0'), its name
 400          * is stored below, whereas the ifp is filled when the rule is configured.
 401          */
 402         char if_name[IFNAMSIZ];
 403         struct ifnet *ifp;
 404         int ready; /* set if ifp != NULL and we got a signal from it */
 405
 406         struct dn_flow_set fs; /* used with fixed-rate flows */
 407 };
 408
 409 SLIST_HEAD(dn_pipe_head, dn_pipe);
 410
 411 #ifdef BSD_KERNEL_PRIVATE
 412 extern uint32_t my_random(void);
 413 void ip_dn_init(void);
 414
 415 typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */
 416 typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir,
 417     struct ip_fw_args *fwa);
 418 extern  ip_dn_ctl_t *ip_dn_ctl_ptr;
 419 extern  ip_dn_io_t *ip_dn_io_ptr;
 420 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
 421
 422 #pragma pack(4)
 423
 424 struct dn_heap_32 {
 425         int size;
 426         int elements;
 427         int offset; /* XXX if > 0 this is the offset of direct ptr to obj */
 428         user32_addr_t p; /* really an array of "size" entries */
 429 };
 430
 431 struct dn_flow_queue_32 {
 432         user32_addr_t next;
 433         struct ip_flow_id id;
 434
 435         user32_addr_t head, tail; /* queue of packets */
 436         u_int len;
 437         u_int len_bytes;
 438         u_int32_t numbytes;     /* credit for transmission (dynamic queues) */
 439
 440         u_int64_t tot_pkts;     /* statistics counters  */
 441         u_int64_t tot_bytes;
 442         u_int32_t drops;
 443
 444         int hash_slot;                  /* debugging/diagnostic */
 445
 446         /* RED parameters */
 447         int avg;                /* average queue length est. (scaled) */
 448         int count;              /* arrivals since last RED drop */
 449         int random;             /* random value (scaled) */
 450         u_int32_t q_time;       /* start of queue idle time */
 451
 452         /* WF2Q+ support */
 453         user32_addr_t fs; /* parent flow set */
 454         int heap_pos;           /* position (index) of struct in heap */
 455         dn_key sched_time;      /* current time when queue enters ready_heap */
 456
 457         dn_key S, F;            /* start time, finish time */
 458         /*
 459          * Setting F < S means the timestamp is invalid. We only need
 460          * to test this when the queue is empty.
 461          */
 462 };
 463
 464 struct dn_flow_set_32 {
 465         user32_addr_t       next;/* next flow set in all_flow_sets list */
 466
 467         u_short fs_nr;                  /* flow_set number       */
 468         u_short flags_fs;
 469 #define DN_HAVE_FLOW_MASK       0x0001
 470 #define DN_IS_RED               0x0002
 471 #define DN_IS_GENTLE_RED        0x0004
 472 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 473 #define DN_NOERROR              0x0010          /* do not report ENOBUFS on drops  */
 474 #define DN_IS_PIPE              0x4000
 475 #define DN_IS_QUEUE             0x8000
 476
 477         user32_addr_t pipe;     /* pointer to parent pipe */
 478         u_short parent_nr;      /* parent pipe#, 0 if local to a pipe */
 479
 480         int weight;             /* WFQ queue weight */
 481         int qsize;              /* queue size in slots or bytes */
 482         int plr;                /* pkt loss rate (2^31-1 means 100%) */
 483
 484         struct ip_flow_id flow_mask;
 485
 486         /* hash table of queues onto this flow_set */
 487         int rq_size;            /* number of slots */
 488         int rq_elements; /* active elements */
 489         user32_addr_t rq; /* array of rq_size entries */
 490
 491         u_int32_t last_expired; /* do not expire too frequently */
 492         int backlogged;                 /* #active queues for this flowset */
 493
 494         /* RED parameters */
 495 #define SCALE_RED               16
 496 #define SCALE(x)                ( (x) << SCALE_RED )
 497 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 498 #define SCALE_MUL(x, y)          ( ( (x) * (y) ) >> SCALE_RED )
 499         int w_q;                /* queue weight (scaled) */
 500         int max_th;             /* maximum threshold for queue (scaled) */
 501         int min_th;             /* minimum threshold for queue (scaled) */
 502         int max_p;              /* maximum value for p_b (scaled) */
 503         u_int c_1;              /* max_p/(max_th-min_th) (scaled) */
 504         u_int c_2;              /* max_p*min_th/(max_th-min_th) (scaled) */
 505         u_int c_3;              /* for GRED, (1-max_p)/max_th (scaled) */
 506         u_int c_4;              /* for GRED, 1 - 2*max_p (scaled) */
 507         user32_addr_t w_q_lookup; /* lookup table for computing (1-w_q)^t */
 508         u_int lookup_depth;     /* depth of lookup table */
 509         int lookup_step;        /* granularity inside the lookup table */
 510         int lookup_weight;      /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 511         int avg_pkt_size;       /* medium packet size */
 512         int max_pkt_size;       /* max packet size */
 513 };
 514
 515 struct dn_pipe_32 {             /* a pipe */
 516         user32_addr_t       next;
 517
 518         int pipe_nr;            /* number       */
 519         int bandwidth;          /* really, bytes/tick.  */
 520         int delay;              /* really, ticks        */
 521
 522         user32_addr_t head, tail; /* packets in delay line */
 523
 524         /* WF2Q+ */
 525         struct dn_heap_32 scheduler_heap; /* top extract - key Finish time*/
 526         struct dn_heap_32 not_eligible_heap; /* top extract- key Start time */
 527         struct dn_heap_32 idle_heap; /* random extract - key Start=Finish time */
 528
 529         dn_key V;               /* virtual time */
 530         int sum;                /* sum of weights of all active sessions */
 531         int numbytes;           /* bits I can transmit (more or less). */
 532
 533         dn_key sched_time; /* time pipe was scheduled in ready_heap */
 534
 535         /*
 536          * When the tx clock come from an interface (if_name[0] != '\0'), its name
 537          * is stored below, whereas the ifp is filled when the rule is configured.
 538          */
 539         char if_name[IFNAMSIZ];
 540         user32_addr_t ifp;
 541         int ready;              /* set if ifp != NULL and we got a signal from it */
 542
 543         struct dn_flow_set_32 fs; /* used with fixed-rate flows */
 544 };
 545 #pragma pack()
 546
 547
 548 struct dn_heap_64 {
 549         int size;
 550         int elements;
 551         int offset; /* XXX if > 0 this is the offset of direct ptr to obj */
 552         user64_addr_t p; /* really an array of "size" entries */
 553 };
 554
 555
 556 struct dn_flow_queue_64 {
 557         user64_addr_t next;
 558         struct ip_flow_id id;
 559
 560         user64_addr_t head, tail; /* queue of packets */
 561         u_int len;
 562         u_int len_bytes;
 563         u_int32_t numbytes;             /* credit for transmission (dynamic queues) */
 564
 565         u_int64_t tot_pkts;             /* statistics counters  */
 566         u_int64_t tot_bytes;
 567         u_int32_t drops;
 568
 569         int hash_slot;                          /* debugging/diagnostic */
 570
 571         /* RED parameters */
 572         int avg;                /* average queue length est. (scaled) */
 573         int count;              /* arrivals since last RED drop */
 574         int random;             /* random value (scaled) */
 575         u_int32_t q_time;       /* start of queue idle time */
 576
 577         /* WF2Q+ support */
 578         user64_addr_t fs;               /* parent flow set */
 579         int heap_pos;                           /* position (index) of struct in heap */
 580         dn_key sched_time;              /* current time when queue enters ready_heap */
 581
 582         dn_key S, F;                            /* start time, finish time */
 583         /*
 584          * Setting F < S means the timestamp is invalid. We only need
 585          * to test this when the queue is empty.
 586          */
 587 };
 588
 589 struct dn_flow_set_64 {
 590         user64_addr_t next;             /* next flow set in all_flow_sets list */
 591
 592         u_short fs_nr;          /* flow_set number       */
 593         u_short flags_fs;
 594 #define DN_HAVE_FLOW_MASK       0x0001
 595 #define DN_IS_RED               0x0002
 596 #define DN_IS_GENTLE_RED        0x0004
 597 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
 598 #define DN_NOERROR              0x0010          /* do not report ENOBUFS on drops  */
 599 #define DN_IS_PIPE              0x4000
 600 #define DN_IS_QUEUE             0x8000
 601
 602         user64_addr_t pipe;     /* pointer to parent pipe */
 603         u_short parent_nr;      /* parent pipe#, 0 if local to a pipe */
 604
 605         int weight;             /* WFQ queue weight */
 606         int qsize;              /* queue size in slots or bytes */
 607         int plr;                /* pkt loss rate (2^31-1 means 100%) */
 608
 609         struct ip_flow_id flow_mask;
 610
 611         /* hash table of queues onto this flow_set */
 612         int rq_size;            /* number of slots */
 613         int rq_elements; /* active elements */
 614         user64_addr_t rq; /* array of rq_size entries */
 615
 616         u_int32_t last_expired; /* do not expire too frequently */
 617         int backlogged;                 /* #active queues for this flowset */
 618
 619         /* RED parameters */
 620 #define SCALE_RED               16
 621 #define SCALE(x)                ( (x) << SCALE_RED )
 622 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
 623 #define SCALE_MUL(x, y)          ( ( (x) * (y) ) >> SCALE_RED )
 624         int w_q;                /* queue weight (scaled) */
 625         int max_th;             /* maximum threshold for queue (scaled) */
 626         int min_th;             /* minimum threshold for queue (scaled) */
 627         int max_p;              /* maximum value for p_b (scaled) */
 628         u_int c_1;              /* max_p/(max_th-min_th) (scaled) */
 629         u_int c_2;              /* max_p*min_th/(max_th-min_th) (scaled) */
 630         u_int c_3;              /* for GRED, (1-max_p)/max_th (scaled) */
 631         u_int c_4;              /* for GRED, 1 - 2*max_p (scaled) */
 632         user64_addr_t w_q_lookup; /* lookup table for computing (1-w_q)^t */
 633         u_int lookup_depth;     /* depth of lookup table */
 634         int lookup_step;        /* granularity inside the lookup table */
 635         int lookup_weight;      /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 636         int avg_pkt_size;       /* medium packet size */
 637         int max_pkt_size;       /* max packet size */
 638 };
 639
 640 struct dn_pipe_64 {             /* a pipe */
 641         user64_addr_t       next;
 642
 643         int pipe_nr;            /* number       */
 644         int bandwidth;          /* really, bytes/tick.  */
 645         int delay;              /* really, ticks        */
 646
 647         user64_addr_t head, tail; /* packets in delay line */
 648
 649         /* WF2Q+ */
 650         struct dn_heap_64 scheduler_heap;       /* top extract - key Finish time*/
 651         struct dn_heap_64 not_eligible_heap;    /* top extract- key Start time */
 652         struct dn_heap_64 idle_heap;                    /* random extract - key Start=Finish time */
 653
 654         dn_key V;               /* virtual time */
 655         int sum;                /* sum of weights of all active sessions */
 656         int numbytes;           /* bits I can transmit (more or less). */
 657
 658         dn_key sched_time; /* time pipe was scheduled in ready_heap */
 659
 660         /*
 661          * When the tx clock come from an interface (if_name[0] != '\0'), its name
 662          * is stored below, whereas the ifp is filled when the rule is configured.
 663          */
 664         char if_name[IFNAMSIZ];
 665         user64_addr_t ifp;
 666         int ready; /* set if ifp != NULL and we got a signal from it */
 667
 668         struct dn_flow_set_64 fs; /* used with fixed-rate flows */
 669 };
 670
 671 #include <sys/eventhandler.h>
 672 /* Dummynet event handling declarations */
 673 extern struct eventhandler_lists_ctxt dummynet_evhdlr_ctxt;
 674 extern void dummynet_init(void);
 675
 676 struct dn_pipe_mini_config {
 677         uint32_t bandwidth;
 678         uint32_t delay;
 679         uint32_t plr;
 680 };
 681
 682 struct dn_rule_mini_config {
 683         uint32_t dir;
 684         uint32_t af;
 685         uint32_t proto;
 686         /*
 687          * XXX PF rules actually define ranges of ports and
 688          * along with range goes an opcode ((not) equal to, less than
 689          * greater than, etc.
 690          * For now the following works assuming there's no port range
 691          * and the rule is for specific port.
 692          * Also the operation is assumed as equal to.
 693          */
 694         uint32_t src_port;
 695         uint32_t dst_port;
 696         char ifname[IFXNAMSIZ];
 697 };
 698
 699 struct dummynet_event {
 700         uint32_t dn_event_code;
 701         union {
 702                 struct dn_pipe_mini_config _dnev_pipe_config;
 703                 struct dn_rule_mini_config _dnev_rule_config;
 704         } dn_event;
 705 };
 706
 707 #define dn_event_pipe_config    dn_event._dnev_pipe_config
 708 #define dn_event_rule_config    dn_event._dnev_rule_config
 709
 710 extern void dummynet_event_enqueue_nwk_wq_entry(struct dummynet_event *);
 711
 712 enum {
 713         DUMMYNET_RULE_CONFIG,
 714         DUMMYNET_RULE_DELETE,
 715         DUMMYNET_PIPE_CONFIG,
 716         DUMMYNET_PIPE_DELETE,
 717         DUMMYNET_NLC_DISABLED,
 718 };
 719
 720 enum    { DN_INOUT, DN_IN, DN_OUT };
 721 /*
 722  * The signature for the callback is:
 723  * eventhandler_entry_arg       __unused
 724  * dummynet_event               pointer to dummynet event object
 725  */
 726 typedef void (*dummynet_event_fn) (struct eventhandler_entry_arg, struct dummynet_event *);
 727 EVENTHANDLER_DECLARE(dummynet_event, dummynet_event_fn);
 728 #endif /* BSD_KERNEL_PRIVATE */
 729 #endif /* PRIVATE */
 730 #endif /* _IP_DUMMYNET_H */