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