2 * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
3 * Portions Copyright (c) 2000 Akamba Corp.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
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.
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
27 * $FreeBSD: src/sys/netinet/ip_dummynet.c,v 1.24.2.22 2003/05/13 09:31:06 maxim Exp $
28 * $DragonFly: src/sys/net/dummynet/ip_dummynet.c,v 1.23 2007/09/02 13:27:23 sephe Exp $
31 #if !defined(KLD_MODULE)
32 #include "opt_ipfw.h" /* for IPFW2 definition */
39 * This module implements IP dummynet, a bandwidth limiter/delay emulator
40 * used in conjunction with the ipfw package.
41 * Description of the data structures used is in ip_dummynet.h
42 * Here you mainly find the following blocks of code:
43 * + variable declarations;
44 * + heap management functions;
45 * + scheduler and dummynet functions;
46 * + configuration and initialization.
48 * NOTA BENE: critical sections are protected by splimp()/splx()
49 * pairs. One would think that splnet() is enough as for most of
50 * the netinet code, but it is not so because when used with
51 * bridging, dummynet is invoked at splimp().
53 * Most important Changes:
56 * 010124: Fixed WF2Q behaviour
57 * 010122: Fixed spl protection.
58 * 000601: WF2Q support
59 * 000106: large rewrite, use heaps to handle very many pipes.
60 * 980513: initial release
62 * include files marked with XXX are probably not needed
65 #include <sys/param.h>
66 #include <sys/systm.h>
67 #include <sys/malloc.h>
69 #include <sys/kernel.h>
70 #include <sys/module.h>
72 #include <sys/socket.h>
73 #include <sys/socketvar.h>
75 #include <sys/sysctl.h>
76 #include <sys/thread2.h>
78 #include <net/route.h>
79 #include <netinet/in.h>
80 #include <netinet/in_systm.h>
81 #include <netinet/in_var.h>
82 #include <netinet/ip.h>
83 #include <net/ipfw/ip_fw.h>
84 #include "ip_dummynet.h"
85 #include <netinet/ip_var.h>
87 #include <netinet/if_ether.h> /* for struct arpcom */
90 * We keep a private variable for the simulation time, but we could
91 * probably use an existing one ("softticks" in sys/kern/kern_timer.c)
93 static dn_key curr_time
= 0 ; /* current simulation time */
95 static int dn_hash_size
= 64 ; /* default hash size */
97 /* statistics on number of queue searches and search steps */
98 static int searches
, search_steps
;
99 static int pipe_expire
= 1 ; /* expire queue if empty */
100 static int dn_max_ratio
= 16 ; /* max queues/buckets ratio */
102 static int red_lookup_depth
= 256; /* RED - default lookup table depth */
103 static int red_avg_pkt_size
= 512; /* RED - default medium packet size */
104 static int red_max_pkt_size
= 1500; /* RED - default max packet size */
107 * Three heaps contain queues and pipes that the scheduler handles:
109 * ready_heap contains all dn_flow_queue related to fixed-rate pipes.
111 * wfq_ready_heap contains the pipes associated with WF2Q flows
113 * extract_heap contains pipes associated with delay lines.
117 MALLOC_DEFINE(M_DUMMYNET
, "dummynet", "dummynet heap");
119 static struct dn_heap ready_heap
, extract_heap
, wfq_ready_heap
;
121 static int heap_init(struct dn_heap
*h
, int size
) ;
122 static int heap_insert (struct dn_heap
*h
, dn_key key1
, void *p
);
123 static void heap_extract(struct dn_heap
*h
, void *obj
);
125 static void transmit_event(struct dn_pipe
*pipe
);
126 static void ready_event(struct dn_flow_queue
*q
);
128 static struct dn_pipe
*all_pipes
= NULL
; /* list of all pipes */
129 static struct dn_flow_set
*all_flow_sets
= NULL
;/* list of all flow_sets */
131 static struct callout dn_timeout
;
134 SYSCTL_NODE(_net_inet_ip
, OID_AUTO
, dummynet
,
135 CTLFLAG_RW
, 0, "Dummynet");
136 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, hash_size
,
137 CTLFLAG_RW
, &dn_hash_size
, 0, "Default hash table size");
138 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, curr_time
,
139 CTLFLAG_RD
, &curr_time
, 0, "Current tick");
140 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, ready_heap
,
141 CTLFLAG_RD
, &ready_heap
.size
, 0, "Size of ready heap");
142 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, extract_heap
,
143 CTLFLAG_RD
, &extract_heap
.size
, 0, "Size of extract heap");
144 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, searches
,
145 CTLFLAG_RD
, &searches
, 0, "Number of queue searches");
146 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, search_steps
,
147 CTLFLAG_RD
, &search_steps
, 0, "Number of queue search steps");
148 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, expire
,
149 CTLFLAG_RW
, &pipe_expire
, 0, "Expire queue if empty");
150 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, max_chain_len
,
151 CTLFLAG_RW
, &dn_max_ratio
, 0,
152 "Max ratio between dynamic queues and buckets");
153 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, red_lookup_depth
,
154 CTLFLAG_RD
, &red_lookup_depth
, 0, "Depth of RED lookup table");
155 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, red_avg_pkt_size
,
156 CTLFLAG_RD
, &red_avg_pkt_size
, 0, "RED Medium packet size");
157 SYSCTL_INT(_net_inet_ip_dummynet
, OID_AUTO
, red_max_pkt_size
,
158 CTLFLAG_RD
, &red_max_pkt_size
, 0, "RED Max packet size");
161 static int config_pipe(struct dn_pipe
*p
);
162 static int ip_dn_ctl(struct sockopt
*sopt
);
164 static void rt_unref(struct rtentry
*);
165 static void dummynet(void *);
166 static void dummynet_flush(void);
167 void dummynet_drain(void);
168 static ip_dn_io_t dummynet_io
;
169 static void dn_rule_delete(void *);
171 int if_tx_rdy(struct ifnet
*ifp
);
174 rt_unref(struct rtentry
*rt
)
178 if (rt
->rt_refcnt
<= 0)
179 kprintf("-- warning, refcnt now %ld, decreasing\n", rt
->rt_refcnt
);
184 * Heap management functions.
186 * In the heap, first node is element 0. Children of i are 2i+1 and 2i+2.
187 * Some macros help finding parent/children so we can optimize them.
189 * heap_init() is called to expand the heap when needed.
190 * Increment size in blocks of 16 entries.
191 * XXX failure to allocate a new element is a pretty bad failure
192 * as we basically stall a whole queue forever!!
193 * Returns 1 on error, 0 on success
195 #define HEAP_FATHER(x) ( ( (x) - 1 ) / 2 )
196 #define HEAP_LEFT(x) ( 2*(x) + 1 )
197 #define HEAP_IS_LEFT(x) ( (x) & 1 )
198 #define HEAP_RIGHT(x) ( 2*(x) + 2 )
199 #define HEAP_SWAP(a, b, buffer) { buffer = a ; a = b ; b = buffer ; }
200 #define HEAP_INCREMENT 15
203 heap_init(struct dn_heap
*h
, int new_size
)
205 struct dn_heap_entry
*p
;
207 if (h
->size
>= new_size
) {
208 kprintf("heap_init, Bogus call, have %d want %d\n",
212 new_size
= (new_size
+ HEAP_INCREMENT
) & ~HEAP_INCREMENT
;
213 p
= kmalloc(new_size
* sizeof(*p
), M_DUMMYNET
, M_WAITOK
| M_ZERO
);
215 bcopy(h
->p
, p
, h
->size
* sizeof(*p
) );
216 kfree(h
->p
, M_DUMMYNET
);
224 * Insert element in heap. Normally, p != NULL, we insert p in
225 * a new position and bubble up. If p == NULL, then the element is
226 * already in place, and key is the position where to start the
228 * Returns 1 on failure (cannot allocate new heap entry)
230 * If offset > 0 the position (index, int) of the element in the heap is
231 * also stored in the element itself at the given offset in bytes.
233 #define SET_OFFSET(heap, node) \
234 if (heap->offset > 0) \
235 *((int *)((char *)(heap->p[node].object) + heap->offset)) = node ;
237 * RESET_OFFSET is used for sanity checks. It sets offset to an invalid value.
239 #define RESET_OFFSET(heap, node) \
240 if (heap->offset > 0) \
241 *((int *)((char *)(heap->p[node].object) + heap->offset)) = -1 ;
243 heap_insert(struct dn_heap
*h
, dn_key key1
, void *p
)
245 int son
= h
->elements
;
247 if (p
== NULL
) /* data already there, set starting point */
249 else { /* insert new element at the end, possibly resize */
251 if (son
== h
->size
) /* need resize... */
252 if (heap_init(h
, h
->elements
+1) )
253 return 1 ; /* failure... */
254 h
->p
[son
].object
= p
;
255 h
->p
[son
].key
= key1
;
258 while (son
> 0) { /* bubble up */
259 int father
= HEAP_FATHER(son
) ;
260 struct dn_heap_entry tmp
;
262 if (DN_KEY_LT( h
->p
[father
].key
, h
->p
[son
].key
) )
263 break ; /* found right position */
264 /* son smaller than father, swap and repeat */
265 HEAP_SWAP(h
->p
[son
], h
->p
[father
], tmp
) ;
274 * remove top element from heap, or obj if obj != NULL
277 heap_extract(struct dn_heap
*h
, void *obj
)
279 int child
, father
, max
= h
->elements
- 1 ;
282 kprintf("warning, extract from empty heap 0x%p\n", h
);
285 father
= 0 ; /* default: move up smallest child */
286 if (obj
!= NULL
) { /* extract specific element, index is at offset */
288 panic("*** heap_extract from middle not supported on this heap!!!\n");
289 father
= *((int *)((char *)obj
+ h
->offset
)) ;
290 if (father
< 0 || father
>= h
->elements
) {
291 kprintf("dummynet: heap_extract, father %d out of bound 0..%d\n",
292 father
, h
->elements
);
293 panic("heap_extract");
296 RESET_OFFSET(h
, father
);
297 child
= HEAP_LEFT(father
) ; /* left child */
298 while (child
<= max
) { /* valid entry */
299 if (child
!= max
&& DN_KEY_LT(h
->p
[child
+1].key
, h
->p
[child
].key
) )
300 child
= child
+1 ; /* take right child, otherwise left */
301 h
->p
[father
] = h
->p
[child
] ;
302 SET_OFFSET(h
, father
);
304 child
= HEAP_LEFT(child
) ; /* left child for next loop */
309 * Fill hole with last entry and bubble up, reusing the insert code
311 h
->p
[father
] = h
->p
[max
] ;
312 heap_insert(h
, father
, NULL
); /* this one cannot fail */
318 * change object position and update references
319 * XXX this one is never used!
322 heap_move(struct dn_heap
*h
, dn_key new_key
, void *object
)
326 int max
= h
->elements
-1 ;
327 struct dn_heap_entry buf
;
330 panic("cannot move items on this heap");
332 i
= *((int *)((char *)object
+ h
->offset
));
333 if (DN_KEY_LT(new_key
, h
->p
[i
].key
) ) { /* must move up */
334 h
->p
[i
].key
= new_key
;
335 for (; i
>0 && DN_KEY_LT(new_key
, h
->p
[(temp
= HEAP_FATHER(i
))].key
) ;
336 i
= temp
) { /* bubble up */
337 HEAP_SWAP(h
->p
[i
], h
->p
[temp
], buf
) ;
340 } else { /* must move down */
341 h
->p
[i
].key
= new_key
;
342 while ( (temp
= HEAP_LEFT(i
)) <= max
) { /* found left child */
343 if ((temp
!= max
) && DN_KEY_GT(h
->p
[temp
].key
, h
->p
[temp
+1].key
))
344 temp
++ ; /* select child with min key */
345 if (DN_KEY_GT(new_key
, h
->p
[temp
].key
)) { /* go down */
346 HEAP_SWAP(h
->p
[i
], h
->p
[temp
], buf
) ;
355 #endif /* heap_move, unused */
358 * heapify() will reorganize data inside an array to maintain the
359 * heap property. It is needed when we delete a bunch of entries.
362 heapify(struct dn_heap
*h
)
366 for (i
= 0 ; i
< h
->elements
; i
++ )
367 heap_insert(h
, i
, NULL
) ;
371 * cleanup the heap and free data structure
374 heap_free(struct dn_heap
*h
)
377 kfree(h
->p
, M_DUMMYNET
);
378 bzero(h
, sizeof(*h
) );
382 * --- end of heap management functions ---
386 * Scheduler functions:
388 * transmit_event() is called when the delay-line needs to enter
389 * the scheduler, either because of existing pkts getting ready,
390 * or new packets entering the queue. The event handled is the delivery
391 * time of the packet.
393 * ready_event() does something similar with fixed-rate queues, and the
394 * event handled is the finish time of the head pkt.
396 * wfq_ready_event() does something similar with WF2Q queues, and the
397 * event handled is the start time of the head pkt.
399 * In all cases, we make sure that the data structures are consistent
400 * before passing pkts out, because this might trigger recursive
401 * invocations of the procedures.
404 transmit_event(struct dn_pipe
*pipe
)
408 while ( (pkt
= pipe
->head
) && DN_KEY_LEQ(pkt
->output_time
, curr_time
) ) {
410 * first unlink, then call procedures, since ip_input() can invoke
411 * ip_output() and viceversa, thus causing nested calls
413 pipe
->head
= DN_NEXT(pkt
) ;
416 * The actual mbuf is preceded by a struct dn_pkt, resembling an mbuf
417 * (NOT A REAL one, just a small block of malloc'ed memory) with
418 * m_type = MT_TAG, m_flags = PACKET_TAG_DUMMYNET
419 * dn_m (m_next) = actual mbuf to be processed by ip_input/output
420 * and some other fields.
421 * The block IS FREED HERE because it contains parameters passed
422 * to the called routine.
424 switch (pkt
->dn_dir
) {
426 ip_output((struct mbuf
*)pkt
, NULL
, NULL
, 0, NULL
, NULL
);
427 rt_unref (pkt
->ro
.ro_rt
) ;
431 ip_input((struct mbuf
*)pkt
) ;
434 case DN_TO_ETH_DEMUX
:
436 struct mbuf
*m
= (struct mbuf
*)pkt
;
437 struct ether_header
*eh
;
439 if (pkt
->dn_m
->m_len
< ETHER_HDR_LEN
&&
440 (pkt
->dn_m
= m_pullup(pkt
->dn_m
, ETHER_HDR_LEN
)) == NULL
) {
441 kprintf("dummynet: pullup fail, dropping pkt\n");
445 * same as ether_input, make eh be a pointer into the mbuf
447 eh
= mtod(pkt
->dn_m
, struct ether_header
*);
448 m_adj(pkt
->dn_m
, ETHER_HDR_LEN
);
449 /* which consumes the mbuf */
450 ether_demux(NULL
, eh
, m
);
454 ether_output_frame(pkt
->ifp
, (struct mbuf
*)pkt
);
458 kprintf("dummynet: bad switch %d!\n", pkt
->dn_dir
);
462 kfree(pkt
, M_DUMMYNET
);
464 /* if there are leftover packets, put into the heap for next event */
465 if ( (pkt
= pipe
->head
) )
466 heap_insert(&extract_heap
, pkt
->output_time
, pipe
) ;
467 /* XXX should check errors on heap_insert, by draining the
468 * whole pipe p and hoping in the future we are more successful
473 * the following macro computes how many ticks we have to wait
474 * before being able to transmit a packet. The credit is taken from
475 * either a pipe (WF2Q) or a flow_queue (per-flow queueing)
477 #define SET_TICKS(pkt, q, p) \
478 (pkt->dn_m->m_pkthdr.len*8*hz - (q)->numbytes + p->bandwidth - 1 ) / \
482 * extract pkt from queue, compute output time (could be now)
483 * and put into delay line (p_queue)
486 move_pkt(struct dn_pkt
*pkt
, struct dn_flow_queue
*q
,
487 struct dn_pipe
*p
, int len
)
489 q
->head
= DN_NEXT(pkt
) ;
491 q
->len_bytes
-= len
;
493 pkt
->output_time
= curr_time
+ p
->delay
;
498 DN_NEXT_NC(p
->tail
) = (struct mbuf
*)pkt
;
500 DN_NEXT_NC(p
->tail
) = NULL
;
504 * ready_event() is invoked every time the queue must enter the
505 * scheduler, either because the first packet arrives, or because
506 * a previously scheduled event fired.
507 * On invokation, drain as many pkts as possible (could be 0) and then
508 * if there are leftover packets reinsert the pkt in the scheduler.
511 ready_event(struct dn_flow_queue
*q
)
514 struct dn_pipe
*p
= q
->fs
->pipe
;
518 kprintf("ready_event- pipe is gone\n");
521 p_was_empty
= (p
->head
== NULL
) ;
524 * schedule fixed-rate queues linked to this pipe:
525 * Account for the bw accumulated since last scheduling, then
526 * drain as many pkts as allowed by q->numbytes and move to
527 * the delay line (in p) computing output time.
528 * bandwidth==0 (no limit) means we can drain the whole queue,
529 * setting len_scaled = 0 does the job.
531 q
->numbytes
+= ( curr_time
- q
->sched_time
) * p
->bandwidth
;
532 while ( (pkt
= q
->head
) != NULL
) {
533 int len
= pkt
->dn_m
->m_pkthdr
.len
;
534 int len_scaled
= p
->bandwidth
? len
*8*hz
: 0 ;
535 if (len_scaled
> q
->numbytes
)
537 q
->numbytes
-= len_scaled
;
538 move_pkt(pkt
, q
, p
, len
);
541 * If we have more packets queued, schedule next ready event
542 * (can only occur when bandwidth != 0, otherwise we would have
543 * flushed the whole queue in the previous loop).
544 * To this purpose we record the current time and compute how many
545 * ticks to go for the finish time of the packet.
547 if ( (pkt
= q
->head
) != NULL
) { /* this implies bandwidth != 0 */
548 dn_key t
= SET_TICKS(pkt
, q
, p
); /* ticks i have to wait */
549 q
->sched_time
= curr_time
;
550 heap_insert(&ready_heap
, curr_time
+ t
, (void *)q
);
551 /* XXX should check errors on heap_insert, and drain the whole
552 * queue on error hoping next time we are luckier.
554 } else { /* RED needs to know when the queue becomes empty */
555 q
->q_time
= curr_time
;
559 * If the delay line was empty call transmit_event(p) now.
560 * Otherwise, the scheduler will take care of it.
567 * Called when we can transmit packets on WF2Q queues. Take pkts out of
568 * the queues at their start time, and enqueue into the delay line.
569 * Packets are drained until p->numbytes < 0. As long as
570 * len_scaled >= p->numbytes, the packet goes into the delay line
571 * with a deadline p->delay. For the last packet, if p->numbytes<0,
572 * there is an additional delay.
575 ready_event_wfq(struct dn_pipe
*p
)
577 int p_was_empty
= (p
->head
== NULL
) ;
578 struct dn_heap
*sch
= &(p
->scheduler_heap
);
579 struct dn_heap
*neh
= &(p
->not_eligible_heap
) ;
581 if (p
->if_name
[0] == 0) /* tx clock is simulated */
582 p
->numbytes
+= ( curr_time
- p
->sched_time
) * p
->bandwidth
;
583 else { /* tx clock is for real, the ifq must be empty or this is a NOP */
584 if (p
->ifp
&& p
->ifp
->if_snd
.ifq_head
!= NULL
)
587 DEB(kprintf("pipe %d ready from %s --\n",
588 p
->pipe_nr
, p
->if_name
);)
593 * While we have backlogged traffic AND credit, we need to do
594 * something on the queue.
596 while ( p
->numbytes
>=0 && (sch
->elements
>0 || neh
->elements
>0) ) {
597 if (sch
->elements
> 0) { /* have some eligible pkts to send out */
598 struct dn_flow_queue
*q
= sch
->p
[0].object
;
599 struct dn_pkt
*pkt
= q
->head
;
600 struct dn_flow_set
*fs
= q
->fs
;
601 u_int64_t len
= pkt
->dn_m
->m_pkthdr
.len
;
602 int len_scaled
= p
->bandwidth
? len
*8*hz
: 0 ;
604 heap_extract(sch
, NULL
); /* remove queue from heap */
605 p
->numbytes
-= len_scaled
;
606 move_pkt(pkt
, q
, p
, len
);
608 p
->V
+= (len
<<MY_M
) / p
->sum
; /* update V */
609 q
->S
= q
->F
; /* update start time */
610 if (q
->len
== 0) { /* Flow not backlogged any more */
612 heap_insert(&(p
->idle_heap
), q
->F
, q
);
613 } else { /* still backlogged */
615 * update F and position in backlogged queue, then
616 * put flow in not_eligible_heap (we will fix this later).
618 len
= (q
->head
)->dn_m
->m_pkthdr
.len
;
619 q
->F
+= (len
<<MY_M
)/(u_int64_t
) fs
->weight
;
620 if (DN_KEY_LEQ(q
->S
, p
->V
))
621 heap_insert(neh
, q
->S
, q
);
623 heap_insert(sch
, q
->F
, q
);
627 * now compute V = max(V, min(S_i)). Remember that all elements in sch
628 * have by definition S_i <= V so if sch is not empty, V is surely
629 * the max and we must not update it. Conversely, if sch is empty
630 * we only need to look at neh.
632 if (sch
->elements
== 0 && neh
->elements
> 0)
633 p
->V
= MAX64 ( p
->V
, neh
->p
[0].key
);
634 /* move from neh to sch any packets that have become eligible */
635 while (neh
->elements
> 0 && DN_KEY_LEQ(neh
->p
[0].key
, p
->V
) ) {
636 struct dn_flow_queue
*q
= neh
->p
[0].object
;
637 heap_extract(neh
, NULL
);
638 heap_insert(sch
, q
->F
, q
);
641 if (p
->if_name
[0] != '\0') {/* tx clock is from a real thing */
642 p
->numbytes
= -1 ; /* mark not ready for I/O */
646 if (sch
->elements
== 0 && neh
->elements
== 0 && p
->numbytes
>= 0
647 && p
->idle_heap
.elements
> 0) {
649 * no traffic and no events scheduled. We can get rid of idle-heap.
653 for (i
= 0 ; i
< p
->idle_heap
.elements
; i
++) {
654 struct dn_flow_queue
*q
= p
->idle_heap
.p
[i
].object
;
661 p
->idle_heap
.elements
= 0 ;
664 * If we are getting clocks from dummynet (not a real interface) and
665 * If we are under credit, schedule the next ready event.
666 * Also fix the delivery time of the last packet.
668 if (p
->if_name
[0]==0 && p
->numbytes
< 0) { /* this implies bandwidth >0 */
669 dn_key t
=0 ; /* number of ticks i have to wait */
671 if (p
->bandwidth
> 0)
672 t
= ( p
->bandwidth
-1 - p
->numbytes
) / p
->bandwidth
;
673 p
->tail
->output_time
+= t
;
674 p
->sched_time
= curr_time
;
675 heap_insert(&wfq_ready_heap
, curr_time
+ t
, (void *)p
);
676 /* XXX should check errors on heap_insert, and drain the whole
677 * queue on error hoping next time we are luckier.
681 * If the delay line was empty call transmit_event(p) now.
682 * Otherwise, the scheduler will take care of it.
689 * This is called once per tick, or HZ times per second. It is used to
690 * increment the current tick counter and schedule expired events.
693 dummynet(void * __unused unused
)
695 void *p
; /* generic parameter to handler */
697 struct dn_heap
*heaps
[3];
701 heaps
[0] = &ready_heap
; /* fixed-rate queues */
702 heaps
[1] = &wfq_ready_heap
; /* wfq queues */
703 heaps
[2] = &extract_heap
; /* delay line */
704 crit_enter(); /* see note on top, splnet() is not enough */
706 for (i
=0; i
< 3 ; i
++) {
708 while (h
->elements
> 0 && DN_KEY_LEQ(h
->p
[0].key
, curr_time
) ) {
709 DDB(if (h
->p
[0].key
> curr_time
)
710 kprintf("-- dummynet: warning, heap %d is %d ticks late\n",
711 i
, (int)(curr_time
- h
->p
[0].key
));)
712 p
= h
->p
[0].object
; /* store a copy before heap_extract */
713 heap_extract(h
, NULL
); /* need to extract before processing */
717 struct dn_pipe
*pipe
= p
;
718 if (pipe
->if_name
[0] != '\0')
719 kprintf("*** bad ready_event_wfq for pipe %s\n",
727 /* sweep pipes trying to expire idle flow_queues */
728 for (pe
= all_pipes
; pe
; pe
= pe
->next
)
729 if (pe
->idle_heap
.elements
> 0 &&
730 DN_KEY_LT(pe
->idle_heap
.p
[0].key
, pe
->V
) ) {
731 struct dn_flow_queue
*q
= pe
->idle_heap
.p
[0].object
;
733 heap_extract(&(pe
->idle_heap
), NULL
);
734 q
->S
= q
->F
+ 1 ; /* mark timestamp as invalid */
735 pe
->sum
-= q
->fs
->weight
;
738 callout_reset(&dn_timeout
, 1, dummynet
, NULL
);
742 * called by an interface when tx_rdy occurs.
745 if_tx_rdy(struct ifnet
*ifp
)
749 for (p
= all_pipes
; p
; p
= p
->next
)
753 for (p
= all_pipes
; p
; p
= p
->next
)
754 if (!strcmp(p
->if_name
, ifp
->if_xname
) ) {
756 DEB(kprintf("++ tx rdy from %s (now found)\n", ifp
->if_xname
);)
761 DEB(kprintf("++ tx rdy from %s - qlen %d\n", ifp
->if_xname
,
762 ifp
->if_snd
.ifq_len
);)
763 p
->numbytes
= 0 ; /* mark ready for I/O */
770 * Unconditionally expire empty queues in case of shortage.
771 * Returns the number of queues freed.
774 expire_queues(struct dn_flow_set
*fs
)
776 struct dn_flow_queue
*q
, *prev
;
777 int i
, initial_elements
= fs
->rq_elements
;
779 if (fs
->last_expired
== time_second
)
781 fs
->last_expired
= time_second
;
782 for (i
= 0 ; i
<= fs
->rq_size
; i
++) /* last one is overflow */
783 for (prev
=NULL
, q
= fs
->rq
[i
] ; q
!= NULL
; )
784 if (q
->head
!= NULL
|| q
->S
!= q
->F
+1) {
787 } else { /* entry is idle, expire it */
788 struct dn_flow_queue
*old_q
= q
;
791 prev
->next
= q
= q
->next
;
793 fs
->rq
[i
] = q
= q
->next
;
795 kfree(old_q
, M_DUMMYNET
);
797 return initial_elements
- fs
->rq_elements
;
801 * If room, create a new queue and put at head of slot i;
802 * otherwise, create or use the default queue.
804 static struct dn_flow_queue
*
805 create_queue(struct dn_flow_set
*fs
, int i
)
807 struct dn_flow_queue
*q
;
809 if (fs
->rq_elements
> fs
->rq_size
* dn_max_ratio
&&
810 expire_queues(fs
) == 0) {
812 * No way to get room, use or create overflow queue.
815 if ( fs
->rq
[i
] != NULL
)
818 q
= kmalloc(sizeof(*q
), M_DUMMYNET
, M_WAITOK
| M_ZERO
);
821 q
->next
= fs
->rq
[i
] ;
822 q
->S
= q
->F
+ 1; /* hack - mark timestamp as invalid */
829 * Given a flow_set and a pkt in last_pkt, find a matching queue
830 * after appropriate masking. The queue is moved to front
831 * so that further searches take less time.
833 static struct dn_flow_queue
*
834 find_queue(struct dn_flow_set
*fs
, struct ipfw_flow_id
*id
)
836 int i
= 0 ; /* we need i and q for new allocations */
837 struct dn_flow_queue
*q
, *prev
;
839 if ( !(fs
->flags_fs
& DN_HAVE_FLOW_MASK
) )
842 /* first, do the masking */
843 id
->dst_ip
&= fs
->flow_mask
.dst_ip
;
844 id
->src_ip
&= fs
->flow_mask
.src_ip
;
845 id
->dst_port
&= fs
->flow_mask
.dst_port
;
846 id
->src_port
&= fs
->flow_mask
.src_port
;
847 id
->proto
&= fs
->flow_mask
.proto
;
848 id
->flags
= 0 ; /* we don't care about this one */
849 /* then, hash function */
850 i
= ( (id
->dst_ip
) & 0xffff ) ^
851 ( (id
->dst_ip
>> 15) & 0xffff ) ^
852 ( (id
->src_ip
<< 1) & 0xffff ) ^
853 ( (id
->src_ip
>> 16 ) & 0xffff ) ^
854 (id
->dst_port
<< 1) ^ (id
->src_port
) ^
856 i
= i
% fs
->rq_size
;
857 /* finally, scan the current list for a match */
859 for (prev
=NULL
, q
= fs
->rq
[i
] ; q
; ) {
861 if (id
->dst_ip
== q
->id
.dst_ip
&&
862 id
->src_ip
== q
->id
.src_ip
&&
863 id
->dst_port
== q
->id
.dst_port
&&
864 id
->src_port
== q
->id
.src_port
&&
865 id
->proto
== q
->id
.proto
&&
866 id
->flags
== q
->id
.flags
)
868 else if (pipe_expire
&& q
->head
== NULL
&& q
->S
== q
->F
+1 ) {
869 /* entry is idle and not in any heap, expire it */
870 struct dn_flow_queue
*old_q
= q
;
873 prev
->next
= q
= q
->next
;
875 fs
->rq
[i
] = q
= q
->next
;
877 kfree(old_q
, M_DUMMYNET
);
883 if (q
&& prev
!= NULL
) { /* found and not in front */
884 prev
->next
= q
->next
;
885 q
->next
= fs
->rq
[i
] ;
889 if (q
== NULL
) { /* no match, need to allocate a new entry */
890 q
= create_queue(fs
, i
);
898 red_drops(struct dn_flow_set
*fs
, struct dn_flow_queue
*q
, int len
)
903 * RED calculates the average queue size (avg) using a low-pass filter
904 * with an exponential weighted (w_q) moving average:
905 * avg <- (1-w_q) * avg + w_q * q_size
906 * where q_size is the queue length (measured in bytes or * packets).
908 * If q_size == 0, we compute the idle time for the link, and set
909 * avg = (1 - w_q)^(idle/s)
910 * where s is the time needed for transmitting a medium-sized packet.
912 * Now, if avg < min_th the packet is enqueued.
913 * If avg > max_th the packet is dropped. Otherwise, the packet is
914 * dropped with probability P function of avg.
919 /* queue in bytes or packets ? */
920 u_int q_size
= (fs
->flags_fs
& DN_QSIZE_IS_BYTES
) ? q
->len_bytes
: q
->len
;
922 DEB(kprintf("\n%d q: %2u ", (int) curr_time
, q_size
);)
924 /* average queue size estimation */
927 * queue is not empty, avg <- avg + (q_size - avg) * w_q
929 int diff
= SCALE(q_size
) - q
->avg
;
930 int64_t v
= SCALE_MUL((int64_t) diff
, (int64_t) fs
->w_q
);
935 * queue is empty, find for how long the queue has been
936 * empty and use a lookup table for computing
937 * (1 - * w_q)^(idle_time/s) where s is the time to send a
942 u_int t
= (curr_time
- q
->q_time
) / fs
->lookup_step
;
944 q
->avg
= (t
< fs
->lookup_depth
) ?
945 SCALE_MUL(q
->avg
, fs
->w_q_lookup
[t
]) : 0;
948 DEB(kprintf("avg: %u ", SCALE_VAL(q
->avg
));)
950 /* should i drop ? */
952 if (q
->avg
< fs
->min_th
) {
954 return 0; /* accept packet ; */
956 if (q
->avg
>= fs
->max_th
) { /* average queue >= max threshold */
957 if (fs
->flags_fs
& DN_IS_GENTLE_RED
) {
959 * According to Gentle-RED, if avg is greater than max_th the
960 * packet is dropped with a probability
961 * p_b = c_3 * avg - c_4
962 * where c_3 = (1 - max_p) / max_th, and c_4 = 1 - 2 * max_p
964 p_b
= SCALE_MUL((int64_t) fs
->c_3
, (int64_t) q
->avg
) - fs
->c_4
;
970 } else if (q
->avg
> fs
->min_th
) {
972 * we compute p_b using the linear dropping function p_b = c_1 *
973 * avg - c_2, where c_1 = max_p / (max_th - min_th), and c_2 =
974 * max_p * min_th / (max_th - min_th)
976 p_b
= SCALE_MUL((int64_t) fs
->c_1
, (int64_t) q
->avg
) - fs
->c_2
;
978 if (fs
->flags_fs
& DN_QSIZE_IS_BYTES
)
979 p_b
= (p_b
* len
) / fs
->max_pkt_size
;
981 q
->random
= krandom() & 0xffff;
984 * q->count counts packets arrived since last drop, so a greater
985 * value of q->count means a greater packet drop probability.
987 if (SCALE_MUL(p_b
, SCALE((int64_t) q
->count
)) > q
->random
) {
989 DEB(kprintf("- red drop");)
990 /* after a drop we calculate a new random value */
991 q
->random
= krandom() & 0xffff;
995 /* end of RED algorithm */
996 return 0 ; /* accept */
1000 struct dn_flow_set
*
1001 locate_flowset(int pipe_nr
, struct ip_fw
*rule
)
1003 struct dn_flow_set
*fs
;
1004 ipfw_insn
*cmd
= rule
->cmd
+ rule
->act_ofs
;
1006 if (cmd
->opcode
== O_LOG
)
1008 fs
= ((ipfw_insn_pipe
*)cmd
)->pipe_ptr
;
1013 if (cmd
->opcode
== O_QUEUE
)
1014 for (fs
=all_flow_sets
; fs
&& fs
->fs_nr
!= pipe_nr
; fs
=fs
->next
)
1018 for (p1
= all_pipes
; p1
&& p1
->pipe_nr
!= pipe_nr
; p1
= p1
->next
)
1023 /* record for the future */
1024 ((ipfw_insn_pipe
*)cmd
)->pipe_ptr
= fs
;
1029 * dummynet hook for packets. Below 'pipe' is a pipe or a queue
1030 * depending on whether WF2Q or fixed bw is used.
1032 * pipe_nr pipe or queue the packet is destined for.
1033 * dir where shall we send the packet after dummynet.
1034 * m the mbuf with the packet
1035 * ifp the 'ifp' parameter from the caller.
1036 * NULL in ip_input, destination interface in ip_output
1037 * ro route parameter (only used in ip_output, NULL otherwise)
1038 * dst destination address, only used by ip_output
1039 * rule matching rule, in case of multiple passes
1040 * flags flags from the caller, only used in ip_output
1044 dummynet_io(struct mbuf
*m
, int pipe_nr
, int dir
, struct ip_fw_args
*fwa
)
1047 struct dn_flow_set
*fs
;
1048 struct dn_pipe
*pipe
;
1049 u_int64_t len
= m
->m_pkthdr
.len
;
1050 struct dn_flow_queue
*q
= NULL
;
1054 ipfw_insn
*cmd
= fwa
->rule
->cmd
+ fwa
->rule
->act_ofs
;
1056 if (cmd
->opcode
== O_LOG
)
1058 is_pipe
= (cmd
->opcode
== O_PIPE
);
1063 * this is a dummynet rule, so we expect a O_PIPE or O_QUEUE rule
1065 fs
= locate_flowset(pipe_nr
, fwa
->rule
);
1067 goto dropit
; /* this queue/pipe does not exist! */
1069 if (pipe
== NULL
) { /* must be a queue, try find a matching pipe */
1070 for (pipe
= all_pipes
; pipe
&& pipe
->pipe_nr
!= fs
->parent_nr
;
1076 kprintf("No pipe %d for queue %d, drop pkt\n",
1077 fs
->parent_nr
, fs
->fs_nr
);
1081 q
= find_queue(fs
, &(fwa
->f_id
));
1083 goto dropit
; /* cannot allocate queue */
1085 * update statistics, then check reasons to drop pkt
1087 q
->tot_bytes
+= len
;
1089 if ( fs
->plr
&& krandom() < fs
->plr
)
1090 goto dropit
; /* random pkt drop */
1091 if ( fs
->flags_fs
& DN_QSIZE_IS_BYTES
) {
1092 if (q
->len_bytes
> fs
->qsize
)
1093 goto dropit
; /* queue size overflow */
1095 if (q
->len
>= fs
->qsize
)
1096 goto dropit
; /* queue count overflow */
1098 if ( fs
->flags_fs
& DN_IS_RED
&& red_drops(fs
, q
, len
) )
1101 /* XXX expensive to zero, see if we can remove it*/
1102 pkt
= kmalloc(sizeof (*pkt
), M_DUMMYNET
, M_INTWAIT
| M_ZERO
| M_NULLOK
);
1104 goto dropit
; /* cannot allocate packet header */
1106 /* ok, i can handle the pkt now... */
1107 /* build and enqueue packet + parameters */
1108 pkt
->hdr
.mh_type
= MT_TAG
;
1109 pkt
->hdr
.mh_flags
= PACKET_TAG_DUMMYNET
;
1110 pkt
->rule
= fwa
->rule
;
1111 DN_NEXT_NC(pkt
) = NULL
;
1115 pkt
->ifp
= fwa
->oif
;
1116 if (dir
== DN_TO_IP_OUT
) {
1118 * We need to copy *ro because for ICMP pkts (and maybe others)
1119 * the caller passed a pointer into the stack; dst might also be
1120 * a pointer into *ro so it needs to be updated.
1122 pkt
->ro
= *(fwa
->ro
);
1124 fwa
->ro
->ro_rt
->rt_refcnt
++ ;
1125 if (fwa
->dst
== (struct sockaddr_in
*)&fwa
->ro
->ro_dst
) /* dst points into ro */
1126 fwa
->dst
= (struct sockaddr_in
*)&(pkt
->ro
.ro_dst
) ;
1128 pkt
->dn_dst
= fwa
->dst
;
1129 pkt
->flags
= fwa
->flags
;
1131 if (q
->head
== NULL
)
1134 DN_NEXT_NC(q
->tail
) = (struct mbuf
*)pkt
;
1137 q
->len_bytes
+= len
;
1139 if ( q
->head
!= pkt
) /* flow was not idle, we are done */
1142 * If we reach this point the flow was previously idle, so we need
1143 * to schedule it. This involves different actions for fixed-rate or
1148 * Fixed-rate queue: just insert into the ready_heap.
1151 if (pipe
->bandwidth
)
1152 t
= SET_TICKS(pkt
, q
, pipe
);
1153 q
->sched_time
= curr_time
;
1154 if (t
== 0) /* must process it now */
1157 heap_insert(&ready_heap
, curr_time
+ t
, q
);
1160 * WF2Q. First, compute start time S: if the flow was idle (S=F+1)
1161 * set S to the virtual time V for the controlling pipe, and update
1162 * the sum of weights for the pipe; otherwise, remove flow from
1163 * idle_heap and set S to max(F,V).
1164 * Second, compute finish time F = S + len/weight.
1165 * Third, if pipe was idle, update V=max(S, V).
1166 * Fourth, count one more backlogged flow.
1168 if (DN_KEY_GT(q
->S
, q
->F
)) { /* means timestamps are invalid */
1170 pipe
->sum
+= fs
->weight
; /* add weight of new queue */
1172 heap_extract(&(pipe
->idle_heap
), q
);
1173 q
->S
= MAX64(q
->F
, pipe
->V
) ;
1175 q
->F
= q
->S
+ ( len
<<MY_M
)/(u_int64_t
) fs
->weight
;
1177 if (pipe
->not_eligible_heap
.elements
== 0 &&
1178 pipe
->scheduler_heap
.elements
== 0)
1179 pipe
->V
= MAX64 ( q
->S
, pipe
->V
);
1182 * Look at eligibility. A flow is not eligibile if S>V (when
1183 * this happens, it means that there is some other flow already
1184 * scheduled for the same pipe, so the scheduler_heap cannot be
1185 * empty). If the flow is not eligible we just store it in the
1186 * not_eligible_heap. Otherwise, we store in the scheduler_heap
1187 * and possibly invoke ready_event_wfq() right now if there is
1189 * Note that for all flows in scheduler_heap (SCH), S_i <= V,
1190 * and for all flows in not_eligible_heap (NEH), S_i > V .
1191 * So when we need to compute max( V, min(S_i) ) forall i in SCH+NEH,
1192 * we only need to look into NEH.
1194 if (DN_KEY_GT(q
->S
, pipe
->V
) ) { /* not eligible */
1195 if (pipe
->scheduler_heap
.elements
== 0)
1196 kprintf("++ ouch! not eligible but empty scheduler!\n");
1197 heap_insert(&(pipe
->not_eligible_heap
), q
->S
, q
);
1199 heap_insert(&(pipe
->scheduler_heap
), q
->F
, q
);
1200 if (pipe
->numbytes
>= 0) { /* pipe is idle */
1201 if (pipe
->scheduler_heap
.elements
!= 1)
1202 kprintf("*** OUCH! pipe should have been idle!\n");
1203 DEB(kprintf("Waking up pipe %d at %d\n",
1204 pipe
->pipe_nr
, (int)(q
->F
>> MY_M
)); )
1205 pipe
->sched_time
= curr_time
;
1206 ready_event_wfq(pipe
);
1219 return ( (fs
&& (fs
->flags_fs
& DN_NOERROR
)) ? 0 : ENOBUFS
);
1223 * Below, the rt_unref is only needed when (pkt->dn_dir == DN_TO_IP_OUT)
1224 * Doing this would probably save us the initial bzero of dn_pkt
1226 #define DN_FREE_PKT(pkt) { \
1227 struct dn_pkt *n = pkt ; \
1228 rt_unref ( n->ro.ro_rt ) ; \
1230 pkt = DN_NEXT(n) ; \
1231 kfree(n, M_DUMMYNET) ; }
1234 * Dispose all packets and flow_queues on a flow_set.
1235 * If all=1, also remove red lookup table and other storage,
1236 * including the descriptor itself.
1237 * For the one in dn_pipe MUST also cleanup ready_heap...
1240 purge_flow_set(struct dn_flow_set
*fs
, int all
)
1242 struct dn_pkt
*pkt
;
1243 struct dn_flow_queue
*q
, *qn
;
1246 for (i
= 0 ; i
<= fs
->rq_size
; i
++ ) {
1247 for (q
= fs
->rq
[i
] ; q
; q
= qn
) {
1248 for (pkt
= q
->head
; pkt
; )
1251 kfree(q
, M_DUMMYNET
);
1255 fs
->rq_elements
= 0 ;
1257 /* RED - free lookup table */
1259 kfree(fs
->w_q_lookup
, M_DUMMYNET
);
1261 kfree(fs
->rq
, M_DUMMYNET
);
1262 /* if this fs is not part of a pipe, free it */
1263 if (fs
->pipe
&& fs
!= &(fs
->pipe
->fs
) )
1264 kfree(fs
, M_DUMMYNET
);
1269 * Dispose all packets queued on a pipe (not a flow_set).
1270 * Also free all resources associated to a pipe, which is about
1274 purge_pipe(struct dn_pipe
*pipe
)
1276 struct dn_pkt
*pkt
;
1278 purge_flow_set( &(pipe
->fs
), 1 );
1280 for (pkt
= pipe
->head
; pkt
; )
1283 heap_free( &(pipe
->scheduler_heap
) );
1284 heap_free( &(pipe
->not_eligible_heap
) );
1285 heap_free( &(pipe
->idle_heap
) );
1289 * Delete all pipes and heaps returning memory. Must also
1290 * remove references from all ipfw rules to all pipes.
1293 dummynet_flush(void)
1295 struct dn_pipe
*curr_p
, *p
;
1296 struct dn_flow_set
*fs
, *curr_fs
;
1300 /* remove all references to pipes ...*/
1301 flush_pipe_ptrs(NULL
);
1302 /* prevent future matches... */
1305 fs
= all_flow_sets
;
1306 all_flow_sets
= NULL
;
1307 /* and free heaps so we don't have unwanted events */
1308 heap_free(&ready_heap
);
1309 heap_free(&wfq_ready_heap
);
1310 heap_free(&extract_heap
);
1313 * Now purge all queued pkts and delete all pipes
1315 /* scan and purge all flow_sets. */
1319 purge_flow_set(curr_fs
, 1);
1325 kfree(curr_p
, M_DUMMYNET
);
1330 extern struct ip_fw
*ip_fw_default_rule
;
1332 dn_rule_delete_fs(struct dn_flow_set
*fs
, void *r
)
1335 struct dn_flow_queue
*q
;
1336 struct dn_pkt
*pkt
;
1338 for (i
= 0 ; i
<= fs
->rq_size
; i
++) /* last one is ovflow */
1339 for (q
= fs
->rq
[i
] ; q
; q
= q
->next
)
1340 for (pkt
= q
->head
; pkt
; pkt
= DN_NEXT(pkt
) )
1342 pkt
->rule
= ip_fw_default_rule
;
1345 * when a firewall rule is deleted, scan all queues and remove the flow-id
1346 * from packets matching this rule.
1349 dn_rule_delete(void *r
)
1352 struct dn_pkt
*pkt
;
1353 struct dn_flow_set
*fs
;
1356 * If the rule references a queue (dn_flow_set), then scan
1357 * the flow set, otherwise scan pipes. Should do either, but doing
1358 * both does not harm.
1360 for ( fs
= all_flow_sets
; fs
; fs
= fs
->next
)
1361 dn_rule_delete_fs(fs
, r
);
1362 for ( p
= all_pipes
; p
; p
= p
->next
) {
1364 dn_rule_delete_fs(fs
, r
);
1365 for (pkt
= p
->head
; pkt
; pkt
= DN_NEXT(pkt
) )
1367 pkt
->rule
= ip_fw_default_rule
;
1372 * setup RED parameters
1375 config_red(struct dn_flow_set
*p
, struct dn_flow_set
* x
)
1380 x
->min_th
= SCALE(p
->min_th
);
1381 x
->max_th
= SCALE(p
->max_th
);
1382 x
->max_p
= p
->max_p
;
1384 x
->c_1
= p
->max_p
/ (p
->max_th
- p
->min_th
);
1385 x
->c_2
= SCALE_MUL(x
->c_1
, SCALE(p
->min_th
));
1386 if (x
->flags_fs
& DN_IS_GENTLE_RED
) {
1387 x
->c_3
= (SCALE(1) - p
->max_p
) / p
->max_th
;
1388 x
->c_4
= (SCALE(1) - 2 * p
->max_p
);
1391 /* if the lookup table already exist, free and create it again */
1392 if (x
->w_q_lookup
) {
1393 kfree(x
->w_q_lookup
, M_DUMMYNET
);
1394 x
->w_q_lookup
= NULL
;
1396 if (red_lookup_depth
== 0) {
1397 kprintf("\nnet.inet.ip.dummynet.red_lookup_depth must be > 0");
1398 kfree(x
, M_DUMMYNET
);
1401 x
->lookup_depth
= red_lookup_depth
;
1402 x
->w_q_lookup
= kmalloc(x
->lookup_depth
* sizeof(int),
1403 M_DUMMYNET
, M_WAITOK
);
1405 /* fill the lookup table with (1 - w_q)^x */
1406 x
->lookup_step
= p
->lookup_step
;
1407 x
->lookup_weight
= p
->lookup_weight
;
1408 x
->w_q_lookup
[0] = SCALE(1) - x
->w_q
;
1409 for (i
= 1; i
< x
->lookup_depth
; i
++)
1410 x
->w_q_lookup
[i
] = SCALE_MUL(x
->w_q_lookup
[i
- 1], x
->lookup_weight
);
1411 if (red_avg_pkt_size
< 1)
1412 red_avg_pkt_size
= 512 ;
1413 x
->avg_pkt_size
= red_avg_pkt_size
;
1414 if (red_max_pkt_size
< 1)
1415 red_max_pkt_size
= 1500 ;
1416 x
->max_pkt_size
= red_max_pkt_size
;
1421 alloc_hash(struct dn_flow_set
*x
, struct dn_flow_set
*pfs
)
1423 if (x
->flags_fs
& DN_HAVE_FLOW_MASK
) { /* allocate some slots */
1424 int l
= pfs
->rq_size
;
1430 else if (l
> DN_MAX_HASH_SIZE
)
1431 l
= DN_MAX_HASH_SIZE
;
1433 } else /* one is enough for null mask */
1435 x
->rq
= kmalloc((1 + x
->rq_size
) * sizeof(struct dn_flow_queue
*),
1436 M_DUMMYNET
, M_WAITOK
| M_ZERO
);
1442 set_fs_parms(struct dn_flow_set
*x
, struct dn_flow_set
*src
)
1444 x
->flags_fs
= src
->flags_fs
;
1445 x
->qsize
= src
->qsize
;
1447 x
->flow_mask
= src
->flow_mask
;
1448 if (x
->flags_fs
& DN_QSIZE_IS_BYTES
) {
1449 if (x
->qsize
> 1024*1024)
1450 x
->qsize
= 1024*1024 ;
1457 /* configuring RED */
1458 if ( x
->flags_fs
& DN_IS_RED
)
1459 config_red(src
, x
) ; /* XXX should check errors */
1463 * setup pipe or queue parameters.
1467 config_pipe(struct dn_pipe
*p
)
1470 struct dn_flow_set
*pfs
= &(p
->fs
);
1471 struct dn_flow_queue
*q
;
1474 * The config program passes parameters as follows:
1475 * bw = bits/second (0 means no limits),
1476 * delay = ms, must be translated into ticks.
1477 * qsize = slots/bytes
1479 p
->delay
= ( p
->delay
* hz
) / 1000 ;
1480 /* We need either a pipe number or a flow_set number */
1481 if (p
->pipe_nr
== 0 && pfs
->fs_nr
== 0)
1483 if (p
->pipe_nr
!= 0 && pfs
->fs_nr
!= 0)
1485 if (p
->pipe_nr
!= 0) { /* this is a pipe */
1486 struct dn_pipe
*x
, *a
, *b
;
1488 for (a
= NULL
, b
= all_pipes
; b
&& b
->pipe_nr
< p
->pipe_nr
;
1489 a
= b
, b
= b
->next
) ;
1491 if (b
== NULL
|| b
->pipe_nr
!= p
->pipe_nr
) { /* new pipe */
1492 x
= kmalloc(sizeof(struct dn_pipe
), M_DUMMYNET
, M_WAITOK
| M_ZERO
);
1493 x
->pipe_nr
= p
->pipe_nr
;
1495 /* idle_heap is the only one from which we extract from the middle.
1497 x
->idle_heap
.size
= x
->idle_heap
.elements
= 0 ;
1498 x
->idle_heap
.offset
=OFFSET_OF(struct dn_flow_queue
, heap_pos
);
1502 /* Flush accumulated credit for all queues */
1503 for (i
= 0; i
<= x
->fs
.rq_size
; i
++)
1504 for (q
= x
->fs
.rq
[i
]; q
; q
= q
->next
)
1510 x
->bandwidth
= p
->bandwidth
;
1511 x
->numbytes
= 0; /* just in case... */
1512 bcopy(p
->if_name
, x
->if_name
, sizeof(p
->if_name
) );
1513 x
->ifp
= NULL
; /* reset interface ptr */
1514 x
->delay
= p
->delay
;
1515 set_fs_parms(&(x
->fs
), pfs
);
1518 if ( x
->fs
.rq
== NULL
) { /* a new pipe */
1519 s
= alloc_hash(&(x
->fs
), pfs
) ;
1521 kfree(x
, M_DUMMYNET
);
1531 } else { /* config queue */
1532 struct dn_flow_set
*x
, *a
, *b
;
1534 /* locate flow_set */
1535 for (a
=NULL
, b
=all_flow_sets
; b
&& b
->fs_nr
< pfs
->fs_nr
;
1536 a
= b
, b
= b
->next
) ;
1538 if (b
== NULL
|| b
->fs_nr
!= pfs
->fs_nr
) { /* new */
1539 if (pfs
->parent_nr
== 0) /* need link to a pipe */
1541 x
= kmalloc(sizeof(struct dn_flow_set
), M_DUMMYNET
, M_WAITOK
|M_ZERO
);
1542 x
->fs_nr
= pfs
->fs_nr
;
1543 x
->parent_nr
= pfs
->parent_nr
;
1544 x
->weight
= pfs
->weight
;
1547 else if (x
->weight
> 100)
1550 /* Change parent pipe not allowed; must delete and recreate */
1551 if (pfs
->parent_nr
!= 0 && b
->parent_nr
!= pfs
->parent_nr
)
1556 set_fs_parms(x
, pfs
);
1558 if ( x
->rq
== NULL
) { /* a new flow_set */
1559 s
= alloc_hash(x
, pfs
) ;
1561 kfree(x
, M_DUMMYNET
);
1576 * Helper function to remove from a heap queues which are linked to
1577 * a flow_set about to be deleted.
1580 fs_remove_from_heap(struct dn_heap
*h
, struct dn_flow_set
*fs
)
1582 int i
= 0, found
= 0 ;
1583 for (; i
< h
->elements
;)
1584 if ( ((struct dn_flow_queue
*)h
->p
[i
].object
)->fs
== fs
) {
1586 h
->p
[i
] = h
->p
[h
->elements
] ;
1595 * helper function to remove a pipe from a heap (can be there at most once)
1598 pipe_remove_from_heap(struct dn_heap
*h
, struct dn_pipe
*p
)
1600 if (h
->elements
> 0) {
1602 for (i
=0; i
< h
->elements
; i
++ ) {
1603 if (h
->p
[i
].object
== p
) { /* found it */
1605 h
->p
[i
] = h
->p
[h
->elements
] ;
1614 * drain all queues. Called in case of severe mbuf shortage.
1617 dummynet_drain(void)
1619 struct dn_flow_set
*fs
;
1623 heap_free(&ready_heap
);
1624 heap_free(&wfq_ready_heap
);
1625 heap_free(&extract_heap
);
1626 /* remove all references to this pipe from flow_sets */
1627 for (fs
= all_flow_sets
; fs
; fs
= fs
->next
)
1628 purge_flow_set(fs
, 0);
1630 for (p
= all_pipes
; p
; p
= p
->next
) {
1631 purge_flow_set(&(p
->fs
), 0);
1632 for (pkt
= p
->head
; pkt
; )
1634 p
->head
= p
->tail
= NULL
;
1639 * Fully delete a pipe or a queue, cleaning up associated info.
1642 delete_pipe(struct dn_pipe
*p
)
1644 if (p
->pipe_nr
== 0 && p
->fs
.fs_nr
== 0)
1646 if (p
->pipe_nr
!= 0 && p
->fs
.fs_nr
!= 0)
1648 if (p
->pipe_nr
!= 0) { /* this is an old-style pipe */
1649 struct dn_pipe
*a
, *b
;
1650 struct dn_flow_set
*fs
;
1653 for (a
= NULL
, b
= all_pipes
; b
&& b
->pipe_nr
< p
->pipe_nr
;
1654 a
= b
, b
= b
->next
) ;
1655 if (b
== NULL
|| (b
->pipe_nr
!= p
->pipe_nr
) )
1656 return EINVAL
; /* not found */
1660 /* unlink from list of pipes */
1662 all_pipes
= b
->next
;
1665 /* remove references to this pipe from the ip_fw rules. */
1666 flush_pipe_ptrs(&(b
->fs
));
1668 /* remove all references to this pipe from flow_sets */
1669 for (fs
= all_flow_sets
; fs
; fs
= fs
->next
)
1670 if (fs
->pipe
== b
) {
1671 kprintf("++ ref to pipe %d from fs %d\n",
1672 p
->pipe_nr
, fs
->fs_nr
);
1674 purge_flow_set(fs
, 0);
1676 fs_remove_from_heap(&ready_heap
, &(b
->fs
));
1677 purge_pipe(b
); /* remove all data associated to this pipe */
1678 /* remove reference to here from extract_heap and wfq_ready_heap */
1679 pipe_remove_from_heap(&extract_heap
, b
);
1680 pipe_remove_from_heap(&wfq_ready_heap
, b
);
1682 kfree(b
, M_DUMMYNET
);
1683 } else { /* this is a WF2Q queue (dn_flow_set) */
1684 struct dn_flow_set
*a
, *b
;
1687 for (a
= NULL
, b
= all_flow_sets
; b
&& b
->fs_nr
< p
->fs
.fs_nr
;
1688 a
= b
, b
= b
->next
) ;
1689 if (b
== NULL
|| (b
->fs_nr
!= p
->fs
.fs_nr
) )
1690 return EINVAL
; /* not found */
1694 all_flow_sets
= b
->next
;
1697 /* remove references to this flow_set from the ip_fw rules. */
1700 if (b
->pipe
!= NULL
) {
1701 /* Update total weight on parent pipe and cleanup parent heaps */
1702 b
->pipe
->sum
-= b
->weight
* b
->backlogged
;
1703 fs_remove_from_heap(&(b
->pipe
->not_eligible_heap
), b
);
1704 fs_remove_from_heap(&(b
->pipe
->scheduler_heap
), b
);
1705 #if 1 /* XXX should i remove from idle_heap as well ? */
1706 fs_remove_from_heap(&(b
->pipe
->idle_heap
), b
);
1709 purge_flow_set(b
, 1);
1716 * helper function used to copy data from kernel in DUMMYNET_GET
1719 dn_copy_set(struct dn_flow_set
*set
, char *bp
)
1722 struct dn_flow_queue
*q
, *qp
= (struct dn_flow_queue
*)bp
;
1724 for (i
= 0 ; i
<= set
->rq_size
; i
++)
1725 for (q
= set
->rq
[i
] ; q
; q
= q
->next
, qp
++ ) {
1726 if (q
->hash_slot
!= i
)
1727 kprintf("++ at %d: wrong slot (have %d, "
1728 "should be %d)\n", copied
, q
->hash_slot
, i
);
1730 kprintf("++ at %d: wrong fs ptr (have %p, should be %p)\n",
1733 bcopy(q
, qp
, sizeof( *q
) );
1734 /* cleanup pointers */
1736 qp
->head
= qp
->tail
= NULL
;
1739 if (copied
!= set
->rq_elements
)
1740 kprintf("++ wrong count, have %d should be %d\n",
1741 copied
, set
->rq_elements
);
1746 dummynet_get(struct sockopt
*sopt
)
1748 char *buf
, *bp
; /* bp is the "copy-pointer" */
1750 struct dn_flow_set
*set
;
1756 * compute size of data structures: list of pipes and flow_sets.
1758 for (p
= all_pipes
, size
= 0 ; p
; p
= p
->next
)
1759 size
+= sizeof( *p
) +
1760 p
->fs
.rq_elements
* sizeof(struct dn_flow_queue
);
1761 for (set
= all_flow_sets
; set
; set
= set
->next
)
1762 size
+= sizeof ( *set
) +
1763 set
->rq_elements
* sizeof(struct dn_flow_queue
);
1764 buf
= kmalloc(size
, M_TEMP
, M_WAITOK
);
1765 for (p
= all_pipes
, bp
= buf
; p
; p
= p
->next
) {
1766 struct dn_pipe
*pipe_bp
= (struct dn_pipe
*)bp
;
1769 * copy pipe descriptor into *bp, convert delay back to ms,
1770 * then copy the flow_set descriptor(s) one at a time.
1771 * After each flow_set, copy the queue descriptor it owns.
1773 bcopy(p
, bp
, sizeof( *p
) );
1774 pipe_bp
->delay
= (pipe_bp
->delay
* 1000) / hz
;
1776 * XXX the following is a hack based on ->next being the
1777 * first field in dn_pipe and dn_flow_set. The correct
1778 * solution would be to move the dn_flow_set to the beginning
1779 * of struct dn_pipe.
1781 pipe_bp
->next
= (struct dn_pipe
*)DN_IS_PIPE
;
1782 /* clean pointers */
1783 pipe_bp
->head
= pipe_bp
->tail
= NULL
;
1784 pipe_bp
->fs
.next
= NULL
;
1785 pipe_bp
->fs
.pipe
= NULL
;
1786 pipe_bp
->fs
.rq
= NULL
;
1788 bp
+= sizeof( *p
) ;
1789 bp
= dn_copy_set( &(p
->fs
), bp
);
1791 for (set
= all_flow_sets
; set
; set
= set
->next
) {
1792 struct dn_flow_set
*fs_bp
= (struct dn_flow_set
*)bp
;
1793 bcopy(set
, bp
, sizeof( *set
) );
1794 /* XXX same hack as above */
1795 fs_bp
->next
= (struct dn_flow_set
*)DN_IS_QUEUE
;
1796 fs_bp
->pipe
= NULL
;
1798 bp
+= sizeof( *set
) ;
1799 bp
= dn_copy_set( set
, bp
);
1802 error
= sooptcopyout(sopt
, buf
, size
);
1808 * Handler for the various dummynet socket options (get, flush, config, del)
1811 ip_dn_ctl(struct sockopt
*sopt
)
1814 struct dn_pipe
*p
, tmp_pipe
;
1816 /* Disallow sets in really-really secure mode. */
1817 if (sopt
->sopt_dir
== SOPT_SET
) {
1818 #if defined(__FreeBSD__) && __FreeBSD_version >= 500034
1819 error
= securelevel_ge(sopt
->sopt_td
->td_ucred
, 3);
1823 if (securelevel
>= 3)
1828 switch (sopt
->sopt_name
) {
1830 kprintf("ip_dn_ctl -- unknown option %d", sopt
->sopt_name
);
1833 case IP_DUMMYNET_GET
:
1834 error
= dummynet_get(sopt
);
1837 case IP_DUMMYNET_FLUSH
:
1841 case IP_DUMMYNET_CONFIGURE
:
1843 error
= sooptcopyin(sopt
, p
, sizeof *p
, sizeof *p
);
1846 error
= config_pipe(p
);
1849 case IP_DUMMYNET_DEL
: /* remove a pipe or queue */
1851 error
= sooptcopyin(sopt
, p
, sizeof *p
, sizeof *p
);
1855 error
= delete_pipe(p
);
1864 kprintf("DUMMYNET initialized (011031)\n");
1866 all_flow_sets
= NULL
;
1867 ready_heap
.size
= ready_heap
.elements
= 0 ;
1868 ready_heap
.offset
= 0 ;
1870 wfq_ready_heap
.size
= wfq_ready_heap
.elements
= 0 ;
1871 wfq_ready_heap
.offset
= 0 ;
1873 extract_heap
.size
= extract_heap
.elements
= 0 ;
1874 extract_heap
.offset
= 0 ;
1875 ip_dn_ctl_ptr
= ip_dn_ctl
;
1876 ip_dn_io_ptr
= dummynet_io
;
1877 ip_dn_ruledel_ptr
= dn_rule_delete
;
1878 callout_init(&dn_timeout
);
1879 callout_reset(&dn_timeout
, 1, dummynet
, NULL
);
1883 dummynet_modevent(module_t mod
, int type
, void *data
)
1888 if (DUMMYNET_LOADED
) {
1890 kprintf("DUMMYNET already loaded\n");
1898 #if !defined(KLD_MODULE)
1899 kprintf("dummynet statically compiled, cannot unload\n");
1903 callout_stop(&dn_timeout
);
1905 ip_dn_ctl_ptr
= NULL
;
1906 ip_dn_io_ptr
= NULL
;
1907 ip_dn_ruledel_ptr
= NULL
;
1917 static moduledata_t dummynet_mod
= {
1922 DECLARE_MODULE(dummynet
, dummynet_mod
, SI_SUB_PSEUDO
, SI_ORDER_ANY
);
1923 MODULE_DEPEND(dummynet
, ipfw
, 1, 1, 1);
1924 MODULE_VERSION(dummynet
, 1);