dummynet2/ip_dummynet.c

   1 /*-
   2  * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
   3  * Portions Copyright (c) 2000 Akamba Corp.
   4  * All rights reserved
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  */
  27
  28 #include <sys/cdefs.h>
  29 __FBSDID("$FreeBSD: head/sys/netinet/ipfw/ip_dummynet.c 200601 2009-12-16 10:48:40Z luigi $");
  30
  31 #define DUMMYNET_DEBUG
  32
  33 #include "opt_inet6.h"
  34
  35 /*
  36  * This module implements IP dummynet, a bandwidth limiter/delay emulator
  37  * used in conjunction with the ipfw package.
  38  * Description of the data structures used is in ip_dummynet.h
  39  * Here you mainly find the following blocks of code:
  40  *  + variable declarations;
  41  *  + heap management functions;
  42  *  + scheduler and dummynet functions;
  43  *  + configuration and initialization.
  44  *
  45  * NOTA BENE: critical sections are protected by the "dummynet lock".
  46  *
  47  * Most important Changes:
  48  *
  49  * 011004: KLDable
  50  * 010124: Fixed WF2Q behaviour
  51  * 010122: Fixed spl protection.
  52  * 000601: WF2Q support
  53  * 000106: large rewrite, use heaps to handle very many pipes.
  54  * 980513:      initial release
  55  *
  56  * include files marked with XXX are probably not needed
  57  */
  58
  59 #include <sys/param.h>
  60 #include <sys/systm.h>
  61 #include <sys/malloc.h>
  62 #include <sys/mbuf.h>
  63 #include <sys/kernel.h>
  64 #include <sys/lock.h>
  65 #include <sys/module.h>
  66 #include <sys/priv.h>
  67 #include <sys/proc.h>
  68 #include <sys/rwlock.h>
  69 #include <sys/socket.h>
  70 #include <sys/socketvar.h>
  71 #include <sys/time.h>
  72 #include <sys/sysctl.h>
  73 #include <sys/taskqueue.h>
  74 #include <net/if.h>     /* IFNAMSIZ, struct ifaddr, ifq head, lock.h mutex.h */
  75 #include <net/netisr.h>
  76 #include <netinet/in.h>
  77 #include <netinet/ip.h>         /* ip_len, ip_off */
  78 #include <netinet/ip_fw.h>
  79 #include <netinet/ipfw/ip_fw_private.h>
  80 #include <netinet/ip_dummynet.h>
  81 #include <netinet/ip_var.h>     /* ip_output(), IP_FORWARDING */
  82
  83 #include <netinet/if_ether.h> /* various ether_* routines */
  84
  85 #include <netinet/ip6.h>       /* for ip6_input, ip6_output prototypes */
  86 #include <netinet6/ip6_var.h>
  87
  88 /*
  89  * We keep a private variable for the simulation time, but we could
  90  * probably use an existing one ("softticks" in sys/kern/kern_timeout.c)
  91  */
  92 static dn_key curr_time = 0 ; /* current simulation time */
  93
  94 static int dn_hash_size = 64 ;  /* default hash size */
  95
  96 /* statistics on number of queue searches and search steps */
  97 static long searches, search_steps ;
  98 static int pipe_expire = 1 ;   /* expire queue if empty */
  99 static int dn_max_ratio = 16 ; /* max queues/buckets ratio */
 100
 101 static long pipe_slot_limit = 100; /* Foot shooting limit for pipe queues. */
 102 static long pipe_byte_limit = 1024 * 1024;
 103
 104 static int red_lookup_depth = 256;      /* RED - default lookup table depth */
 105 static int red_avg_pkt_size = 512;      /* RED - default medium packet size */
 106 static int red_max_pkt_size = 1500;     /* RED - default max packet size */
 107
 108 static struct timeval prev_t, t;
 109 static long tick_last;                  /* Last tick duration (usec). */
 110 static long tick_delta;                 /* Last vs standard tick diff (usec). */
 111 static long tick_delta_sum;             /* Accumulated tick difference (usec).*/
 112 static long tick_adjustment;            /* Tick adjustments done. */
 113 static long tick_lost;                  /* Lost(coalesced) ticks number. */
 114 /* Adjusted vs non-adjusted curr_time difference (ticks). */
 115 static long tick_diff;
 116
 117 static int              io_fast;
 118 static unsigned long    io_pkt;
 119 static unsigned long    io_pkt_fast;
 120 static unsigned long    io_pkt_drop;
 121
 122 /*
 123  * Three heaps contain queues and pipes that the scheduler handles:
 124  *
 125  * ready_heap contains all dn_flow_queue related to fixed-rate pipes.
 126  *
 127  * wfq_ready_heap contains the pipes associated with WF2Q flows
 128  *
 129  * extract_heap contains pipes associated with delay lines.
 130  *
 131  */
 132
 133 MALLOC_DEFINE(M_DUMMYNET, "dummynet", "dummynet heap");
 134
 135 static struct dn_heap ready_heap, extract_heap, wfq_ready_heap ;
 136
 137 static int      heap_init(struct dn_heap *h, int size);
 138 static int      heap_insert (struct dn_heap *h, dn_key key1, void *p);
 139 static void     heap_extract(struct dn_heap *h, void *obj);
 140 static void     transmit_event(struct dn_pipe *pipe, struct mbuf **head,
 141                     struct mbuf **tail);
 142 static void     ready_event(struct dn_flow_queue *q, struct mbuf **head,
 143                     struct mbuf **tail);
 144 static void     ready_event_wfq(struct dn_pipe *p, struct mbuf **head,
 145                     struct mbuf **tail);
 146
 147 #define HASHSIZE        16
 148 #define HASH(num)       ((((num) >> 8) ^ ((num) >> 4) ^ (num)) & 0x0f)
 149 static struct dn_pipe_head      pipehash[HASHSIZE];     /* all pipes */
 150 static struct dn_flow_set_head  flowsethash[HASHSIZE];  /* all flowsets */
 151
 152 static struct callout dn_timeout;
 153
 154 extern  void (*bridge_dn_p)(struct mbuf *, struct ifnet *);
 155
 156 #ifdef SYSCTL_NODE
 157 SYSCTL_DECL(_net_inet);
 158 SYSCTL_DECL(_net_inet_ip);
 159
 160 SYSCTL_NODE(_net_inet_ip, OID_AUTO, dummynet, CTLFLAG_RW, 0, "Dummynet");
 161 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, hash_size,
 162     CTLFLAG_RW, &dn_hash_size, 0, "Default hash table size");
 163 #if 0   /* curr_time is 64 bit */
 164 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, curr_time,
 165     CTLFLAG_RD, &curr_time, 0, "Current tick");
 166 #endif
 167 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, ready_heap,
 168     CTLFLAG_RD, &ready_heap.size, 0, "Size of ready heap");
 169 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, extract_heap,
 170     CTLFLAG_RD, &extract_heap.size, 0, "Size of extract heap");
 171 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, searches,
 172     CTLFLAG_RD, &searches, 0, "Number of queue searches");
 173 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, search_steps,
 174     CTLFLAG_RD, &search_steps, 0, "Number of queue search steps");
 175 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, expire,
 176     CTLFLAG_RW, &pipe_expire, 0, "Expire queue if empty");
 177 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, max_chain_len,
 178     CTLFLAG_RW, &dn_max_ratio, 0,
 179     "Max ratio between dynamic queues and buckets");
 180 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_lookup_depth,
 181     CTLFLAG_RD, &red_lookup_depth, 0, "Depth of RED lookup table");
 182 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_avg_pkt_size,
 183     CTLFLAG_RD, &red_avg_pkt_size, 0, "RED Medium packet size");
 184 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, red_max_pkt_size,
 185     CTLFLAG_RD, &red_max_pkt_size, 0, "RED Max packet size");
 186 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_delta,
 187     CTLFLAG_RD, &tick_delta, 0, "Last vs standard tick difference (usec).");
 188 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_delta_sum,
 189     CTLFLAG_RD, &tick_delta_sum, 0, "Accumulated tick difference (usec).");
 190 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_adjustment,
 191     CTLFLAG_RD, &tick_adjustment, 0, "Tick adjustments done.");
 192 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_diff,
 193     CTLFLAG_RD, &tick_diff, 0,
 194     "Adjusted vs non-adjusted curr_time difference (ticks).");
 195 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, tick_lost,
 196     CTLFLAG_RD, &tick_lost, 0,
 197     "Number of ticks coalesced by dummynet taskqueue.");
 198 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, io_fast,
 199     CTLFLAG_RW, &io_fast, 0, "Enable fast dummynet io.");
 200 SYSCTL_ULONG(_net_inet_ip_dummynet, OID_AUTO, io_pkt,
 201     CTLFLAG_RD, &io_pkt, 0,
 202     "Number of packets passed to dummynet.");
 203 SYSCTL_ULONG(_net_inet_ip_dummynet, OID_AUTO, io_pkt_fast,
 204     CTLFLAG_RD, &io_pkt_fast, 0,
 205     "Number of packets bypassed dummynet scheduler.");
 206 SYSCTL_ULONG(_net_inet_ip_dummynet, OID_AUTO, io_pkt_drop,
 207     CTLFLAG_RD, &io_pkt_drop, 0,
 208     "Number of packets dropped by dummynet.");
 209 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, pipe_slot_limit,
 210     CTLFLAG_RW, &pipe_slot_limit, 0, "Upper limit in slots for pipe queue.");
 211 SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, pipe_byte_limit,
 212     CTLFLAG_RW, &pipe_byte_limit, 0, "Upper limit in bytes for pipe queue.");
 213 #endif
 214
 215 #ifdef DUMMYNET_DEBUG
 216 int     dummynet_debug = 0;
 217 #ifdef SYSCTL_NODE
 218 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, debug, CTLFLAG_RW, &dummynet_debug,
 219             0, "control debugging printfs");
 220 #endif
 221 #define DPRINTF(X)      if (dummynet_debug) printf X
 222 #else
 223 #define DPRINTF(X)
 224 #endif
 225
 226 static struct task      dn_task;
 227 static struct taskqueue *dn_tq = NULL;
 228 static void dummynet_task(void *, int);
 229
 230 #if defined( __linux__ ) || defined( _WIN32 )
 231 static DEFINE_SPINLOCK(dummynet_mtx);
 232 #else
 233 static struct mtx dummynet_mtx;
 234 #endif
 235 #define DUMMYNET_LOCK_INIT() \
 236         mtx_init(&dummynet_mtx, "dummynet", NULL, MTX_DEF)
 237 #define DUMMYNET_LOCK_DESTROY() mtx_destroy(&dummynet_mtx)
 238 #define DUMMYNET_LOCK()         mtx_lock(&dummynet_mtx)
 239 #define DUMMYNET_UNLOCK()       mtx_unlock(&dummynet_mtx)
 240 #define DUMMYNET_LOCK_ASSERT()  mtx_assert(&dummynet_mtx, MA_OWNED)
 241
 242 static int      config_pipe(struct dn_pipe *p);
 243 static int      ip_dn_ctl(struct sockopt *sopt);
 244
 245 static void     dummynet(void *);
 246 static void     dummynet_flush(void);
 247 static void     dummynet_send(struct mbuf *);
 248 void            dummynet_drain(void);
 249 static int      dummynet_io(struct mbuf **, int , struct ip_fw_args *);
 250
 251 /*
 252  * Flow queue is idle if:
 253  *   1) it's empty for at least 1 tick
 254  *   2) it has invalid timestamp (WF2Q case)
 255  *   3) parent pipe has no 'exhausted' burst.
 256  */
 257 #define QUEUE_IS_IDLE(q) ((q)->head == NULL && (q)->S == (q)->F + 1 && \
 258         curr_time > (q)->idle_time + 1 && \
 259         ((q)->numbytes + (curr_time - (q)->idle_time - 1) * \
 260         (q)->fs->pipe->bandwidth >= (q)->fs->pipe->burst))
 261
 262 /*
 263  * Heap management functions.
 264  *
 265  * In the heap, first node is element 0. Children of i are 2i+1 and 2i+2.
 266  * Some macros help finding parent/children so we can optimize them.
 267  *
 268  * heap_init() is called to expand the heap when needed.
 269  * Increment size in blocks of 16 entries.
 270  * XXX failure to allocate a new element is a pretty bad failure
 271  * as we basically stall a whole queue forever!!
 272  * Returns 1 on error, 0 on success
 273  */
 274 #define HEAP_FATHER(x) ( ( (x) - 1 ) / 2 )
 275 #define HEAP_LEFT(x) ( 2*(x) + 1 )
 276 #define HEAP_IS_LEFT(x) ( (x) & 1 )
 277 #define HEAP_RIGHT(x) ( 2*(x) + 2 )
 278 #define HEAP_SWAP(a, b, buffer) { buffer = a ; a = b ; b = buffer ; }
 279 #define HEAP_INCREMENT  15
 280
 281 static int
 282 heap_init(struct dn_heap *h, int new_size)
 283 {
 284     struct dn_heap_entry *p;
 285
 286     if (h->size >= new_size ) {
 287         printf("dummynet: %s, Bogus call, have %d want %d\n", __func__,
 288                 h->size, new_size);
 289         return 0 ;
 290     }
 291     new_size = (new_size + HEAP_INCREMENT ) & ~HEAP_INCREMENT ;
 292     p = malloc(new_size * sizeof(*p), M_DUMMYNET, M_NOWAIT);
 293     if (p == NULL) {
 294         printf("dummynet: %s, resize %d failed\n", __func__, new_size );
 295         return 1 ; /* error */
 296     }
 297     if (h->size > 0) {
 298         bcopy(h->p, p, h->size * sizeof(*p) );
 299         free(h->p, M_DUMMYNET);
 300     }
 301     h->p = p ;
 302     h->size = new_size ;
 303     return 0 ;
 304 }
 305
 306 /*
 307  * Insert element in heap. Normally, p != NULL, we insert p in
 308  * a new position and bubble up. If p == NULL, then the element is
 309  * already in place, and key is the position where to start the
 310  * bubble-up.
 311  * Returns 1 on failure (cannot allocate new heap entry)
 312  *
 313  * If offset > 0 the position (index, int) of the element in the heap is
 314  * also stored in the element itself at the given offset in bytes.
 315  */
 316 #define SET_OFFSET(heap, node) \
 317     if (heap->offset > 0) \
 318             *((int *)((char *)(heap->p[node].object) + heap->offset)) = node ;
 319 /*
 320  * RESET_OFFSET is used for sanity checks. It sets offset to an invalid value.
 321  */
 322 #define RESET_OFFSET(heap, node) \
 323     if (heap->offset > 0) \
 324             *((int *)((char *)(heap->p[node].object) + heap->offset)) = -1 ;
 325 static int
 326 heap_insert(struct dn_heap *h, dn_key key1, void *p)
 327 {
 328     int son = h->elements ;
 329
 330     if (p == NULL)      /* data already there, set starting point */
 331         son = key1 ;
 332     else {              /* insert new element at the end, possibly resize */
 333         son = h->elements ;
 334         if (son == h->size) /* need resize... */
 335             if (heap_init(h, h->elements+1) )
 336                 return 1 ; /* failure... */
 337         h->p[son].object = p ;
 338         h->p[son].key = key1 ;
 339         h->elements++ ;
 340     }
 341     while (son > 0) {                           /* bubble up */
 342         int father = HEAP_FATHER(son) ;
 343         struct dn_heap_entry tmp  ;
 344
 345         if (DN_KEY_LT( h->p[father].key, h->p[son].key ) )
 346             break ; /* found right position */
 347         /* son smaller than father, swap and repeat */
 348         HEAP_SWAP(h->p[son], h->p[father], tmp) ;
 349         SET_OFFSET(h, son);
 350         son = father ;
 351     }
 352     SET_OFFSET(h, son);
 353     return 0 ;
 354 }
 355
 356 /*
 357  * remove top element from heap, or obj if obj != NULL
 358  */
 359 static void
 360 heap_extract(struct dn_heap *h, void *obj)
 361 {
 362     int child, father, max = h->elements - 1 ;
 363
 364     if (max < 0) {
 365         printf("dummynet: warning, extract from empty heap 0x%p\n", h);
 366         return ;
 367     }
 368     father = 0 ; /* default: move up smallest child */
 369     if (obj != NULL) { /* extract specific element, index is at offset */
 370         if (h->offset <= 0)
 371             panic("dummynet: heap_extract from middle not supported on this heap!!!\n");
 372         father = *((int *)((char *)obj + h->offset)) ;
 373         if (father < 0 || father >= h->elements) {
 374             printf("dummynet: heap_extract, father %d out of bound 0..%d\n",
 375                 father, h->elements);
 376             panic("dummynet: heap_extract");
 377         }
 378     }
 379     RESET_OFFSET(h, father);
 380     child = HEAP_LEFT(father) ;         /* left child */
 381     while (child <= max) {              /* valid entry */
 382         if (child != max && DN_KEY_LT(h->p[child+1].key, h->p[child].key) )
 383             child = child+1 ;           /* take right child, otherwise left */
 384         h->p[father] = h->p[child] ;
 385         SET_OFFSET(h, father);
 386         father = child ;
 387         child = HEAP_LEFT(child) ;   /* left child for next loop */
 388     }
 389     h->elements-- ;
 390     if (father != max) {
 391         /*
 392          * Fill hole with last entry and bubble up, reusing the insert code
 393          */
 394         h->p[father] = h->p[max] ;
 395         heap_insert(h, father, NULL); /* this one cannot fail */
 396     }
 397 }
 398
 399 #if 0
 400 /*
 401  * change object position and update references
 402  * XXX this one is never used!
 403  */
 404 static void
 405 heap_move(struct dn_heap *h, dn_key new_key, void *object)
 406 {
 407     int temp;
 408     int i ;
 409     int max = h->elements-1 ;
 410     struct dn_heap_entry buf ;
 411
 412     if (h->offset <= 0)
 413         panic("cannot move items on this heap");
 414
 415     i = *((int *)((char *)object + h->offset));
 416     if (DN_KEY_LT(new_key, h->p[i].key) ) { /* must move up */
 417         h->p[i].key = new_key ;
 418         for (; i>0 && DN_KEY_LT(new_key, h->p[(temp = HEAP_FATHER(i))].key) ;
 419                  i = temp ) { /* bubble up */
 420             HEAP_SWAP(h->p[i], h->p[temp], buf) ;
 421             SET_OFFSET(h, i);
 422         }
 423     } else {            /* must move down */
 424         h->p[i].key = new_key ;
 425         while ( (temp = HEAP_LEFT(i)) <= max ) { /* found left child */
 426             if ((temp != max) && DN_KEY_GT(h->p[temp].key, h->p[temp+1].key))
 427                 temp++ ; /* select child with min key */
 428             if (DN_KEY_GT(new_key, h->p[temp].key)) { /* go down */
 429                 HEAP_SWAP(h->p[i], h->p[temp], buf) ;
 430                 SET_OFFSET(h, i);
 431             } else
 432                 break ;
 433             i = temp ;
 434         }
 435     }
 436     SET_OFFSET(h, i);
 437 }
 438 #endif /* heap_move, unused */
 439
 440 /*
 441  * heapify() will reorganize data inside an array to maintain the
 442  * heap property. It is needed when we delete a bunch of entries.
 443  */
 444 static void
 445 heapify(struct dn_heap *h)
 446 {
 447     int i ;
 448
 449     for (i = 0 ; i < h->elements ; i++ )
 450         heap_insert(h, i , NULL) ;
 451 }
 452
 453 /*
 454  * cleanup the heap and free data structure
 455  */
 456 static void
 457 heap_free(struct dn_heap *h)
 458 {
 459     if (h->size >0 )
 460         free(h->p, M_DUMMYNET);
 461     bzero(h, sizeof(*h) );
 462 }
 463
 464 /*
 465  * --- end of heap management functions ---
 466  */
 467
 468 /*
 469  * Dispose a list of packet. Use an inline functions so if we
 470  * need to free extra state associated to a packet, this is a
 471  * central point to do it.
 472  */
 473
 474 static __inline void dn_free_pkts(struct mbuf *mnext)
 475 {
 476         struct mbuf *m;
 477
 478         while ((m = mnext) != NULL) {
 479                 mnext = m->m_nextpkt;
 480                 FREE_PKT(m);
 481         }
 482 }
 483
 484 /*
 485  * Return the mbuf tag holding the dummynet state.  As an optimization
 486  * this is assumed to be the first tag on the list.  If this turns out
 487  * wrong we'll need to search the list.
 488  */
 489 static struct dn_pkt_tag *
 490 dn_tag_get(struct mbuf *m)
 491 {
 492     struct m_tag *mtag = m_tag_first(m);
 493     KASSERT(mtag != NULL &&
 494             mtag->m_tag_cookie == MTAG_ABI_COMPAT &&
 495             mtag->m_tag_id == PACKET_TAG_DUMMYNET,
 496             ("packet on dummynet queue w/o dummynet tag!"));
 497     return (struct dn_pkt_tag *)(mtag+1);
 498 }
 499
 500 /*
 501  * Scheduler functions:
 502  *
 503  * transmit_event() is called when the delay-line needs to enter
 504  * the scheduler, either because of existing pkts getting ready,
 505  * or new packets entering the queue. The event handled is the delivery
 506  * time of the packet.
 507  *
 508  * ready_event() does something similar with fixed-rate queues, and the
 509  * event handled is the finish time of the head pkt.
 510  *
 511  * wfq_ready_event() does something similar with WF2Q queues, and the
 512  * event handled is the start time of the head pkt.
 513  *
 514  * In all cases, we make sure that the data structures are consistent
 515  * before passing pkts out, because this might trigger recursive
 516  * invocations of the procedures.
 517  */
 518 static void
 519 transmit_event(struct dn_pipe *pipe, struct mbuf **head, struct mbuf **tail)
 520 {
 521         struct mbuf *m;
 522         struct dn_pkt_tag *pkt;
 523
 524         DUMMYNET_LOCK_ASSERT();
 525
 526         while ((m = pipe->head) != NULL) {
 527                 pkt = dn_tag_get(m);
 528                 if (!DN_KEY_LEQ(pkt->output_time, curr_time))
 529                         break;
 530
 531                 pipe->head = m->m_nextpkt;
 532                 if (*tail != NULL)
 533                         (*tail)->m_nextpkt = m;
 534                 else
 535                         *head = m;
 536                 *tail = m;
 537         }
 538         if (*tail != NULL)
 539                 (*tail)->m_nextpkt = NULL;
 540
 541         /* If there are leftover packets, put into the heap for next event. */
 542         if ((m = pipe->head) != NULL) {
 543                 pkt = dn_tag_get(m);
 544                 /*
 545                  * XXX Should check errors on heap_insert, by draining the
 546                  * whole pipe p and hoping in the future we are more successful.
 547                  */
 548                 heap_insert(&extract_heap, pkt->output_time, pipe);
 549         }
 550 }
 551
 552 #ifndef __linux__
 553 #define div64(a, b)     ((int64_t)(a) / (int64_t)(b))
 554 #endif
 555 /*
 556  * Compute how many ticks we have to wait before being able to send
 557  * a packet. This is computed as the "wire time" for the packet
 558  * (length + extra bits), minus the credit available, scaled to ticks.
 559  * Check that the result is not be negative (it could be if we have
 560  * too much leftover credit in q->numbytes).
 561  */
 562 static inline dn_key
 563 set_ticks(struct mbuf *m, struct dn_flow_queue *q, struct dn_pipe *p)
 564 {
 565         int64_t ret;
 566
 567         ret = div64( (m->m_pkthdr.len * 8 + q->extra_bits) * hz
 568                 - q->numbytes + p->bandwidth - 1 , p->bandwidth);
 569         if (ret < 0)
 570                 ret = 0;
 571         return ret;
 572 }
 573
 574 /*
 575  * Convert the additional MAC overheads/delays into an equivalent
 576  * number of bits for the given data rate. The samples are in milliseconds
 577  * so we need to divide by 1000.
 578  */
 579 static dn_key
 580 compute_extra_bits(struct mbuf *pkt, struct dn_pipe *p)
 581 {
 582         int index;
 583         dn_key extra_bits;
 584
 585         if (!p->samples || p->samples_no == 0)
 586                 return 0;
 587         index  = random() % p->samples_no;
 588         extra_bits = div64((dn_key)p->samples[index] * p->bandwidth, 1000);
 589         if (index >= p->loss_level) {
 590                 struct dn_pkt_tag *dt = dn_tag_get(pkt);
 591                 if (dt)
 592                         dt->dn_dir = DIR_DROP;
 593         }
 594         return extra_bits;
 595 }
 596
 597 static void
 598 free_pipe(struct dn_pipe *p)
 599 {
 600         if (p->samples)
 601                 free(p->samples, M_DUMMYNET);
 602         free(p, M_DUMMYNET);
 603 }
 604
 605 /*
 606  * extract pkt from queue, compute output time (could be now)
 607  * and put into delay line (p_queue)
 608  */
 609 static void
 610 move_pkt(struct mbuf *pkt, struct dn_flow_queue *q, struct dn_pipe *p,
 611     int len)
 612 {
 613     struct dn_pkt_tag *dt = dn_tag_get(pkt);
 614
 615     q->head = pkt->m_nextpkt ;
 616     q->len-- ;
 617     q->len_bytes -= len ;
 618
 619     dt->output_time = curr_time + p->delay ;
 620
 621     if (p->head == NULL)
 622         p->head = pkt;
 623     else
 624         p->tail->m_nextpkt = pkt;
 625     p->tail = pkt;
 626     p->tail->m_nextpkt = NULL;
 627 }
 628
 629 /*
 630  * ready_event() is invoked every time the queue must enter the
 631  * scheduler, either because the first packet arrives, or because
 632  * a previously scheduled event fired.
 633  * On invokation, drain as many pkts as possible (could be 0) and then
 634  * if there are leftover packets reinsert the pkt in the scheduler.
 635  */
 636 static void
 637 ready_event(struct dn_flow_queue *q, struct mbuf **head, struct mbuf **tail)
 638 {
 639         struct mbuf *pkt;
 640         struct dn_pipe *p = q->fs->pipe;
 641         int p_was_empty;
 642
 643         DUMMYNET_LOCK_ASSERT();
 644
 645         if (p == NULL) {
 646                 printf("dummynet: ready_event- pipe is gone\n");
 647                 return;
 648         }
 649         p_was_empty = (p->head == NULL);
 650
 651         /*
 652          * Schedule fixed-rate queues linked to this pipe:
 653          * account for the bw accumulated since last scheduling, then
 654          * drain as many pkts as allowed by q->numbytes and move to
 655          * the delay line (in p) computing output time.
 656          * bandwidth==0 (no limit) means we can drain the whole queue,
 657          * setting len_scaled = 0 does the job.
 658          */
 659         q->numbytes += (curr_time - q->sched_time) * p->bandwidth;
 660         while ((pkt = q->head) != NULL) {
 661                 int len = pkt->m_pkthdr.len;
 662                 dn_key len_scaled = p->bandwidth ? len*8*hz
 663                         + q->extra_bits*hz
 664                         : 0;
 665
 666                 if (DN_KEY_GT(len_scaled, q->numbytes))
 667                         break;
 668                 q->numbytes -= len_scaled;
 669                 move_pkt(pkt, q, p, len);
 670                 if (q->head)
 671                         q->extra_bits = compute_extra_bits(q->head, p);
 672         }
 673         /*
 674          * If we have more packets queued, schedule next ready event
 675          * (can only occur when bandwidth != 0, otherwise we would have
 676          * flushed the whole queue in the previous loop).
 677          * To this purpose we record the current time and compute how many
 678          * ticks to go for the finish time of the packet.
 679          */
 680         if ((pkt = q->head) != NULL) {  /* this implies bandwidth != 0 */
 681                 dn_key t = set_ticks(pkt, q, p); /* ticks i have to wait */
 682
 683                 q->sched_time = curr_time;
 684                 heap_insert(&ready_heap, curr_time + t, (void *)q);
 685                 /*
 686                  * XXX Should check errors on heap_insert, and drain the whole
 687                  * queue on error hoping next time we are luckier.
 688                  */
 689         } else          /* RED needs to know when the queue becomes empty. */
 690                 q->idle_time = curr_time;
 691
 692         /*
 693          * If the delay line was empty call transmit_event() now.
 694          * Otherwise, the scheduler will take care of it.
 695          */
 696         if (p_was_empty)
 697                 transmit_event(p, head, tail);
 698 }
 699
 700 /*
 701  * Called when we can transmit packets on WF2Q queues. Take pkts out of
 702  * the queues at their start time, and enqueue into the delay line.
 703  * Packets are drained until p->numbytes < 0. As long as
 704  * len_scaled >= p->numbytes, the packet goes into the delay line
 705  * with a deadline p->delay. For the last packet, if p->numbytes < 0,
 706  * there is an additional delay.
 707  */
 708 static void
 709 ready_event_wfq(struct dn_pipe *p, struct mbuf **head, struct mbuf **tail)
 710 {
 711         int p_was_empty = (p->head == NULL);
 712         struct dn_heap *sch = &(p->scheduler_heap);
 713         struct dn_heap *neh = &(p->not_eligible_heap);
 714         int64_t p_numbytes = p->numbytes;
 715
 716         /*
 717          * p->numbytes is only 32bits in FBSD7, but we might need 64 bits.
 718          * Use a local variable for the computations, and write back the
 719          * results when done, saturating if needed.
 720          * The local variable has no impact on performance and helps
 721          * reducing diffs between the various branches.
 722          */
 723
 724         DUMMYNET_LOCK_ASSERT();
 725
 726         if (p->if_name[0] == 0)         /* tx clock is simulated */
 727                 p_numbytes += (curr_time - p->sched_time) * p->bandwidth;
 728         else {  /*
 729                  * tx clock is for real,
 730                  * the ifq must be empty or this is a NOP.
 731                  */
 732 #ifdef __linux__
 733                 return;
 734 #else
 735                 if (p->ifp && p->ifp->if_snd.ifq_head != NULL)
 736                         return;
 737                 else {
 738                         DPRINTF(("dummynet: pipe %d ready from %s --\n",
 739                             p->pipe_nr, p->if_name));
 740                 }
 741 #endif
 742         }
 743
 744         /*
 745          * While we have backlogged traffic AND credit, we need to do
 746          * something on the queue.
 747          */
 748         while (p_numbytes >= 0 && (sch->elements > 0 || neh->elements > 0)) {
 749                 if (sch->elements > 0) {
 750                         /* Have some eligible pkts to send out. */
 751                         struct dn_flow_queue *q = sch->p[0].object;
 752                         struct mbuf *pkt = q->head;
 753                         struct dn_flow_set *fs = q->fs;
 754                         uint64_t len = pkt->m_pkthdr.len;
 755                         int len_scaled = p->bandwidth ? len * 8 * hz : 0;
 756
 757                         heap_extract(sch, NULL); /* Remove queue from heap. */
 758                         p_numbytes -= len_scaled;
 759                         move_pkt(pkt, q, p, len);
 760
 761                         p->V += div64((len << MY_M), p->sum);   /* Update V. */
 762                         q->S = q->F;                    /* Update start time. */
 763                         if (q->len == 0) {
 764                                 /* Flow not backlogged any more. */
 765                                 fs->backlogged--;
 766                                 heap_insert(&(p->idle_heap), q->F, q);
 767                         } else {
 768                                 /* Still backlogged. */
 769
 770                                 /*
 771                                  * Update F and position in backlogged queue,
 772                                  * then put flow in not_eligible_heap
 773                                  * (we will fix this later).
 774                                  */
 775                                 len = (q->head)->m_pkthdr.len;
 776                                 q->F += div64((len << MY_M), fs->weight);
 777                                 if (DN_KEY_LEQ(q->S, p->V))
 778                                         heap_insert(neh, q->S, q);
 779                                 else
 780                                         heap_insert(sch, q->F, q);
 781                         }
 782                 }
 783                 /*
 784                  * Now compute V = max(V, min(S_i)). Remember that all elements
 785                  * in sch have by definition S_i <= V so if sch is not empty,
 786                  * V is surely the max and we must not update it. Conversely,
 787                  * if sch is empty we only need to look at neh.
 788                  */
 789                 if (sch->elements == 0 && neh->elements > 0)
 790                         p->V = MAX64(p->V, neh->p[0].key);
 791                 /* Move from neh to sch any packets that have become eligible */
 792                 while (neh->elements > 0 && DN_KEY_LEQ(neh->p[0].key, p->V)) {
 793                         struct dn_flow_queue *q = neh->p[0].object;
 794                         heap_extract(neh, NULL);
 795                         heap_insert(sch, q->F, q);
 796                 }
 797
 798                 if (p->if_name[0] != '\0') { /* Tx clock is from a real thing */
 799                         p_numbytes = -1;        /* Mark not ready for I/O. */
 800                         break;
 801                 }
 802         }
 803         if (sch->elements == 0 && neh->elements == 0 && p_numbytes >= 0) {
 804                 p->idle_time = curr_time;
 805                 /*
 806                  * No traffic and no events scheduled.
 807                  * We can get rid of idle-heap.
 808                  */
 809                 if (p->idle_heap.elements > 0) {
 810                         int i;
 811
 812                         for (i = 0; i < p->idle_heap.elements; i++) {
 813                                 struct dn_flow_queue *q;
 814
 815                                 q = p->idle_heap.p[i].object;
 816                                 q->F = 0;
 817                                 q->S = q->F + 1;
 818                         }
 819                         p->sum = 0;
 820                         p->V = 0;
 821                         p->idle_heap.elements = 0;
 822                 }
 823         }
 824         /*
 825          * If we are getting clocks from dummynet (not a real interface) and
 826          * If we are under credit, schedule the next ready event.
 827          * Also fix the delivery time of the last packet.
 828          */
 829         if (p->if_name[0]==0 && p_numbytes < 0) { /* This implies bw > 0. */
 830                 dn_key t = 0;           /* Number of ticks i have to wait. */
 831
 832                 if (p->bandwidth > 0)
 833                         t = div64(p->bandwidth - 1 - p_numbytes, p->bandwidth);
 834                 dn_tag_get(p->tail)->output_time += t;
 835                 p->sched_time = curr_time;
 836                 heap_insert(&wfq_ready_heap, curr_time + t, (void *)p);
 837                 /*
 838                  * XXX Should check errors on heap_insert, and drain the whole
 839                  * queue on error hoping next time we are luckier.
 840                  */
 841         }
 842
 843         /* Write back p_numbytes (adjust 64->32bit if necessary). */
 844         p->numbytes = p_numbytes;
 845
 846         /*
 847          * If the delay line was empty call transmit_event() now.
 848          * Otherwise, the scheduler will take care of it.
 849          */
 850         if (p_was_empty)
 851                 transmit_event(p, head, tail);
 852 }
 853
 854 /*
 855  * This is called one tick, after previous run. It is used to
 856  * schedule next run.
 857  */
 858 static void
 859 dummynet(void * __unused unused)
 860 {
 861
 862         taskqueue_enqueue(dn_tq, &dn_task);
 863 }
 864
 865 /*
 866  * The main dummynet processing function.
 867  */
 868 static void
 869 dummynet_task(void *context, int pending)
 870 {
 871         struct mbuf *head = NULL, *tail = NULL;
 872         struct dn_pipe *pipe;
 873         struct dn_heap *heaps[3];
 874         struct dn_heap *h;
 875         void *p;        /* generic parameter to handler */
 876         int i;
 877
 878         DUMMYNET_LOCK();
 879
 880         heaps[0] = &ready_heap;                 /* fixed-rate queues */
 881         heaps[1] = &wfq_ready_heap;             /* wfq queues */
 882         heaps[2] = &extract_heap;               /* delay line */
 883
 884         /* Update number of lost(coalesced) ticks. */
 885         tick_lost += pending - 1;
 886
 887         getmicrouptime(&t);
 888         /* Last tick duration (usec). */
 889         tick_last = (t.tv_sec - prev_t.tv_sec) * 1000000 +
 890             (t.tv_usec - prev_t.tv_usec);
 891         /* Last tick vs standard tick difference (usec). */
 892         tick_delta = (tick_last * hz - 1000000) / hz;
 893         /* Accumulated tick difference (usec). */
 894         tick_delta_sum += tick_delta;
 895
 896         prev_t = t;
 897
 898         /*
 899          * Adjust curr_time if accumulated tick difference greater than
 900          * 'standard' tick. Since curr_time should be monotonically increasing,
 901          * we do positive adjustment as required and throttle curr_time in
 902          * case of negative adjustment.
 903          */
 904         curr_time++;
 905         if (tick_delta_sum - tick >= 0) {
 906                 int diff = tick_delta_sum / tick;
 907
 908                 curr_time += diff;
 909                 tick_diff += diff;
 910                 tick_delta_sum %= tick;
 911                 tick_adjustment++;
 912         } else if (tick_delta_sum + tick <= 0) {
 913                 curr_time--;
 914                 tick_diff--;
 915                 tick_delta_sum += tick;
 916                 tick_adjustment++;
 917         }
 918
 919         for (i = 0; i < 3; i++) {
 920                 h = heaps[i];
 921                 while (h->elements > 0 && DN_KEY_LEQ(h->p[0].key, curr_time)) {
 922                         if (h->p[0].key > curr_time)
 923                                 printf("dummynet: warning, "
 924                                     "heap %d is %d ticks late\n",
 925                                     i, (int)(curr_time - h->p[0].key));
 926                         /* store a copy before heap_extract */
 927                         p = h->p[0].object;
 928                         /* need to extract before processing */
 929                         heap_extract(h, NULL);
 930                         if (i == 0)
 931                                 ready_event(p, &head, &tail);
 932                         else if (i == 1) {
 933                                 struct dn_pipe *pipe = p;
 934                                 if (pipe->if_name[0] != '\0')
 935                                         printf("dummynet: bad ready_event_wfq "
 936                                             "for pipe %s\n", pipe->if_name);
 937                                 else
 938                                         ready_event_wfq(p, &head, &tail);
 939                         } else
 940                                 transmit_event(p, &head, &tail);
 941                 }
 942         }
 943
 944         /* Sweep pipes trying to expire idle flow_queues. */
 945         for (i = 0; i < HASHSIZE; i++) {
 946                 SLIST_FOREACH(pipe, &pipehash[i], next) {
 947                         if (pipe->idle_heap.elements > 0 &&
 948                             DN_KEY_LT(pipe->idle_heap.p[0].key, pipe->V)) {
 949                                 struct dn_flow_queue *q =
 950                                     pipe->idle_heap.p[0].object;
 951
 952                                 heap_extract(&(pipe->idle_heap), NULL);
 953                                 /* Mark timestamp as invalid. */
 954                                 q->S = q->F + 1;
 955                                 pipe->sum -= q->fs->weight;
 956                         }
 957                 }
 958         }
 959
 960         DUMMYNET_UNLOCK();
 961
 962         if (head != NULL)
 963                 dummynet_send(head);
 964
 965         callout_reset(&dn_timeout, 1, dummynet, NULL);
 966 }
 967
 968 static void
 969 dummynet_send(struct mbuf *m)
 970 {
 971         struct mbuf *n;
 972
 973         for (; m != NULL; m = n) {
 974                 struct ifnet *ifp = NULL;
 975                 int dst;
 976                 struct m_tag *tag;
 977
 978                 n = m->m_nextpkt;
 979                 m->m_nextpkt = NULL;
 980                 tag = m_tag_first(m);
 981                 if (tag == NULL) {
 982                         dst = DIR_DROP;
 983                 } else {
 984                         struct dn_pkt_tag *pkt = dn_tag_get(m);
 985                         /* extract the dummynet info, rename the tag */
 986                         dst = pkt->dn_dir;
 987                         ifp = pkt->ifp;
 988                         /* rename the tag so it carries reinject info */
 989                         tag->m_tag_cookie = MTAG_IPFW_RULE;
 990                         tag->m_tag_id = 0;
 991                 }
 992
 993                 switch (dst) {
 994                 case DIR_OUT:
 995                         SET_HOST_IPLEN(mtod(m, struct ip *));
 996                         ip_output(m, NULL, NULL, IP_FORWARDING, NULL, NULL);
 997                         break ;
 998                 case DIR_IN :
 999                         /* put header in network format for ip_input() */
1000                         //SET_NET_IPLEN(mtod(m, struct ip *));
1001                         netisr_dispatch(NETISR_IP, m);
1002                         break;
1003 #ifdef INET6
1004                 case DIR_IN | PROTO_IPV6:
1005                         netisr_dispatch(NETISR_IPV6, m);
1006                         break;
1007
1008                 case DIR_OUT | PROTO_IPV6:
1009                         SET_HOST_IPLEN(mtod(m, struct ip *));
1010                         ip6_output(m, NULL, NULL, IPV6_FORWARDING, NULL, NULL, NULL);
1011                         break;
1012 #endif
1013                 case DIR_FWD | PROTO_IFB: /* DN_TO_IFB_FWD: */
1014                         if (bridge_dn_p != NULL)
1015                                 ((*bridge_dn_p)(m, ifp));
1016                         else
1017                                 printf("dummynet: if_bridge not loaded\n");
1018
1019                         break;
1020                 case DIR_IN | PROTO_LAYER2: /* DN_TO_ETH_DEMUX: */
1021                         /*
1022                          * The Ethernet code assumes the Ethernet header is
1023                          * contiguous in the first mbuf header.
1024                          * Insure this is true.
1025                          */
1026                         if (m->m_len < ETHER_HDR_LEN &&
1027                             (m = m_pullup(m, ETHER_HDR_LEN)) == NULL) {
1028                                 printf("dummynet/ether: pullup failed, "
1029                                     "dropping packet\n");
1030                                 break;
1031                         }
1032                         ether_demux(m->m_pkthdr.rcvif, m);
1033                         break;
1034                 case DIR_OUT | PROTO_LAYER2: /* N_TO_ETH_OUT: */
1035                         ether_output_frame(ifp, m);
1036                         break;
1037
1038                 case DIR_DROP:
1039                         /* drop the packet after some time */
1040                         FREE_PKT(m);
1041                         break;
1042
1043                 default:
1044                         printf("dummynet: bad switch %d!\n", dst);
1045                         FREE_PKT(m);
1046                         break;
1047                 }
1048         }
1049 }
1050
1051 /*
1052  * Unconditionally expire empty queues in case of shortage.
1053  * Returns the number of queues freed.
1054  */
1055 static int
1056 expire_queues(struct dn_flow_set *fs)
1057 {
1058     struct dn_flow_queue *q, *prev ;
1059     int i, initial_elements = fs->rq_elements ;
1060
1061     if (fs->last_expired == time_uptime)
1062         return 0 ;
1063     fs->last_expired = time_uptime ;
1064     for (i = 0 ; i <= fs->rq_size ; i++) { /* last one is overflow */
1065         for (prev=NULL, q = fs->rq[i] ; q != NULL ; ) {
1066             if (!QUEUE_IS_IDLE(q)) {
1067                 prev = q ;
1068                 q = q->next ;
1069             } else { /* entry is idle, expire it */
1070                 struct dn_flow_queue *old_q = q ;
1071
1072                 if (prev != NULL)
1073                     prev->next = q = q->next ;
1074                 else
1075                     fs->rq[i] = q = q->next ;
1076                 fs->rq_elements-- ;
1077                 free(old_q, M_DUMMYNET);
1078             }
1079         }
1080     }
1081     return initial_elements - fs->rq_elements ;
1082 }
1083
1084 /*
1085  * If room, create a new queue and put at head of slot i;
1086  * otherwise, create or use the default queue.
1087  */
1088 static struct dn_flow_queue *
1089 create_queue(struct dn_flow_set *fs, int i)
1090 {
1091         struct dn_flow_queue *q;
1092
1093         if (fs->rq_elements > fs->rq_size * dn_max_ratio &&
1094             expire_queues(fs) == 0) {
1095                 /* No way to get room, use or create overflow queue. */
1096                 i = fs->rq_size;
1097                 if (fs->rq[i] != NULL)
1098                     return fs->rq[i];
1099         }
1100         q = malloc(sizeof(*q), M_DUMMYNET, M_NOWAIT | M_ZERO);
1101         if (q == NULL) {
1102                 printf("dummynet: sorry, cannot allocate queue for new flow\n");
1103                 return (NULL);
1104         }
1105         q->fs = fs;
1106         q->hash_slot = i;
1107         q->next = fs->rq[i];
1108         q->S = q->F + 1;        /* hack - mark timestamp as invalid. */
1109         q->numbytes = fs->pipe->burst + (io_fast ? fs->pipe->bandwidth : 0);
1110         fs->rq[i] = q;
1111         fs->rq_elements++;
1112         return (q);
1113 }
1114
1115 /*
1116  * Given a flow_set and a pkt in last_pkt, find a matching queue
1117  * after appropriate masking. The queue is moved to front
1118  * so that further searches take less time.
1119  */
1120 static struct dn_flow_queue *
1121 find_queue(struct dn_flow_set *fs, struct ipfw_flow_id *id)
1122 {
1123     int i = 0 ; /* we need i and q for new allocations */
1124     struct dn_flow_queue *q, *prev;
1125     int is_v6 = IS_IP6_FLOW_ID(id);
1126
1127     if ( !(fs->flags_fs & DN_HAVE_FLOW_MASK) )
1128         q = fs->rq[0] ;
1129     else {
1130         /* first, do the masking, then hash */
1131         id->dst_port &= fs->flow_mask.dst_port ;
1132         id->src_port &= fs->flow_mask.src_port ;
1133         id->proto &= fs->flow_mask.proto ;
1134         id->flags = 0 ; /* we don't care about this one */
1135         if (is_v6) {
1136             APPLY_MASK(&id->dst_ip6, &fs->flow_mask.dst_ip6);
1137             APPLY_MASK(&id->src_ip6, &fs->flow_mask.src_ip6);
1138             id->flow_id6 &= fs->flow_mask.flow_id6;
1139
1140             i = ((id->dst_ip6.__u6_addr.__u6_addr32[0]) & 0xffff)^
1141                 ((id->dst_ip6.__u6_addr.__u6_addr32[1]) & 0xffff)^
1142                 ((id->dst_ip6.__u6_addr.__u6_addr32[2]) & 0xffff)^
1143                 ((id->dst_ip6.__u6_addr.__u6_addr32[3]) & 0xffff)^
1144
1145                 ((id->dst_ip6.__u6_addr.__u6_addr32[0] >> 15) & 0xffff)^
1146                 ((id->dst_ip6.__u6_addr.__u6_addr32[1] >> 15) & 0xffff)^
1147                 ((id->dst_ip6.__u6_addr.__u6_addr32[2] >> 15) & 0xffff)^
1148                 ((id->dst_ip6.__u6_addr.__u6_addr32[3] >> 15) & 0xffff)^
1149
1150                 ((id->src_ip6.__u6_addr.__u6_addr32[0] << 1) & 0xfffff)^
1151                 ((id->src_ip6.__u6_addr.__u6_addr32[1] << 1) & 0xfffff)^
1152                 ((id->src_ip6.__u6_addr.__u6_addr32[2] << 1) & 0xfffff)^
1153                 ((id->src_ip6.__u6_addr.__u6_addr32[3] << 1) & 0xfffff)^
1154
1155                 ((id->src_ip6.__u6_addr.__u6_addr32[0] << 16) & 0xffff)^
1156                 ((id->src_ip6.__u6_addr.__u6_addr32[1] << 16) & 0xffff)^
1157                 ((id->src_ip6.__u6_addr.__u6_addr32[2] << 16) & 0xffff)^
1158                 ((id->src_ip6.__u6_addr.__u6_addr32[3] << 16) & 0xffff)^
1159
1160                 (id->dst_port << 1) ^ (id->src_port) ^
1161                 (id->proto ) ^
1162                 (id->flow_id6);
1163         } else {
1164             id->dst_ip &= fs->flow_mask.dst_ip ;
1165             id->src_ip &= fs->flow_mask.src_ip ;
1166
1167             i = ( (id->dst_ip) & 0xffff ) ^
1168                 ( (id->dst_ip >> 15) & 0xffff ) ^
1169                 ( (id->src_ip << 1) & 0xffff ) ^
1170                 ( (id->src_ip >> 16 ) & 0xffff ) ^
1171                 (id->dst_port << 1) ^ (id->src_port) ^
1172                 (id->proto );
1173         }
1174         i = i % fs->rq_size ;
1175         /* finally, scan the current list for a match */
1176         searches++ ;
1177         for (prev=NULL, q = fs->rq[i] ; q ; ) {
1178             search_steps++;
1179             if (is_v6 &&
1180                     IN6_ARE_ADDR_EQUAL(&id->dst_ip6,&q->id.dst_ip6) &&
1181                     IN6_ARE_ADDR_EQUAL(&id->src_ip6,&q->id.src_ip6) &&
1182                     id->dst_port == q->id.dst_port &&
1183                     id->src_port == q->id.src_port &&
1184                     id->proto == q->id.proto &&
1185                     id->flags == q->id.flags &&
1186                     id->flow_id6 == q->id.flow_id6)
1187                 break ; /* found */
1188
1189             if (!is_v6 && id->dst_ip == q->id.dst_ip &&
1190                     id->src_ip == q->id.src_ip &&
1191                     id->dst_port == q->id.dst_port &&
1192                     id->src_port == q->id.src_port &&
1193                     id->proto == q->id.proto &&
1194                     id->flags == q->id.flags)
1195                 break ; /* found */
1196
1197             /* No match. Check if we can expire the entry */
1198             if (pipe_expire && QUEUE_IS_IDLE(q)) {
1199                 /* entry is idle and not in any heap, expire it */
1200                 struct dn_flow_queue *old_q = q ;
1201
1202                 if (prev != NULL)
1203                     prev->next = q = q->next ;
1204                 else
1205                     fs->rq[i] = q = q->next ;
1206                 fs->rq_elements-- ;
1207                 free(old_q, M_DUMMYNET);
1208                 continue ;
1209             }
1210             prev = q ;
1211             q = q->next ;
1212         }
1213         if (q && prev != NULL) { /* found and not in front */
1214             prev->next = q->next ;
1215             q->next = fs->rq[i] ;
1216             fs->rq[i] = q ;
1217         }
1218     }
1219     if (q == NULL) { /* no match, need to allocate a new entry */
1220         q = create_queue(fs, i);
1221         if (q != NULL)
1222         q->id = *id ;
1223     }
1224     return q ;
1225 }
1226
1227 static int
1228 red_drops(struct dn_flow_set *fs, struct dn_flow_queue *q, int len)
1229 {
1230         /*
1231          * RED algorithm
1232          *
1233          * RED calculates the average queue size (avg) using a low-pass filter
1234          * with an exponential weighted (w_q) moving average:
1235          *      avg  <-  (1-w_q) * avg + w_q * q_size
1236          * where q_size is the queue length (measured in bytes or * packets).
1237          *
1238          * If q_size == 0, we compute the idle time for the link, and set
1239          *      avg = (1 - w_q)^(idle/s)
1240          * where s is the time needed for transmitting a medium-sized packet.
1241          *
1242          * Now, if avg < min_th the packet is enqueued.
1243          * If avg > max_th the packet is dropped. Otherwise, the packet is
1244          * dropped with probability P function of avg.
1245          */
1246
1247         int64_t p_b = 0;
1248
1249         /* Queue in bytes or packets? */
1250         u_int q_size = (fs->flags_fs & DN_QSIZE_IS_BYTES) ?
1251             q->len_bytes : q->len;
1252
1253         DPRINTF(("\ndummynet: %d q: %2u ", (int)curr_time, q_size));
1254
1255         /* Average queue size estimation. */
1256         if (q_size != 0) {
1257                 /* Queue is not empty, avg <- avg + (q_size - avg) * w_q */
1258                 int diff = SCALE(q_size) - q->avg;
1259                 int64_t v = SCALE_MUL((int64_t)diff, (int64_t)fs->w_q);
1260
1261                 q->avg += (int)v;
1262         } else {
1263                 /*
1264                  * Queue is empty, find for how long the queue has been
1265                  * empty and use a lookup table for computing
1266                  * (1 - * w_q)^(idle_time/s) where s is the time to send a
1267                  * (small) packet.
1268                  * XXX check wraps...
1269                  */
1270                 if (q->avg) {
1271                         u_int t = div64(curr_time - q->idle_time,
1272                             fs->lookup_step);
1273
1274                         q->avg = (t < fs->lookup_depth) ?
1275                             SCALE_MUL(q->avg, fs->w_q_lookup[t]) : 0;
1276                 }
1277         }
1278         DPRINTF(("dummynet: avg: %u ", SCALE_VAL(q->avg)));
1279
1280         /* Should i drop? */
1281         if (q->avg < fs->min_th) {
1282                 q->count = -1;
1283                 return (0);     /* accept packet */
1284         }
1285         if (q->avg >= fs->max_th) {     /* average queue >=  max threshold */
1286                 if (fs->flags_fs & DN_IS_GENTLE_RED) {
1287                         /*
1288                          * According to Gentle-RED, if avg is greater than
1289                          * max_th the packet is dropped with a probability
1290                          *       p_b = c_3 * avg - c_4
1291                          * where c_3 = (1 - max_p) / max_th
1292                          *       c_4 = 1 - 2 * max_p
1293                          */
1294                         p_b = SCALE_MUL((int64_t)fs->c_3, (int64_t)q->avg) -
1295                             fs->c_4;
1296                 } else {
1297                         q->count = -1;
1298                         DPRINTF(("dummynet: - drop"));
1299                         return (1);
1300                 }
1301         } else if (q->avg > fs->min_th) {
1302                 /*
1303                  * We compute p_b using the linear dropping function
1304                  *       p_b = c_1 * avg - c_2
1305                  * where c_1 = max_p / (max_th - min_th)
1306                  *       c_2 = max_p * min_th / (max_th - min_th)
1307                  */
1308                 p_b = SCALE_MUL((int64_t)fs->c_1, (int64_t)q->avg) - fs->c_2;
1309         }
1310
1311         if (fs->flags_fs & DN_QSIZE_IS_BYTES)
1312                 p_b = div64(p_b * len, fs->max_pkt_size);
1313         if (++q->count == 0)
1314                 q->random = random() & 0xffff;
1315         else {
1316                 /*
1317                  * q->count counts packets arrived since last drop, so a greater
1318                  * value of q->count means a greater packet drop probability.
1319                  */
1320                 if (SCALE_MUL(p_b, SCALE((int64_t)q->count)) > q->random) {
1321                         q->count = 0;
1322                         DPRINTF(("dummynet: - red drop"));
1323                         /* After a drop we calculate a new random value. */
1324                         q->random = random() & 0xffff;
1325                         return (1);     /* drop */
1326                 }
1327         }
1328         /* End of RED algorithm. */
1329
1330         return (0);     /* accept */
1331 }
1332
1333 static __inline struct dn_flow_set *
1334 locate_flowset(int fs_nr)
1335 {
1336         struct dn_flow_set *fs;
1337
1338         SLIST_FOREACH(fs, &flowsethash[HASH(fs_nr)], next)
1339                 if (fs->fs_nr == fs_nr)
1340                         return (fs);
1341
1342         return (NULL);
1343 }
1344
1345 static __inline struct dn_pipe *
1346 locate_pipe(int pipe_nr)
1347 {
1348         struct dn_pipe *pipe;
1349
1350         SLIST_FOREACH(pipe, &pipehash[HASH(pipe_nr)], next)
1351                 if (pipe->pipe_nr == pipe_nr)
1352                         return (pipe);
1353
1354         return (NULL);
1355 }
1356
1357 /*
1358  * dummynet hook for packets. Below 'pipe' is a pipe or a queue
1359  * depending on whether WF2Q or fixed bw is used.
1360  *
1361  * pipe_nr      pipe or queue the packet is destined for.
1362  * dir          where shall we send the packet after dummynet.
1363  * m            the mbuf with the packet
1364  * ifp          the 'ifp' parameter from the caller.
1365  *              NULL in ip_input, destination interface in ip_output,
1366  * rule         matching rule, in case of multiple passes
1367  */
1368 static int
1369 dummynet_io(struct mbuf **m0, int dir, struct ip_fw_args *fwa)
1370 {
1371         struct mbuf *m = *m0, *head = NULL, *tail = NULL;
1372         struct dn_pkt_tag *pkt;
1373         struct m_tag *mtag;
1374         struct dn_flow_set *fs = NULL;
1375         struct dn_pipe *pipe;
1376         uint64_t len = m->m_pkthdr.len;
1377         struct dn_flow_queue *q = NULL;
1378         int is_pipe = fwa->rule.info & IPFW_IS_PIPE;
1379
1380         KASSERT(m->m_nextpkt == NULL,
1381             ("dummynet_io: mbuf queue passed to dummynet"));
1382
1383         DUMMYNET_LOCK();
1384         io_pkt++;
1385         /*
1386          * This is a dummynet rule, so we expect an O_PIPE or O_QUEUE rule.
1387          */
1388         if (is_pipe) {
1389                 pipe = locate_pipe(fwa->rule.info & IPFW_INFO_MASK);
1390                 if (pipe != NULL)
1391                         fs = &(pipe->fs);
1392         } else
1393                 fs = locate_flowset(fwa->rule.info & IPFW_INFO_MASK);
1394
1395         if (fs == NULL)
1396                 goto dropit;    /* This queue/pipe does not exist! */
1397         pipe = fs->pipe;
1398         if (pipe == NULL) {     /* Must be a queue, try find a matching pipe. */
1399                 pipe = locate_pipe(fs->parent_nr);
1400                 if (pipe != NULL)
1401                         fs->pipe = pipe;
1402                 else {
1403                         printf("dummynet: no pipe %d for queue %d, drop pkt\n",
1404                             fs->parent_nr, fs->fs_nr);
1405                         goto dropit;
1406                 }
1407         }
1408         q = find_queue(fs, &(fwa->f_id));
1409         if (q == NULL)
1410                 goto dropit;            /* Cannot allocate queue. */
1411
1412         /* Update statistics, then check reasons to drop pkt. */
1413         q->tot_bytes += len;
1414         q->tot_pkts++;
1415         if (fs->plr && random() < fs->plr)
1416                 goto dropit;            /* Random pkt drop. */
1417         if (fs->flags_fs & DN_QSIZE_IS_BYTES) {
1418                 if (q->len_bytes > fs->qsize)
1419                         goto dropit;    /* Queue size overflow. */
1420         } else {
1421                 if (q->len >= fs->qsize)
1422                         goto dropit;    /* Queue count overflow. */
1423         }
1424         if (fs->flags_fs & DN_IS_RED && red_drops(fs, q, len))
1425                 goto dropit;
1426
1427         /* XXX expensive to zero, see if we can remove it. */
1428         mtag = m_tag_get(PACKET_TAG_DUMMYNET,
1429             sizeof(struct dn_pkt_tag), M_NOWAIT | M_ZERO);
1430         if (mtag == NULL)
1431                 goto dropit;            /* Cannot allocate packet header. */
1432         m_tag_prepend(m, mtag);         /* Attach to mbuf chain. */
1433
1434         pkt = (struct dn_pkt_tag *)(mtag + 1);
1435         /*
1436          * Ok, i can handle the pkt now...
1437          * Build and enqueue packet + parameters.
1438          */
1439         pkt->rule = fwa->rule;
1440         pkt->rule.info &= IPFW_ONEPASS; /* only keep this info */
1441         pkt->dn_dir = dir;
1442         pkt->ifp = fwa->oif;
1443
1444         if (q->head == NULL)
1445                 q->head = m;
1446         else
1447                 q->tail->m_nextpkt = m;
1448         q->tail = m;
1449         q->len++;
1450         q->len_bytes += len;
1451
1452         if (q->head != m)               /* Flow was not idle, we are done. */
1453                 goto done;
1454
1455         if (is_pipe) {                  /* Fixed rate queues. */
1456                 if (q->idle_time < curr_time) {
1457                         /* Calculate available burst size. */
1458                         q->numbytes +=
1459                             (curr_time - q->idle_time - 1) * pipe->bandwidth;
1460                         if (q->numbytes > pipe->burst)
1461                                 q->numbytes = pipe->burst;
1462                         if (io_fast)
1463                                 q->numbytes += pipe->bandwidth;
1464                 }
1465         } else {                        /* WF2Q. */
1466                 if (pipe->idle_time < curr_time &&
1467                     pipe->scheduler_heap.elements == 0 &&
1468                     pipe->not_eligible_heap.elements == 0) {
1469                         /* Calculate available burst size. */
1470                         pipe->numbytes +=
1471                             (curr_time - pipe->idle_time - 1) * pipe->bandwidth;
1472                         if (pipe->numbytes > 0 && pipe->numbytes > pipe->burst)
1473                                 pipe->numbytes = pipe->burst;
1474                         if (io_fast)
1475                                 pipe->numbytes += pipe->bandwidth;
1476                 }
1477                 pipe->idle_time = curr_time;
1478         }
1479         /* Necessary for both: fixed rate & WF2Q queues. */
1480         q->idle_time = curr_time;
1481
1482         /*
1483          * If we reach this point the flow was previously idle, so we need
1484          * to schedule it. This involves different actions for fixed-rate or
1485          * WF2Q queues.
1486          */
1487         if (is_pipe) {
1488                 /* Fixed-rate queue: just insert into the ready_heap. */
1489                 dn_key t = 0;
1490
1491                 if (pipe->bandwidth) {
1492                         q->extra_bits = compute_extra_bits(m, pipe);
1493                         t = set_ticks(m, q, pipe);
1494                 }
1495                 q->sched_time = curr_time;
1496                 if (t == 0)             /* Must process it now. */
1497                         ready_event(q, &head, &tail);
1498                 else
1499                         heap_insert(&ready_heap, curr_time + t , q);
1500         } else {
1501                 /*
1502                  * WF2Q. First, compute start time S: if the flow was
1503                  * idle (S = F + 1) set S to the virtual time V for the
1504                  * controlling pipe, and update the sum of weights for the pipe;
1505                  * otherwise, remove flow from idle_heap and set S to max(F,V).
1506                  * Second, compute finish time F = S + len / weight.
1507                  * Third, if pipe was idle, update V = max(S, V).
1508                  * Fourth, count one more backlogged flow.
1509                  */
1510                 if (DN_KEY_GT(q->S, q->F)) { /* Means timestamps are invalid. */
1511                         q->S = pipe->V;
1512                         pipe->sum += fs->weight; /* Add weight of new queue. */
1513                 } else {
1514                         heap_extract(&(pipe->idle_heap), q);
1515                         q->S = MAX64(q->F, pipe->V);
1516                 }
1517                 q->F = q->S + div64(len << MY_M, fs->weight);
1518
1519                 if (pipe->not_eligible_heap.elements == 0 &&
1520                     pipe->scheduler_heap.elements == 0)
1521                         pipe->V = MAX64(q->S, pipe->V);
1522                 fs->backlogged++;
1523                 /*
1524                  * Look at eligibility. A flow is not eligibile if S>V (when
1525                  * this happens, it means that there is some other flow already
1526                  * scheduled for the same pipe, so the scheduler_heap cannot be
1527                  * empty). If the flow is not eligible we just store it in the
1528                  * not_eligible_heap. Otherwise, we store in the scheduler_heap
1529                  * and possibly invoke ready_event_wfq() right now if there is
1530                  * leftover credit.
1531                  * Note that for all flows in scheduler_heap (SCH), S_i <= V,
1532                  * and for all flows in not_eligible_heap (NEH), S_i > V.
1533                  * So when we need to compute max(V, min(S_i)) forall i in
1534                  * SCH+NEH, we only need to look into NEH.
1535                  */
1536                 if (DN_KEY_GT(q->S, pipe->V)) {         /* Not eligible. */
1537                         if (pipe->scheduler_heap.elements == 0)
1538                                 printf("dummynet: ++ ouch! not eligible but empty scheduler!\n");
1539                         heap_insert(&(pipe->not_eligible_heap), q->S, q);
1540                 } else {
1541                         heap_insert(&(pipe->scheduler_heap), q->F, q);
1542                         if (pipe->numbytes >= 0) {       /* Pipe is idle. */
1543                                 if (pipe->scheduler_heap.elements != 1)
1544                                         printf("dummynet: OUCH! pipe should have been idle!\n");
1545                                 DPRINTF(("dummynet: waking up pipe %d at %d\n",
1546                                     pipe->pipe_nr, (int)(q->F >> MY_M)));
1547                                 pipe->sched_time = curr_time;
1548                                 ready_event_wfq(pipe, &head, &tail);
1549                         }
1550                 }
1551         }
1552 done:
1553         if (head == m && (dir & PROTO_LAYER2) == 0 ) {
1554                 /* Fast io. */
1555                 io_pkt_fast++;
1556                 if (m->m_nextpkt != NULL)
1557                         printf("dummynet: fast io: pkt chain detected!\n");
1558                 head = m->m_nextpkt = NULL;
1559         } else
1560                 *m0 = NULL;             /* Normal io. */
1561
1562         DUMMYNET_UNLOCK();
1563         if (head != NULL)
1564                 dummynet_send(head);
1565         return (0);
1566
1567 dropit:
1568         io_pkt_drop++;
1569         if (q)
1570                 q->drops++;
1571         DUMMYNET_UNLOCK();
1572         FREE_PKT(m);
1573         *m0 = NULL;
1574         return ((fs && (fs->flags_fs & DN_NOERROR)) ? 0 : ENOBUFS);
1575 }
1576
1577 /*
1578  * Dispose all packets and flow_queues on a flow_set.
1579  * If all=1, also remove red lookup table and other storage,
1580  * including the descriptor itself.
1581  * For the one in dn_pipe MUST also cleanup ready_heap...
1582  */
1583 static void
1584 purge_flow_set(struct dn_flow_set *fs, int all)
1585 {
1586         struct dn_flow_queue *q, *qn;
1587         int i;
1588
1589         DUMMYNET_LOCK_ASSERT();
1590
1591         for (i = 0; i <= fs->rq_size; i++) {
1592                 for (q = fs->rq[i]; q != NULL; q = qn) {
1593                         dn_free_pkts(q->head);
1594                         qn = q->next;
1595                         free(q, M_DUMMYNET);
1596                 }
1597                 fs->rq[i] = NULL;
1598         }
1599
1600         fs->rq_elements = 0;
1601         if (all) {
1602                 /* RED - free lookup table. */
1603                 if (fs->w_q_lookup != NULL)
1604                         free(fs->w_q_lookup, M_DUMMYNET);
1605                 if (fs->rq != NULL)
1606                         free(fs->rq, M_DUMMYNET);
1607                 /* If this fs is not part of a pipe, free it. */
1608                 if (fs->pipe == NULL || fs != &(fs->pipe->fs))
1609                         free(fs, M_DUMMYNET);
1610         }
1611 }
1612
1613 /*
1614  * Dispose all packets queued on a pipe (not a flow_set).
1615  * Also free all resources associated to a pipe, which is about
1616  * to be deleted.
1617  */
1618 static void
1619 purge_pipe(struct dn_pipe *pipe)
1620 {
1621
1622     purge_flow_set( &(pipe->fs), 1 );
1623
1624     dn_free_pkts(pipe->head);
1625
1626     heap_free( &(pipe->scheduler_heap) );
1627     heap_free( &(pipe->not_eligible_heap) );
1628     heap_free( &(pipe->idle_heap) );
1629 }
1630
1631 /*
1632  * Delete all pipes and heaps returning memory. Must also
1633  * remove references from all ipfw rules to all pipes.
1634  */
1635 static void
1636 dummynet_flush(void)
1637 {
1638         struct dn_pipe *pipe, *pipe1;
1639         struct dn_flow_set *fs, *fs1;
1640         int i;
1641
1642         DUMMYNET_LOCK();
1643         /* Free heaps so we don't have unwanted events. */
1644         heap_free(&ready_heap);
1645         heap_free(&wfq_ready_heap);
1646         heap_free(&extract_heap);
1647
1648         /*
1649          * Now purge all queued pkts and delete all pipes.
1650          *
1651          * XXXGL: can we merge the for(;;) cycles into one or not?
1652          */
1653         for (i = 0; i < HASHSIZE; i++)
1654                 SLIST_FOREACH_SAFE(fs, &flowsethash[i], next, fs1) {
1655                         SLIST_REMOVE(&flowsethash[i], fs, dn_flow_set, next);
1656                         purge_flow_set(fs, 1);
1657                 }
1658         for (i = 0; i < HASHSIZE; i++)
1659                 SLIST_FOREACH_SAFE(pipe, &pipehash[i], next, pipe1) {
1660                         SLIST_REMOVE(&pipehash[i], pipe, dn_pipe, next);
1661                         purge_pipe(pipe);
1662                         free_pipe(pipe);
1663                 }
1664         DUMMYNET_UNLOCK();
1665 }
1666
1667 /*
1668  * setup RED parameters
1669  */
1670 static int
1671 config_red(struct dn_flow_set *p, struct dn_flow_set *x)
1672 {
1673         int i;
1674
1675         x->w_q = p->w_q;
1676         x->min_th = SCALE(p->min_th);
1677         x->max_th = SCALE(p->max_th);
1678         x->max_p = p->max_p;
1679
1680         x->c_1 = p->max_p / (p->max_th - p->min_th);
1681         x->c_2 = SCALE_MUL(x->c_1, SCALE(p->min_th));
1682
1683         if (x->flags_fs & DN_IS_GENTLE_RED) {
1684                 x->c_3 = (SCALE(1) - p->max_p) / p->max_th;
1685                 x->c_4 = SCALE(1) - 2 * p->max_p;
1686         }
1687
1688         /* If the lookup table already exist, free and create it again. */
1689         if (x->w_q_lookup) {
1690                 free(x->w_q_lookup, M_DUMMYNET);
1691                 x->w_q_lookup = NULL;
1692         }
1693         if (red_lookup_depth == 0) {
1694                 printf("\ndummynet: net.inet.ip.dummynet.red_lookup_depth"
1695                     "must be > 0\n");
1696                 free(x, M_DUMMYNET);
1697                 return (EINVAL);
1698         }
1699         x->lookup_depth = red_lookup_depth;
1700         x->w_q_lookup = (u_int *)malloc(x->lookup_depth * sizeof(int),
1701             M_DUMMYNET, M_NOWAIT);
1702         if (x->w_q_lookup == NULL) {
1703                 printf("dummynet: sorry, cannot allocate red lookup table\n");
1704                 free(x, M_DUMMYNET);
1705                 return(ENOSPC);
1706         }
1707
1708         /* Fill the lookup table with (1 - w_q)^x */
1709         x->lookup_step = p->lookup_step;
1710         x->lookup_weight = p->lookup_weight;
1711         x->w_q_lookup[0] = SCALE(1) - x->w_q;
1712
1713         for (i = 1; i < x->lookup_depth; i++)
1714                 x->w_q_lookup[i] =
1715                     SCALE_MUL(x->w_q_lookup[i - 1], x->lookup_weight);
1716
1717         if (red_avg_pkt_size < 1)
1718                 red_avg_pkt_size = 512;
1719         x->avg_pkt_size = red_avg_pkt_size;
1720         if (red_max_pkt_size < 1)
1721                 red_max_pkt_size = 1500;
1722         x->max_pkt_size = red_max_pkt_size;
1723         return (0);
1724 }
1725
1726 static int
1727 alloc_hash(struct dn_flow_set *x, struct dn_flow_set *pfs)
1728 {
1729     if (x->flags_fs & DN_HAVE_FLOW_MASK) {     /* allocate some slots */
1730         int l = pfs->rq_size;
1731
1732         if (l == 0)
1733             l = dn_hash_size;
1734         if (l < 4)
1735             l = 4;
1736         else if (l > DN_MAX_HASH_SIZE)
1737             l = DN_MAX_HASH_SIZE;
1738         x->rq_size = l;
1739     } else                  /* one is enough for null mask */
1740         x->rq_size = 1;
1741     x->rq = malloc((1 + x->rq_size) * sizeof(struct dn_flow_queue *),
1742             M_DUMMYNET, M_NOWAIT | M_ZERO);
1743     if (x->rq == NULL) {
1744         printf("dummynet: sorry, cannot allocate queue\n");
1745         return (ENOMEM);
1746     }
1747     x->rq_elements = 0;
1748     return 0 ;
1749 }
1750
1751 static void
1752 set_fs_parms(struct dn_flow_set *x, struct dn_flow_set *src)
1753 {
1754         x->flags_fs = src->flags_fs;
1755         x->qsize = src->qsize;
1756         x->plr = src->plr;
1757         x->flow_mask = src->flow_mask;
1758         if (x->flags_fs & DN_QSIZE_IS_BYTES) {
1759                 if (x->qsize > pipe_byte_limit)
1760                         x->qsize = 1024 * 1024;
1761         } else {
1762                 if (x->qsize == 0)
1763                         x->qsize = 50;
1764                 if (x->qsize > pipe_slot_limit)
1765                         x->qsize = 50;
1766         }
1767         /* Configuring RED. */
1768         if (x->flags_fs & DN_IS_RED)
1769                 config_red(src, x);     /* XXX should check errors */
1770 }
1771
1772 /*
1773  * Setup pipe or queue parameters.
1774  */
1775 static int
1776 config_pipe(struct dn_pipe *p)
1777 {
1778         struct dn_flow_set *pfs = &(p->fs);
1779         struct dn_flow_queue *q;
1780         int i, error;
1781
1782         /*
1783          * The config program passes parameters as follows:
1784          * bw = bits/second (0 means no limits),
1785          * delay = ms, must be translated into ticks.
1786          * qsize = slots/bytes
1787          */
1788         p->delay = (p->delay * hz) / 1000;
1789         /* Scale burst size: bytes -> bits * hz */
1790         p->burst *= 8 * hz;
1791         /* We need either a pipe number or a flow_set number. */
1792         if (p->pipe_nr == 0 && pfs->fs_nr == 0)
1793                 return (EINVAL);
1794         if (p->pipe_nr != 0 && pfs->fs_nr != 0)
1795                 return (EINVAL);
1796         if (p->pipe_nr != 0) {                  /* this is a pipe */
1797                 struct dn_pipe *pipe;
1798
1799                 DUMMYNET_LOCK();
1800                 pipe = locate_pipe(p->pipe_nr); /* locate pipe */
1801
1802                 if (pipe == NULL) {             /* new pipe */
1803                         pipe = malloc(sizeof(struct dn_pipe), M_DUMMYNET,
1804                             M_NOWAIT | M_ZERO);
1805                         if (pipe == NULL) {
1806                                 DUMMYNET_UNLOCK();
1807                                 printf("dummynet: no memory for new pipe\n");
1808                                 return (ENOMEM);
1809                         }
1810                         pipe->pipe_nr = p->pipe_nr;
1811                         pipe->fs.pipe = pipe;
1812                         /*
1813                          * idle_heap is the only one from which
1814                          * we extract from the middle.
1815                          */
1816                         pipe->idle_heap.size = pipe->idle_heap.elements = 0;
1817                         pipe->idle_heap.offset =
1818                             offsetof(struct dn_flow_queue, heap_pos);
1819                 } else {
1820                         /* Flush accumulated credit for all queues. */
1821                         for (i = 0; i <= pipe->fs.rq_size; i++) {
1822                                 for (q = pipe->fs.rq[i]; q; q = q->next) {
1823                                         q->numbytes = p->burst +
1824                                             (io_fast ? p->bandwidth : 0);
1825                                 }
1826                         }
1827                 }
1828
1829                 pipe->bandwidth = p->bandwidth;
1830                 pipe->burst = p->burst;
1831                 pipe->numbytes = pipe->burst + (io_fast ? pipe->bandwidth : 0);
1832                 bcopy(p->if_name, pipe->if_name, sizeof(p->if_name));
1833                 pipe->ifp = NULL;               /* reset interface ptr */
1834                 pipe->delay = p->delay;
1835                 set_fs_parms(&(pipe->fs), pfs);
1836
1837                 /* Handle changes in the delay profile. */
1838                 if (p->samples_no > 0) {
1839                         if (pipe->samples_no != p->samples_no) {
1840                                 if (pipe->samples != NULL)
1841                                         free(pipe->samples, M_DUMMYNET);
1842                                 pipe->samples =
1843                                     malloc(p->samples_no*sizeof(dn_key),
1844                                         M_DUMMYNET, M_NOWAIT | M_ZERO);
1845                                 if (pipe->samples == NULL) {
1846                                         DUMMYNET_UNLOCK();
1847                                         printf("dummynet: no memory "
1848                                                 "for new samples\n");
1849                                         return (ENOMEM);
1850                                 }
1851                                 pipe->samples_no = p->samples_no;
1852                         }
1853
1854                         strncpy(pipe->name,p->name,sizeof(pipe->name));
1855                         pipe->loss_level = p->loss_level;
1856                         for (i = 0; i<pipe->samples_no; ++i)
1857                                 pipe->samples[i] = p->samples[i];
1858                 } else if (pipe->samples != NULL) {
1859                         free(pipe->samples, M_DUMMYNET);
1860                         pipe->samples = NULL;
1861                         pipe->samples_no = 0;
1862                 }
1863
1864                 if (pipe->fs.rq == NULL) {      /* a new pipe */
1865                         error = alloc_hash(&(pipe->fs), pfs);
1866                         if (error) {
1867                                 DUMMYNET_UNLOCK();
1868                                 free_pipe(pipe);
1869                                 return (error);
1870                         }
1871                         SLIST_INSERT_HEAD(&pipehash[HASH(pipe->pipe_nr)],
1872                             pipe, next);
1873                 }
1874                 DUMMYNET_UNLOCK();
1875         } else {                                /* config queue */
1876                 struct dn_flow_set *fs;
1877
1878                 DUMMYNET_LOCK();
1879                 fs = locate_flowset(pfs->fs_nr); /* locate flow_set */
1880
1881                 if (fs == NULL) {               /* new */
1882                         if (pfs->parent_nr == 0) { /* need link to a pipe */
1883                                 DUMMYNET_UNLOCK();
1884                                 return (EINVAL);
1885                         }
1886                         fs = malloc(sizeof(struct dn_flow_set), M_DUMMYNET,
1887                             M_NOWAIT | M_ZERO);
1888                         if (fs == NULL) {
1889                                 DUMMYNET_UNLOCK();
1890                                 printf(
1891                                     "dummynet: no memory for new flow_set\n");
1892                                 return (ENOMEM);
1893                         }
1894                         fs->fs_nr = pfs->fs_nr;
1895                         fs->parent_nr = pfs->parent_nr;
1896                         fs->weight = pfs->weight;
1897                         if (fs->weight == 0)
1898                                 fs->weight = 1;
1899                         else if (fs->weight > 100)
1900                                 fs->weight = 100;
1901                 } else {
1902                         /*
1903                          * Change parent pipe not allowed;
1904                          * must delete and recreate.
1905                          */
1906                         if (pfs->parent_nr != 0 &&
1907                             fs->parent_nr != pfs->parent_nr) {
1908                                 DUMMYNET_UNLOCK();
1909                                 return (EINVAL);
1910                         }
1911                 }
1912
1913                 set_fs_parms(fs, pfs);
1914
1915                 if (fs->rq == NULL) {           /* a new flow_set */
1916                         error = alloc_hash(fs, pfs);
1917                         if (error) {
1918                                 DUMMYNET_UNLOCK();
1919                                 free(fs, M_DUMMYNET);
1920                                 return (error);
1921                         }
1922                         SLIST_INSERT_HEAD(&flowsethash[HASH(fs->fs_nr)],
1923                             fs, next);
1924                 }
1925                 DUMMYNET_UNLOCK();
1926         }
1927         return (0);
1928 }
1929
1930 /*
1931  * Helper function to remove from a heap queues which are linked to
1932  * a flow_set about to be deleted.
1933  */
1934 static void
1935 fs_remove_from_heap(struct dn_heap *h, struct dn_flow_set *fs)
1936 {
1937     int i, found;
1938
1939     for (i = found = 0 ; i < h->elements ;) {
1940         if ( ((struct dn_flow_queue *)h->p[i].object)->fs == fs) {
1941             h->elements-- ;
1942             h->p[i] = h->p[h->elements] ;
1943             found++ ;
1944         } else
1945             i++ ;
1946     }
1947     if (found)
1948         heapify(h);
1949 }
1950
1951 /*
1952  * helper function to remove a pipe from a heap (can be there at most once)
1953  */
1954 static void
1955 pipe_remove_from_heap(struct dn_heap *h, struct dn_pipe *p)
1956 {
1957     int i;
1958
1959     for (i=0; i < h->elements ; i++ ) {
1960         if (h->p[i].object == p) { /* found it */
1961             h->elements-- ;
1962             h->p[i] = h->p[h->elements] ;
1963             heapify(h);
1964             break ;
1965         }
1966     }
1967 }
1968
1969 /*
1970  * drain all queues. Called in case of severe mbuf shortage.
1971  */
1972 void
1973 dummynet_drain(void)
1974 {
1975     struct dn_flow_set *fs;
1976     struct dn_pipe *pipe;
1977     int i;
1978
1979     DUMMYNET_LOCK_ASSERT();
1980
1981     heap_free(&ready_heap);
1982     heap_free(&wfq_ready_heap);
1983     heap_free(&extract_heap);
1984     /* remove all references to this pipe from flow_sets */
1985     for (i = 0; i < HASHSIZE; i++)
1986         SLIST_FOREACH(fs, &flowsethash[i], next)
1987                 purge_flow_set(fs, 0);
1988
1989     for (i = 0; i < HASHSIZE; i++) {
1990         SLIST_FOREACH(pipe, &pipehash[i], next) {
1991                 purge_flow_set(&(pipe->fs), 0);
1992                 dn_free_pkts(pipe->head);
1993                 pipe->head = pipe->tail = NULL;
1994         }
1995     }
1996 }
1997
1998 /*
1999  * Fully delete a pipe or a queue, cleaning up associated info.
2000  */
2001 static int
2002 delete_pipe(struct dn_pipe *p)
2003 {
2004
2005     if (p->pipe_nr == 0 && p->fs.fs_nr == 0)
2006         return EINVAL ;
2007     if (p->pipe_nr != 0 && p->fs.fs_nr != 0)
2008         return EINVAL ;
2009     if (p->pipe_nr != 0) { /* this is an old-style pipe */
2010         struct dn_pipe *pipe;
2011         struct dn_flow_set *fs;
2012         int i;
2013
2014         DUMMYNET_LOCK();
2015         pipe = locate_pipe(p->pipe_nr); /* locate pipe */
2016
2017         if (pipe == NULL) {
2018             DUMMYNET_UNLOCK();
2019             return (ENOENT);    /* not found */
2020         }
2021
2022         /* Unlink from list of pipes. */
2023         SLIST_REMOVE(&pipehash[HASH(pipe->pipe_nr)], pipe, dn_pipe, next);
2024
2025         /* Remove all references to this pipe from flow_sets. */
2026         for (i = 0; i < HASHSIZE; i++) {
2027             SLIST_FOREACH(fs, &flowsethash[i], next) {
2028                 if (fs->pipe == pipe) {
2029                         printf("dummynet: ++ ref to pipe %d from fs %d\n",
2030                             p->pipe_nr, fs->fs_nr);
2031                         fs->pipe = NULL ;
2032                         purge_flow_set(fs, 0);
2033                 }
2034             }
2035         }
2036         fs_remove_from_heap(&ready_heap, &(pipe->fs));
2037         purge_pipe(pipe); /* remove all data associated to this pipe */
2038         /* remove reference to here from extract_heap and wfq_ready_heap */
2039         pipe_remove_from_heap(&extract_heap, pipe);
2040         pipe_remove_from_heap(&wfq_ready_heap, pipe);
2041         DUMMYNET_UNLOCK();
2042
2043         free_pipe(pipe);
2044     } else { /* this is a WF2Q queue (dn_flow_set) */
2045         struct dn_flow_set *fs;
2046
2047         DUMMYNET_LOCK();
2048         fs = locate_flowset(p->fs.fs_nr); /* locate set */
2049
2050         if (fs == NULL) {
2051             DUMMYNET_UNLOCK();
2052             return (ENOENT); /* not found */
2053         }
2054
2055         /* Unlink from list of flowsets. */
2056         SLIST_REMOVE( &flowsethash[HASH(fs->fs_nr)], fs, dn_flow_set, next);
2057
2058         if (fs->pipe != NULL) {
2059             /* Update total weight on parent pipe and cleanup parent heaps. */
2060             fs->pipe->sum -= fs->weight * fs->backlogged ;
2061             fs_remove_from_heap(&(fs->pipe->not_eligible_heap), fs);
2062             fs_remove_from_heap(&(fs->pipe->scheduler_heap), fs);
2063 #if 1   /* XXX should i remove from idle_heap as well ? */
2064             fs_remove_from_heap(&(fs->pipe->idle_heap), fs);
2065 #endif
2066         }
2067         purge_flow_set(fs, 1);
2068         DUMMYNET_UNLOCK();
2069     }
2070     return 0 ;
2071 }
2072
2073 /*
2074  * helper function used to copy data from kernel in DUMMYNET_GET
2075  */
2076 static char *
2077 dn_copy_set(struct dn_flow_set *set, char *bp)
2078 {
2079     int i, copied = 0 ;
2080     struct dn_flow_queue *q, *qp = (struct dn_flow_queue *)bp;
2081
2082     DUMMYNET_LOCK_ASSERT();
2083
2084     for (i = 0 ; i <= set->rq_size ; i++) {
2085         for (q = set->rq[i] ; q ; q = q->next, qp++ ) {
2086             if (q->hash_slot != i)
2087                 printf("dummynet: ++ at %d: wrong slot (have %d, "
2088                     "should be %d)\n", copied, q->hash_slot, i);
2089             if (q->fs != set)
2090                 printf("dummynet: ++ at %d: wrong fs ptr (have %p, should be %p)\n",
2091                         i, q->fs, set);
2092             copied++ ;
2093             bcopy(q, qp, sizeof( *q ) );
2094             /* cleanup pointers */
2095             qp->next = NULL ;
2096             qp->head = qp->tail = NULL ;
2097             qp->fs = NULL ;
2098         }
2099     }
2100     if (copied != set->rq_elements)
2101         printf("dummynet: ++ wrong count, have %d should be %d\n",
2102             copied, set->rq_elements);
2103     return (char *)qp ;
2104 }
2105
2106 static size_t
2107 dn_calc_size(void)
2108 {
2109     struct dn_flow_set *fs;
2110     struct dn_pipe *pipe;
2111     size_t size = 0;
2112     int i;
2113
2114     DUMMYNET_LOCK_ASSERT();
2115     /*
2116      * Compute size of data structures: list of pipes and flow_sets.
2117      */
2118     for (i = 0; i < HASHSIZE; i++) {
2119         SLIST_FOREACH(pipe, &pipehash[i], next)
2120                 size += sizeof(*pipe) +
2121                     pipe->fs.rq_elements * sizeof(struct dn_flow_queue);
2122         SLIST_FOREACH(fs, &flowsethash[i], next)
2123                 size += sizeof (*fs) +
2124                     fs->rq_elements * sizeof(struct dn_flow_queue);
2125     }
2126     return size;
2127 }
2128
2129 static int
2130 dummynet_get(struct sockopt *sopt)
2131 {
2132     char *buf, *bp ; /* bp is the "copy-pointer" */
2133     size_t size ;
2134     struct dn_flow_set *fs;
2135     struct dn_pipe *pipe;
2136     int error=0, i ;
2137
2138     /* XXX lock held too long */
2139     DUMMYNET_LOCK();
2140     /*
2141      * XXX: Ugly, but we need to allocate memory with M_WAITOK flag and we
2142      *      cannot use this flag while holding a mutex.
2143      */
2144     for (i = 0; i < 10; i++) {
2145         size = dn_calc_size();
2146         DUMMYNET_UNLOCK();
2147         buf = malloc(size, M_TEMP, M_WAITOK);
2148         DUMMYNET_LOCK();
2149         if (size >= dn_calc_size())
2150                 break;
2151         free(buf, M_TEMP);
2152         buf = NULL;
2153     }
2154     if (buf == NULL) {
2155         DUMMYNET_UNLOCK();
2156         return ENOBUFS ;
2157     }
2158     bp = buf;
2159     for (i = 0; i < HASHSIZE; i++) {
2160         SLIST_FOREACH(pipe, &pipehash[i], next) {
2161                 struct dn_pipe *pipe_bp = (struct dn_pipe *)bp;
2162
2163                 /*
2164                  * Copy pipe descriptor into *bp, convert delay back to ms,
2165                  * then copy the flow_set descriptor(s) one at a time.
2166                  * After each flow_set, copy the queue descriptor it owns.
2167                  */
2168                 bcopy(pipe, bp, sizeof(*pipe));
2169                 pipe_bp->delay = (pipe_bp->delay * 1000) / hz;
2170                 pipe_bp->burst = div64(pipe_bp->burst, 8 * hz);
2171                 /*
2172                  * XXX the following is a hack based on ->next being the
2173                  * first field in dn_pipe and dn_flow_set. The correct
2174                  * solution would be to move the dn_flow_set to the beginning
2175                  * of struct dn_pipe.
2176                  */
2177                 pipe_bp->next.sle_next = (struct dn_pipe *)DN_IS_PIPE;
2178                 /* Clean pointers. */
2179                 pipe_bp->head = pipe_bp->tail = NULL;
2180                 pipe_bp->fs.next.sle_next = NULL;
2181                 pipe_bp->fs.pipe = NULL;
2182                 pipe_bp->fs.rq = NULL;
2183                 pipe_bp->samples = NULL;
2184
2185                 bp += sizeof(*pipe) ;
2186                 bp = dn_copy_set(&(pipe->fs), bp);
2187         }
2188     }
2189
2190     for (i = 0; i < HASHSIZE; i++) {
2191         SLIST_FOREACH(fs, &flowsethash[i], next) {
2192                 struct dn_flow_set *fs_bp = (struct dn_flow_set *)bp;
2193
2194                 bcopy(fs, bp, sizeof(*fs));
2195                 /* XXX same hack as above */
2196                 fs_bp->next.sle_next = (struct dn_flow_set *)DN_IS_QUEUE;
2197                 fs_bp->pipe = NULL;
2198                 fs_bp->rq = NULL;
2199                 bp += sizeof(*fs);
2200                 bp = dn_copy_set(fs, bp);
2201         }
2202     }
2203
2204     DUMMYNET_UNLOCK();
2205
2206     error = sooptcopyout(sopt, buf, size);
2207     free(buf, M_TEMP);
2208     return error ;
2209 }
2210
2211 /*
2212  * Handler for the various dummynet socket options (get, flush, config, del)
2213  */
2214 static int
2215 ip_dn_ctl(struct sockopt *sopt)
2216 {
2217     int error;
2218     struct dn_pipe *p = NULL;
2219
2220     error = priv_check(sopt->sopt_td, PRIV_NETINET_DUMMYNET);
2221     if (error)
2222         return (error);
2223
2224     /* Disallow sets in really-really secure mode. */
2225     if (sopt->sopt_dir == SOPT_SET) {
2226 #if __FreeBSD_version >= 500034
2227         error =  securelevel_ge(sopt->sopt_td->td_ucred, 3);
2228         if (error)
2229             return (error);
2230 #else
2231         if (securelevel >= 3)
2232             return (EPERM);
2233 #endif
2234     }
2235
2236     switch (sopt->sopt_name) {
2237     default :
2238         printf("dummynet: -- unknown option %d", sopt->sopt_name);
2239         error = EINVAL ;
2240         break;
2241
2242     case IP_DUMMYNET_GET :
2243         error = dummynet_get(sopt);
2244         break ;
2245
2246     case IP_DUMMYNET_FLUSH :
2247         dummynet_flush() ;
2248         break ;
2249
2250     case IP_DUMMYNET_CONFIGURE :
2251         p = malloc(sizeof(struct dn_pipe_max), M_TEMP, M_WAITOK);
2252         error = sooptcopyin(sopt, p, sizeof(struct dn_pipe_max), sizeof *p);
2253         if (error)
2254             break ;
2255         if (p->samples_no > 0)
2256             p->samples = &(((struct dn_pipe_max *)p)->samples[0]);
2257
2258         error = config_pipe(p);
2259         break ;
2260
2261     case IP_DUMMYNET_DEL :      /* remove a pipe or queue */
2262         p = malloc(sizeof(struct dn_pipe), M_TEMP, M_WAITOK);
2263         error = sooptcopyin(sopt, p, sizeof(struct dn_pipe), sizeof *p);
2264         if (error)
2265             break ;
2266
2267         error = delete_pipe(p);
2268         break ;
2269     }
2270
2271     if (p != NULL)
2272         free(p, M_TEMP);
2273
2274     return error ;
2275 }
2276
2277 static void
2278 ip_dn_init(void)
2279 {
2280         int i;
2281
2282         if (bootverbose)
2283                 printf("DUMMYNET with IPv6 initialized (040826)\n");
2284
2285         DUMMYNET_LOCK_INIT();
2286
2287         for (i = 0; i < HASHSIZE; i++) {
2288                 SLIST_INIT(&pipehash[i]);
2289                 SLIST_INIT(&flowsethash[i]);
2290         }
2291         ready_heap.size = ready_heap.elements = 0;
2292         ready_heap.offset = 0;
2293
2294         wfq_ready_heap.size = wfq_ready_heap.elements = 0;
2295         wfq_ready_heap.offset = 0;
2296
2297         extract_heap.size = extract_heap.elements = 0;
2298         extract_heap.offset = 0;
2299
2300         ip_dn_ctl_ptr = ip_dn_ctl;
2301         ip_dn_io_ptr = dummynet_io;
2302
2303         TASK_INIT(&dn_task, 0, dummynet_task, NULL);
2304         dn_tq = taskqueue_create_fast("dummynet", M_NOWAIT,
2305             taskqueue_thread_enqueue, &dn_tq);
2306         taskqueue_start_threads(&dn_tq, 1, PI_NET, "dummynet");
2307
2308         callout_init(&dn_timeout, CALLOUT_MPSAFE);
2309         callout_reset(&dn_timeout, 1, dummynet, NULL);
2310
2311         /* Initialize curr_time adjustment mechanics. */
2312         getmicrouptime(&prev_t);
2313 }
2314
2315 #ifdef KLD_MODULE
2316 static void
2317 ip_dn_destroy(void)
2318 {
2319         ip_dn_ctl_ptr = NULL;
2320         ip_dn_io_ptr = NULL;
2321
2322         DUMMYNET_LOCK();
2323         callout_stop(&dn_timeout);
2324         DUMMYNET_UNLOCK();
2325         taskqueue_drain(dn_tq, &dn_task);
2326         taskqueue_free(dn_tq);
2327
2328         dummynet_flush();
2329
2330         DUMMYNET_LOCK_DESTROY();
2331 }
2332 #endif /* KLD_MODULE */
2333
2334 static int
2335 dummynet_modevent(module_t mod, int type, void *data)
2336 {
2337
2338         switch (type) {
2339         case MOD_LOAD:
2340                 if (ip_dn_io_ptr) {
2341                     printf("DUMMYNET already loaded\n");
2342                     return EEXIST ;
2343                 }
2344                 ip_dn_init();
2345                 break;
2346
2347         case MOD_UNLOAD:
2348 #if !defined(KLD_MODULE)
2349                 printf("dummynet statically compiled, cannot unload\n");
2350                 return EINVAL ;
2351 #else
2352                 ip_dn_destroy();
2353 #endif
2354                 break ;
2355         default:
2356                 return EOPNOTSUPP;
2357                 break ;
2358         }
2359         return 0 ;
2360 }
2361
2362 static moduledata_t dummynet_mod = {
2363         "dummynet",
2364         dummynet_modevent,
2365         NULL
2366 };
2367 DECLARE_MODULE(dummynet, dummynet_mod, SI_SUB_PROTO_IFATTACHDOMAIN, SI_ORDER_ANY);
2368 MODULE_DEPEND(dummynet, ipfw, 2, 2, 2);
2369 MODULE_VERSION(dummynet, 1);
2370 /* end of file */