sys/netinet/ip_dummynet.c

   1 /*
   2  * Copyright (c) 1998-2000 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  * $FreeBSD$
  28  */
  29
  30 #define DEB(x)
  31 #define DDB(x)  x
  32
  33 /*
  34  * This module implements IP dummynet, a bandwidth limiter/delay emulator
  35  * used in conjunction with the ipfw package.
  36  *
  37  * Most important Changes:
  38  *
  39  * 000106: large rewrite, use heaps to handle very many pipes.
  40  * 980513:      initial release
  41  *
  42  * include files marked with XXX are probably not needed
  43  */
  44
  45 #include <sys/param.h>
  46 #include <sys/systm.h>
  47 #include <sys/malloc.h>
  48 #include <sys/mbuf.h>
  49 #include <sys/queue.h>                  /* XXX */
  50 #include <sys/kernel.h>
  51 #include <sys/module.h>
  52 #include <sys/socket.h>
  53 #include <sys/socketvar.h>
  54 #include <sys/time.h>
  55 #include <sys/sysctl.h>
  56 #include <net/if.h>
  57 #include <net/route.h>
  58 #include <netinet/in.h>
  59 #include <netinet/in_systm.h>
  60 #include <netinet/in_var.h>
  61 #include <netinet/ip.h>
  62 #include <netinet/ip_fw.h>
  63 #include <netinet/ip_dummynet.h>
  64 #include <netinet/ip_var.h>
  65
  66 #include "opt_bdg.h"
  67 #ifdef BRIDGE
  68 #include <netinet/if_ether.h> /* for struct arpcom */
  69 #include <net/bridge.h>
  70 #endif
  71
  72 /*
  73  * we keep a private variable for the simulation time, but probably
  74  * it would be better to use the already existing one "softticks"
  75  * (in sys/kern/kern_timer.c)
  76  */
  77 static dn_key curr_time = 0 ; /* current simulation time */
  78
  79 static int dn_hash_size = 64 ;  /* default hash size */
  80
  81 /* statistics on number of queue searches and search steps */
  82 static int searches, search_steps ;
  83 static int pipe_expire = 1 ;   /* expire queue if empty */
  84
  85 static struct dn_heap ready_heap, extract_heap ;
  86 static int heap_init(struct dn_heap *h, int size) ;
  87 static int heap_insert (struct dn_heap *h, dn_key key1, void *p);
  88 static void heap_extract(struct dn_heap *h);
  89 static void transmit_event(struct dn_pipe *pipe);
  90 static void ready_event(struct dn_flow_queue *q);
  91
  92 static struct dn_pipe *all_pipes = NULL ;       /* list of all pipes */
  93
  94 #ifdef SYSCTL_NODE
  95 SYSCTL_NODE(_net_inet_ip, OID_AUTO, dummynet,
  96                 CTLFLAG_RW, 0, "Dummynet");
  97 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, hash_size,
  98             CTLFLAG_RW, &dn_hash_size, 0, "Default hash table size");
  99 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, curr_time,
 100             CTLFLAG_RD, &curr_time, 0, "Current tick");
 101 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, ready_heap,
 102             CTLFLAG_RD, &ready_heap.size, 0, "Size of ready heap");
 103 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, extract_heap,
 104             CTLFLAG_RD, &extract_heap.size, 0, "Size of extract heap");
 105 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, searches,
 106             CTLFLAG_RD, &searches, 0, "Number of queue searches");
 107 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, search_steps,
 108             CTLFLAG_RD, &search_steps, 0, "Number of queue search steps");
 109 SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, expire,
 110             CTLFLAG_RW, &pipe_expire, 0, "Expire queue if empty");
 111 #endif
 112
 113 static int ip_dn_ctl(struct sockopt *sopt);
 114
 115 static void rt_unref(struct rtentry *);
 116 static void dummynet(void *);
 117 static void dummynet_flush(void);
 118
 119 /*
 120  * ip_fw_chain is used when deleting a pipe, because ipfw rules can
 121  * hold references to the pipe.
 122  */
 123 extern LIST_HEAD (ip_fw_head, ip_fw_chain) ip_fw_chain;
 124
 125 static void
 126 rt_unref(struct rtentry *rt)
 127 {
 128     if (rt == NULL)
 129         return ;
 130     if (rt->rt_refcnt <= 0)
 131         printf("-- warning, refcnt now %ld, decreasing\n", rt->rt_refcnt);
 132     RTFREE(rt);
 133 }
 134
 135 /*
 136  * Heap management functions.
 137  *
 138  * In the heap, first node is element 0. Children of i are 2i+1 and 2i+2.
 139  * Some macros help finding parent/children so we can optimize them.
 140  *
 141  * heap_init() is called to expand the heap when needed.
 142  * Increment size in blocks of 256 entries (which make one 4KB page)
 143  * XXX failure to allocate a new element is a pretty bad failure
 144  * as we basically stall a whole queue forever!!
 145  * Returns 1 on error, 0 on success
 146  */
 147 #define HEAP_FATHER(x) ( ( (x) - 1 ) / 2 )
 148 #define HEAP_LEFT(x) ( 2*(x) + 1 )
 149 #define HEAP_IS_LEFT(x) ( (x) & 1 )
 150 #define HEAP_RIGHT(x) ( 2*(x) + 1 )
 151 #define HEAP_SWAP(a, b, buffer) { buffer = a ; a = b ; b = buffer ; }
 152 #define HEAP_INCREMENT  255
 153
 154 static int
 155 heap_init(struct dn_heap *h, int new_size)
 156 {
 157     struct dn_heap_entry *p;
 158
 159     if (h->size >= new_size ) {
 160         printf("heap_init, Bogus call, have %d want %d\n",
 161                 h->size, new_size);
 162         return 0 ;
 163     }
 164     new_size = (new_size + HEAP_INCREMENT ) & ~HEAP_INCREMENT ;
 165     p = malloc(new_size * sizeof(*p), M_IPFW, M_DONTWAIT );
 166     if (p == NULL) {
 167         printf(" heap_init, resize %d failed\n", new_size );
 168         return 1 ; /* error */
 169     }
 170     if (h->size > 0) {
 171         bcopy(h->p, p, h->size * sizeof(*p) );
 172         free(h->p, M_IPFW);
 173     }
 174     h->p = p ;
 175     h->size = new_size ;
 176     return 0 ;
 177 }
 178
 179 /*
 180  * Insert element in heap. Normally, p != NULL, we insert p in
 181  * a new position and bubble up. If p == NULL, then the element is
 182  * already in place, and key is the position where to start the
 183  * bubble-up.
 184  * Returns 1 on failure (cannot allocate new heap entry)
 185  */
 186 static int
 187 heap_insert(struct dn_heap *h, dn_key key1, void *p)
 188 {
 189     int son = h->elements ;
 190
 191     if (p == NULL)      /* data already there, set starting point */
 192         son = key1 ;
 193     else {              /* insert new element at the end, possibly resize */
 194         son = h->elements ;
 195         if (son == h->size) /* need resize... */
 196             if (heap_init(h, h->elements+1) )
 197                 return 1 ; /* failure... */
 198         h->p[son].object = p ;
 199         h->p[son].key = key1 ;
 200         h->elements++ ;
 201     }
 202     while (son > 0) {                           /* bubble up */
 203         int father = HEAP_FATHER(son) ;
 204         struct dn_heap_entry tmp  ;
 205
 206         if (DN_KEY_LT( h->p[father].key, h->p[son].key ) )
 207             break ; /* found right position */
 208         /* son smaller than father, swap and try again */
 209         HEAP_SWAP(h->p[son], h->p[father], tmp) ;
 210         son = father ;
 211     }
 212     return 0 ;
 213 }
 214
 215 /*
 216  * remove top element from heap
 217  */
 218 static void
 219 heap_extract(struct dn_heap *h)
 220 {
 221     int child, father, max = h->elements - 1 ;
 222     if (max < 0)
 223         return ;
 224
 225     /* move up smallest child */
 226     father = 0 ;
 227     child = HEAP_LEFT(father) ;         /* left child */
 228     while (child <= max) {              /* valid entry */
 229         if (child != max && DN_KEY_LT(h->p[child+1].key, h->p[child].key) )
 230             child = child+1 ;           /* take right child, otherwise left */
 231         h->p[father] = h->p[child] ;
 232         father = child ;
 233         child = HEAP_LEFT(child) ;   /* left child for next loop */
 234     }
 235     h->elements-- ;
 236     if (father != max) {
 237         /*
 238          * Fill hole with last entry and bubble up, reusing the insert code
 239          */
 240         h->p[father] = h->p[max] ;
 241         heap_insert(h, father, NULL); /* this one cannot fail */
 242     }
 243 }
 244
 245 /*
 246  * heapify() will reorganize data inside an array to maintain the
 247  * heap property. It is needed when we delete a bunch of entries.
 248  */
 249 static void
 250 heapify(struct dn_heap *h)
 251 {
 252     int father, i ;
 253     struct dn_heap_entry tmp ;
 254
 255     for (i = h->elements - 1 ; i > 0 ; i-- ) {
 256         father = HEAP_FATHER(i) ;
 257         if ( DN_KEY_LT(h->p[i].key, h->p[father].key) )
 258             HEAP_SWAP(h->p[father], h->p[i], tmp) ;
 259     }
 260 }
 261 /*
 262  * --- end of heap management functions ---
 263  */
 264
 265 /*
 266  * Scheduler functions -- transmit_event(), ready_event()
 267  *
 268  * transmit_event() is called when the delay-line needs to enter
 269  * the scheduler, either because of existing pkts getting ready,
 270  * or new packets entering the queue. The event handled is the delivery
 271  * time of the packet.
 272  *
 273  * ready_event() does something similar with flow queues, and the
 274  * event handled is the finish time of the head pkt.
 275  *
 276  * In both cases, we make sure that the data structures are consistent
 277  * before passing pkts out, because this might trigger recursive
 278  * invocations of the procedures.
 279  */
 280 static void
 281 transmit_event(struct dn_pipe *pipe)
 282 {
 283     struct dn_pkt *pkt ;
 284
 285     while ( (pkt = pipe->p.head) && DN_KEY_LEQ(pkt->output_time, curr_time) ) {
 286         /*
 287          * first unlink, then call procedures, since ip_input() can invoke
 288          * ip_output() and viceversa, thus causing nested calls
 289          */
 290         pipe->p.head = DN_NEXT(pkt) ;
 291
 292         /*
 293          * The actual mbuf is preceded by a struct dn_pkt, resembling an mbuf
 294          * (NOT A REAL one, just a small block of malloc'ed memory) with
 295          *     m_type = MT_DUMMYNET
 296          *     m_next = actual mbuf to be processed by ip_input/output
 297          *     m_data = the matching rule
 298          * and some other fields.
 299          * The block IS FREED HERE because it contains parameters passed
 300          * to the called routine.
 301          */
 302         switch (pkt->dn_dir) {
 303         case DN_TO_IP_OUT:
 304             (void)ip_output((struct mbuf *)pkt, NULL, NULL, 0, NULL);
 305             rt_unref (pkt->ro.ro_rt) ;
 306             break ;
 307
 308         case DN_TO_IP_IN :
 309             ip_input((struct mbuf *)pkt) ;
 310             break ;
 311
 312 #ifdef BRIDGE
 313         case DN_TO_BDG_FWD : {
 314             struct mbuf *m = (struct mbuf *)pkt ;
 315             bdg_forward(&m, pkt->ifp);
 316             if (m)
 317                 m_freem(m);
 318             }
 319             break ;
 320 #endif
 321
 322         default:
 323             printf("dummynet: bad switch %d!\n", pkt->dn_dir);
 324             m_freem(pkt->dn_m);
 325             break ;
 326         }
 327         FREE(pkt, M_IPFW);
 328     }
 329     /* if there are leftover packets, put into the heap for next event */
 330     if ( (pkt = pipe->p.head) )
 331          heap_insert(&extract_heap, pkt->output_time, pipe ) ;
 332     /* XXX should check errors on heap_insert, by draining the
 333      * whole pipe p and hoping in the future we are more successful
 334      */
 335 }
 336
 337 /*
 338  * ready_event() is invoked every time the queue must enter the
 339  * scheduler, either because the first packet arrives, or because
 340  * a previously scheduled event fired.
 341  * On invokation, drain as many pkts as possible (could be 0) and then
 342  * if there are leftover packets reinsert the pkt in the scheduler.
 343  */
 344 static void
 345 ready_event(struct dn_flow_queue *q)
 346 {
 347     struct dn_pkt *pkt;
 348     struct dn_pipe *p = q->p ;
 349     int p_was_empty = (p->p.head == NULL) ;
 350
 351     while ( (pkt = q->r.head) != NULL ) {
 352         int len = pkt->dn_m->m_pkthdr.len;
 353         int len_scaled = p->bandwidth ? len*8*hz : 0 ;
 354         /*
 355          * bandwidth==0 (no limit) means we can drain as many pkts as
 356          * needed from the queue. Setting len_scaled = 0 does the job.
 357          */
 358         if (len_scaled > q->numbytes )
 359             break ;
 360         /*
 361          * extract pkt from queue, compute output time (could be now)
 362          * and put into delay line (p_queue)
 363          */
 364         q->numbytes -= len_scaled ;
 365         q->r.head = DN_NEXT(pkt) ;
 366         q->len-- ;
 367         q->len_bytes -= len ;
 368
 369         pkt->output_time = curr_time + p->delay ;
 370
 371         if (p->p.head == NULL)
 372             p->p.head = pkt;
 373         else
 374             DN_NEXT(p->p.tail) = pkt;
 375         p->p.tail = pkt;
 376         DN_NEXT(p->p.tail) = NULL;
 377     }
 378     /*
 379      * If we have more packets queued, schedule next ready event
 380      * (can only occur when bandwidth != 0, otherwise we would have
 381      * flushed the whole queue in the previous loop).
 382      * To this purpose compute how many ticks to go for the next
 383      * event, accounting for packet size and residual credit. This means
 384      * we compute the finish time of the packet.
 385      */
 386     if ( (pkt = q->r.head) != NULL ) { /* this implies bandwidth != 0 */
 387         dn_key t ;
 388         t = (pkt->dn_m->m_pkthdr.len*8*hz - q->numbytes + p->bandwidth - 1 ) /
 389                 p->bandwidth ;
 390         q->numbytes += t * p->bandwidth ;
 391         heap_insert(&ready_heap, curr_time + t, (void *)q );
 392         /* XXX should check errors on heap_insert, and drain the whole
 393          * queue on error hoping next time we are luckier.
 394          */
 395     }
 396     /*
 397      * If the delay line was empty call transmit_event(p) now.
 398      * Otherwise, the scheduler will take care of it.
 399      */
 400     if (p_was_empty)
 401         transmit_event(p);
 402 }
 403
 404 /*
 405  * this is called once per tick, or HZ times per second. It is used to
 406  * increment the current tick counter and schedule expired events.
 407  */
 408 static void
 409 dummynet(void * __unused unused)
 410 {
 411     void *p ; /* generic parameter to handler */
 412     struct dn_heap *h ;
 413     int s ;
 414
 415     s = splnet(); /* avoid network interrupts... */
 416     curr_time++ ;
 417     h = &ready_heap ;
 418     while (h->elements > 0 && DN_KEY_LEQ(h->p[0].key, curr_time) ) {
 419         /*
 420          * XXX if the event is late, we should probably credit the queue
 421          * by q->p->bandwidth * (delta_ticks). On the other hand, i dont
 422          * think this can ever occur with this code (i.e. curr_time will
 423          * still be incremented by one at each tick. Things might be
 424          * different if we were using the counter from the high priority
 425          * timer.
 426          */
 427         if (h->p[0].key != curr_time)
 428             printf("-- dummynet: warning, event is %d ticks late\n",
 429                 curr_time - h->p[0].key);
 430         p = h->p[0].object ;
 431         heap_extract(h); /* need to extract before processing */
 432         ready_event(p) ;
 433     }
 434     h = &extract_heap ;
 435     while (h->elements > 0 && DN_KEY_LEQ(h->p[0].key, curr_time) ) {
 436         if (h->p[0].key != curr_time)   /* XXX same as above */
 437             printf("-- dummynet: warning, event is %d ticks late\n",
 438                 curr_time - h->p[0].key);
 439         p = h->p[0].object ;
 440         heap_extract(&extract_heap);
 441         transmit_event(p);
 442     }
 443     splx(s);
 444     timeout(dummynet, NULL, 1);
 445 }
 446
 447 /*
 448  * Given a pipe and a pkt in last_pkt, find a matching queue
 449  * after appropriate masking. The queue is moved to front
 450  * so that further searches take less time.
 451  * XXX if the queue is longer than some threshold should consider
 452  * purging old unused entries. They will get in the way every time
 453  * we have a new flow.
 454  */
 455 static struct dn_flow_queue *
 456 find_queue(struct dn_pipe *pipe)
 457 {
 458     int i = 0 ; /* we need i and q for new allocations */
 459     struct dn_flow_queue *q, *prev;
 460
 461     if ( !(pipe->flags & DN_HAVE_FLOW_MASK) )
 462         q = pipe->rq[0] ;
 463     else {
 464         /* first, do the masking */
 465         last_pkt.dst_ip &= pipe->flow_mask.dst_ip ;
 466         last_pkt.src_ip &= pipe->flow_mask.src_ip ;
 467         last_pkt.dst_port &= pipe->flow_mask.dst_port ;
 468         last_pkt.src_port &= pipe->flow_mask.src_port ;
 469         last_pkt.proto &= pipe->flow_mask.proto ;
 470         last_pkt.flags = 0 ; /* we don't care about this one */
 471         /* then, hash function */
 472         i = ( (last_pkt.dst_ip) & 0xffff ) ^
 473             ( (last_pkt.dst_ip >> 15) & 0xffff ) ^
 474             ( (last_pkt.src_ip << 1) & 0xffff ) ^
 475             ( (last_pkt.src_ip >> 16 ) & 0xffff ) ^
 476             (last_pkt.dst_port << 1) ^ (last_pkt.src_port) ^
 477             (last_pkt.proto );
 478         i = i % pipe->rq_size ;
 479         /* finally, scan the current list for a match */
 480         searches++ ;
 481         for (prev=NULL, q = pipe->rq[i] ; q ; ) {
 482             search_steps++;
 483             if (bcmp(&last_pkt, &(q->id), sizeof(q->id) ) == 0)
 484                 break ; /* found */
 485             else if (pipe_expire && q->r.head == NULL) {
 486                 /* entry is idle, expire it */
 487                 struct dn_flow_queue *old_q = q ;
 488
 489                 if (prev != NULL)
 490                     prev->next = q = q->next ;
 491                 else
 492                     pipe->rq[i] = q = q->next ;
 493                 pipe->rq_elements-- ;
 494                 free(old_q, M_IPFW);
 495                 continue ;
 496             }
 497             prev = q ;
 498             q = q->next ;
 499         }
 500         if (q && prev != NULL) { /* found and not in front */
 501             prev->next = q->next ;
 502             q->next = pipe->rq[i] ;
 503             pipe->rq[i] = q ;
 504         }
 505     }
 506     if (q == NULL) { /* no match, need to allocate a new entry */
 507         q = malloc(sizeof(*q), M_IPFW, M_DONTWAIT) ;
 508         if (q == NULL) {
 509             printf("sorry, cannot allocate new flow\n");
 510             return NULL ;
 511         }
 512         bzero(q, sizeof(*q) );  /* needed */
 513         q->id = last_pkt ;
 514         q->p = pipe ;
 515         q->hash_slot = i ;
 516         q->next = pipe->rq[i] ;
 517         pipe->rq[i] = q ;
 518         pipe->rq_elements++ ;
 519         DEB(printf("++ new queue (%d) for 0x%08x/0x%04x -> 0x%08x/0x%04x\n",
 520                 pipe->rq_elements,
 521                 last_pkt.src_ip, last_pkt.src_port,
 522                 last_pkt.dst_ip, last_pkt.dst_port); )
 523     }
 524     return q ;
 525 }
 526
 527 /*
 528  * dummynet hook for packets.
 529  */
 530 int
 531 dummynet_io(int pipe_nr, int dir,
 532         struct mbuf *m, struct ifnet *ifp, struct route *ro,
 533         struct sockaddr_in *dst,
 534         struct ip_fw_chain *rule, int flags)
 535 {
 536     struct dn_pkt *pkt;
 537     struct dn_pipe *p;
 538     int len = m->m_pkthdr.len ;
 539     struct dn_flow_queue *q = NULL ;
 540     int s ;
 541
 542     s = splimp();
 543     /* XXX check the spl protection. It might be unnecessary since we
 544      * run this at splnet() already.
 545      */
 546
 547     DEB(printf("-- last_pkt dst 0x%08x/0x%04x src 0x%08x/0x%04x\n",
 548         last_pkt.dst_ip, last_pkt.dst_port,
 549         last_pkt.src_ip, last_pkt.src_port);)
 550
 551     pipe_nr &= 0xffff ;
 552     /*
 553      * locate pipe. First time is expensive, next have direct access.
 554      */
 555     if ( (p = rule->rule->pipe_ptr) == NULL ) {
 556         for (p = all_pipes; p && p->pipe_nr != pipe_nr; p = p->next)
 557             ;
 558         if (p == NULL)
 559             goto dropit ;       /* this pipe does not exist! */
 560         rule->rule->pipe_ptr = p ; /* record pipe ptr for the future    */
 561     }
 562     q = find_queue(p);
 563     /*
 564      * update statistics, then do various check on reasons to drop pkt
 565      */
 566     if ( q == NULL )
 567         goto dropit ;           /* cannot allocate queue                */
 568     q->tot_bytes += len ;
 569     q->tot_pkts++ ;
 570     if ( p->plr && random() < p->plr )
 571         goto dropit ;           /* random pkt drop                      */
 572     if ( p->queue_size && q->len >= p->queue_size)
 573         goto dropit ;           /* queue count overflow                 */
 574     if ( p->queue_size_bytes && len + q->len_bytes > p->queue_size_bytes)
 575         goto dropit ;           /* queue size overflow                  */
 576     /*
 577      * can implement RED drops here if needed.
 578      */
 579
 580     pkt = (struct dn_pkt *)malloc(sizeof (*pkt), M_IPFW, M_NOWAIT) ;
 581     if ( pkt == NULL )
 582         goto dropit ;           /* cannot allocate packet header        */
 583     /* ok, i can handle the pkt now... */
 584     bzero(pkt, sizeof(*pkt) ); /* XXX expensive, see if we can remove it*/
 585     /* build and enqueue packet + parameters */
 586     pkt->hdr.mh_type = MT_DUMMYNET ;
 587     (struct ip_fw_chain *)pkt->hdr.mh_data = rule ;
 588     DN_NEXT(pkt) = NULL;
 589     pkt->dn_m = m;
 590     pkt->dn_dir = dir ;
 591
 592     pkt->ifp = ifp;
 593     if (dir == DN_TO_IP_OUT) {
 594         /*
 595          * We need to copy *ro because for ICMP pkts (and maybe others)
 596          * the caller passed a pointer into the stack; and, dst might
 597          * also be a pointer into *ro so it needs to be updated.
 598          */
 599         pkt->ro = *ro;
 600         if (ro->ro_rt)
 601             ro->ro_rt->rt_refcnt++ ; /* XXX */
 602         if (dst == (struct sockaddr_in *)&ro->ro_dst) /* dst points into ro */
 603             dst = (struct sockaddr_in *)&(pkt->ro.ro_dst) ;
 604
 605         pkt->dn_dst = dst;
 606         pkt->flags = flags ;
 607     }
 608     if (q->r.head == NULL)
 609         q->r.head = pkt;
 610     else
 611         DN_NEXT(q->r.tail) = pkt;
 612     q->r.tail = pkt;
 613     q->len++;
 614     q->len_bytes += len ;
 615
 616     /*
 617      * If queue was empty (this is first pkt) then call ready_event()
 618      * now to make the pkt go out at the right time. Otherwise we are done,
 619      * as there must be a ready event already scheduled.
 620      */
 621     if (q->r.head == pkt) /* r_queue was empty */
 622         ready_event( q );
 623     splx(s);
 624     return 0;
 625
 626 dropit:
 627     splx(s);
 628     if (q)
 629         q->drops++ ;
 630     m_freem(m);
 631     return 0 ; /* XXX should I return an error ? */
 632 }
 633
 634 /*
 635  * below, the rt_unref is only needed when (pkt->dn_dir == DN_TO_IP_OUT)
 636  * Doing this would probably save us the initial bzero of dn_pkt
 637  */
 638 #define DN_FREE_PKT(pkt)        {               \
 639         struct dn_pkt *n = pkt ;                \
 640         rt_unref ( n->ro.ro_rt ) ;              \
 641         m_freem(n->dn_m);                       \
 642         pkt = DN_NEXT(n) ;                      \
 643         free(n, M_IPFW) ;       }
 644 /*
 645  * dispose all packets queued on a pipe
 646  */
 647 static void
 648 purge_pipe(struct dn_pipe *pipe)
 649 {
 650     struct dn_pkt *pkt ;
 651     struct dn_flow_queue *q, *qn ;
 652     int i ;
 653
 654     for (i = 0 ; i < pipe->rq_size ; i++ )
 655         for (q = pipe->rq[i] ; q ; q = qn ) {
 656             for (pkt = q->r.head ; pkt ; )
 657                 DN_FREE_PKT(pkt) ;
 658             qn = q->next ;
 659             free(q, M_IPFW);
 660         }
 661     for (pkt = pipe->p.head ; pkt ; )
 662         DN_FREE_PKT(pkt) ;
 663 }
 664
 665 /*
 666  * Delete all pipes and heaps returning memory. Must also
 667  * remove references from all ipfw rules to all pipes.
 668  */
 669 static void
 670 dummynet_flush()
 671 {
 672     struct dn_pipe *curr_p, *p ;
 673     struct ip_fw_chain *chain ;
 674     int s ;
 675
 676     s = splnet() ;
 677
 678     /* remove all references to pipes ...*/
 679     for (chain= ip_fw_chain.lh_first ; chain; chain = chain->chain.le_next)
 680         chain->rule->pipe_ptr = NULL ;
 681     /* prevent future matches... */
 682     p = all_pipes ;
 683     all_pipes = NULL ;
 684     /* and free heaps so we don't have unwanted events */
 685     if (ready_heap.size >0 )
 686         free(ready_heap.p, M_IPFW);
 687     ready_heap.elements = ready_heap.size = 0 ;
 688     if (extract_heap.size >0 )
 689         free(extract_heap.p, M_IPFW);
 690     extract_heap.elements = extract_heap.size = 0 ;
 691     splx(s) ;
 692     /*
 693      * Now purge all queued pkts and delete all pipes
 694      */
 695     for ( ; p ; ) {
 696         purge_pipe(p);
 697         curr_p = p ;
 698         p = p->next ;
 699         free(curr_p->rq, M_IPFW);
 700         free(curr_p, M_IPFW);
 701     }
 702 }
 703
 704 extern struct ip_fw_chain *ip_fw_default_rule ;
 705 /*
 706  * when a firewall rule is deleted, scan all queues and remove the flow-id
 707  * from packets matching this rule.
 708  */
 709 void
 710 dn_rule_delete(void *r)
 711 {
 712     struct dn_pipe *p ;
 713     struct dn_flow_queue *q ;
 714     struct dn_pkt *pkt ;
 715     int i ;
 716
 717     for ( p = all_pipes ; p ; p = p->next ) {
 718         for (i = 0 ; i < p->rq_size ; i++)
 719             for (q = p->rq[i] ; q ; q = q->next )
 720                 for (pkt = q->r.head ; pkt ; pkt = DN_NEXT(pkt) )
 721                     if (pkt->hdr.mh_data == r)
 722                         pkt->hdr.mh_data = (void *)ip_fw_default_rule ;
 723         for (pkt = p->p.head ; pkt ; pkt = DN_NEXT(pkt) )
 724             if (pkt->hdr.mh_data == r)
 725                 pkt->hdr.mh_data = (void *)ip_fw_default_rule ;
 726     }
 727 }
 728
 729 /*
 730  * handler for the various dummynet socket options
 731  * (get, flush, config, del)
 732  */
 733 static int
 734 ip_dn_ctl(struct sockopt *sopt)
 735 {
 736     int error = 0 ;
 737     size_t size ;
 738     char *buf, *bp ; /* bp is the "copy-pointer" */
 739     struct dn_pipe *p, tmp_pipe ;
 740
 741     struct dn_pipe *x, *a, *b ;
 742
 743     /* Disallow sets in really-really secure mode. */
 744     if (sopt->sopt_dir == SOPT_SET && securelevel >= 3)
 745         return (EPERM);
 746
 747     switch (sopt->sopt_name) {
 748     default :
 749         panic("ip_dn_ctl -- unknown option");
 750
 751     case IP_DUMMYNET_GET :
 752         for (p = all_pipes, size = 0 ; p ; p = p->next )
 753             size += sizeof( *p ) +
 754                 p->rq_elements * sizeof(struct dn_flow_queue);
 755         buf = malloc(size, M_TEMP, M_WAITOK);
 756         if (buf == 0) {
 757             error = ENOBUFS ;
 758             break ;
 759         }
 760         for (p = all_pipes, bp = buf ; p ; p = p->next ) {
 761             int i ;
 762             struct dn_pipe *pipe_bp = (struct dn_pipe *)bp ;
 763             struct dn_flow_queue *q;
 764
 765             /*
 766              * copy the pipe descriptor into *bp, convert delay back to ms,
 767              * then copy the queue descriptor(s) one at a time.
 768              */
 769             bcopy(p, bp, sizeof( *p ) );
 770             pipe_bp->delay = (pipe_bp->delay * 1000) / hz ;
 771             bp += sizeof( *p ) ;
 772             for (i = 0 ; i < p->rq_size ; i++)
 773                 for (q = p->rq[i] ; q ; q = q->next, bp += sizeof(*q) )
 774                     bcopy(q, bp, sizeof( *q ) );
 775         }
 776         error = sooptcopyout(sopt, buf, size);
 777         FREE(buf, M_TEMP);
 778         break ;
 779
 780     case IP_DUMMYNET_FLUSH :
 781         dummynet_flush() ;
 782         break ;
 783
 784     case IP_DUMMYNET_CONFIGURE :
 785         p = &tmp_pipe ;
 786         error = sooptcopyin(sopt, p, sizeof *p, sizeof *p);
 787         if (error)
 788             break ;
 789         /*
 790          * The config program passes parameters as follows:
 791          * bandwidth = bits/second (0 means no limits);
 792          * delay = millisec.,   must be translated into ticks.
 793          * queue_size = slots (0 means no limit)
 794          * queue_size_bytes = bytes (0 means no limit)
 795          *        only one can be set, must be bound-checked
 796          */
 797         p->delay = ( p->delay * hz ) / 1000 ;
 798         if (p->queue_size == 0 && p->queue_size_bytes == 0)
 799             p->queue_size = 50 ;
 800         if (p->queue_size != 0 )        /* buffers are prevailing */
 801             p->queue_size_bytes = 0 ;
 802         if (p->queue_size > 100)
 803             p->queue_size = 50 ;
 804         if (p->queue_size_bytes > 1024*1024)
 805             p->queue_size_bytes = 1024*1024 ;
 806         for (a = NULL , b = all_pipes ; b && b->pipe_nr < p->pipe_nr ;
 807                  a = b , b = b->next) ;
 808         if (b && b->pipe_nr == p->pipe_nr) {
 809             b->bandwidth = p->bandwidth ;
 810             b->delay = p->delay ;
 811             b->queue_size = p->queue_size ;
 812             b->queue_size_bytes = p->queue_size_bytes ;
 813             b->plr = p->plr ;
 814             b->flow_mask = p->flow_mask ;
 815             b->flags = p->flags ;
 816         } else { /* completely new pipe */
 817             int s ;
 818             x = malloc(sizeof(struct dn_pipe), M_IPFW, M_DONTWAIT) ;
 819             if (x == NULL) {
 820                 printf("ip_dummynet.c: no memory for new pipe\n");
 821                 error = ENOSPC ;
 822                 break ;
 823             }
 824             bzero(x, sizeof(*x) );
 825             x->bandwidth = p->bandwidth ;
 826             x->delay = p->delay ;
 827             x->pipe_nr = p->pipe_nr ;
 828             x->queue_size = p->queue_size ;
 829             x->queue_size_bytes = p->queue_size_bytes ;
 830             x->plr = p->plr ;
 831             x->flow_mask = p->flow_mask ;
 832             x->flags = p->flags ;
 833             if (x->flags & DN_HAVE_FLOW_MASK) {/* allocate some slots */
 834                 int l = p->rq_size ;
 835                 if (l == 0)
 836                     l = dn_hash_size ;
 837                 if (l < 4)
 838                     l = 4 ;
 839                 else if (l > 1024)
 840                     l = 1024 ;
 841                 x->rq_size = l ;
 842             } else /* one is enough for null mask */
 843                 x->rq_size = 1 ;
 844             x->rq = malloc(x->rq_size * sizeof(struct dn_flow_queue *),
 845                     M_IPFW, M_DONTWAIT) ;
 846             if (x->rq == NULL ) {
 847                 printf("sorry, cannot allocate queue\n");
 848                 free(x, M_IPFW);
 849                 error = ENOSPC ;
 850                 break ;
 851             }
 852             bzero(x->rq, x->rq_size * sizeof(struct dn_flow_queue *) );
 853             x->rq_elements = 0 ;
 854
 855             s = splnet() ;
 856             x->next = b ;
 857             if (a == NULL)
 858                 all_pipes = x ;
 859             else
 860                 a->next = x ;
 861             splx(s);
 862         }
 863         break ;
 864
 865     case IP_DUMMYNET_DEL :
 866         p = &tmp_pipe ;
 867         error = sooptcopyin(sopt, p, sizeof *p, sizeof *p);
 868         if (error)
 869             break ;
 870
 871         for (a = NULL , b = all_pipes ; b && b->pipe_nr < p->pipe_nr ;
 872                  a = b , b = b->next) ;
 873         if (b && b->pipe_nr == p->pipe_nr) {    /* found pipe */
 874             int s ;
 875             struct ip_fw_chain *chain ;
 876
 877             s = splnet() ;
 878             chain = ip_fw_chain.lh_first;
 879
 880             if (a == NULL)
 881                 all_pipes = b->next ;
 882             else
 883                 a->next = b->next ;
 884             /*
 885              * remove references to this pipe from the ip_fw rules.
 886              */
 887             for (; chain; chain = chain->chain.le_next)
 888                 if (chain->rule->pipe_ptr == b)
 889                     chain->rule->pipe_ptr = NULL ;
 890             /* remove all references to b from heaps */
 891             if (ready_heap.elements > 0) {
 892                 struct dn_heap *h = &ready_heap ;
 893                 int i = 0, found = 0 ;
 894                 while ( i < h->elements ) {
 895                     if (((struct dn_flow_queue *)(h->p[i].object))->p == b) {
 896                         /* found one */
 897                         h->elements-- ;
 898                         h->p[i] = h->p[h->elements] ;
 899                         found++ ;
 900                     } else
 901                         i++ ;
 902                 }
 903                 if (found)
 904                     heapify(h);
 905             }
 906             if (extract_heap.elements > 0) {
 907                 struct dn_heap *h = &extract_heap ;
 908                 int i = 0, found = 0 ;
 909                 while ( i < h->elements ) {
 910                     if (h->p[i].object == b) { /* found one */
 911                         h->elements-- ;
 912                         h->p[i] = h->p[h->elements] ;
 913                         found++ ;
 914                     } else
 915                         i++ ;
 916                 }
 917                 if (found)
 918                     heapify(h);
 919             }
 920             splx(s);
 921             purge_pipe(b);      /* remove pkts from here */
 922             free(b->rq, M_IPFW);
 923             free(b, M_IPFW);
 924         }
 925         break ;
 926     }
 927     return error ;
 928 }
 929
 930 static void
 931 ip_dn_init(void)
 932 {
 933     printf("DUMMYNET initialized (000106)\n");
 934     all_pipes = NULL ;
 935     ready_heap.size = ready_heap.elements = 0 ;
 936     extract_heap.size = extract_heap.elements = 0 ;
 937     ip_dn_ctl_ptr = ip_dn_ctl;
 938     timeout(dummynet, NULL, 1);
 939 }
 940
 941 static ip_dn_ctl_t *old_dn_ctl_ptr ;
 942
 943 static int
 944 dummynet_modevent(module_t mod, int type, void *data)
 945 {
 946         int s ;
 947         switch (type) {
 948         case MOD_LOAD:
 949                 s = splnet();
 950                 old_dn_ctl_ptr = ip_dn_ctl_ptr;
 951                 ip_dn_init();
 952                 splx(s);
 953                 break;
 954         case MOD_UNLOAD:
 955                 s = splnet();
 956                 ip_dn_ctl_ptr =  old_dn_ctl_ptr;
 957                 splx(s);
 958                 dummynet_flush();
 959                 break ;
 960         default:
 961                 break ;
 962         }
 963         return 0 ;
 964 }
 965
 966 static moduledata_t dummynet_mod = {
 967         "dummynet",
 968         dummynet_modevent,
 969         NULL
 970 } ;
 971 DECLARE_MODULE(dummynet, dummynet_mod, SI_SUB_PSEUDO, SI_ORDER_ANY);