1*6a03354eSMatthew Dillon /* 2*6a03354eSMatthew Dillon * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa 3*6a03354eSMatthew Dillon * Portions Copyright (c) 2000 Akamba Corp. 4*6a03354eSMatthew Dillon * All rights reserved 5*6a03354eSMatthew Dillon * 6*6a03354eSMatthew Dillon * Redistribution and use in source and binary forms, with or without 7*6a03354eSMatthew Dillon * modification, are permitted provided that the following conditions 8*6a03354eSMatthew Dillon * are met: 9*6a03354eSMatthew Dillon * 1. Redistributions of source code must retain the above copyright 10*6a03354eSMatthew Dillon * notice, this list of conditions and the following disclaimer. 11*6a03354eSMatthew Dillon * 2. Redistributions in binary form must reproduce the above copyright 12*6a03354eSMatthew Dillon * notice, this list of conditions and the following disclaimer in the 13*6a03354eSMatthew Dillon * documentation and/or other materials provided with the distribution. 14*6a03354eSMatthew Dillon * 15*6a03354eSMatthew Dillon * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16*6a03354eSMatthew Dillon * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17*6a03354eSMatthew Dillon * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18*6a03354eSMatthew Dillon * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19*6a03354eSMatthew Dillon * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20*6a03354eSMatthew Dillon * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21*6a03354eSMatthew Dillon * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22*6a03354eSMatthew Dillon * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23*6a03354eSMatthew Dillon * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24*6a03354eSMatthew Dillon * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25*6a03354eSMatthew Dillon * SUCH DAMAGE. 26*6a03354eSMatthew Dillon * 27*6a03354eSMatthew Dillon * $FreeBSD: src/sys/netinet/ip_dummynet.h,v 1.10.2.9 2003/05/13 09:31:06 maxim Exp $ 28*6a03354eSMatthew Dillon * $DragonFly: src/sys/net/dummynet/ip_dummynet.h,v 1.19 2008/09/20 04:36:51 sephe Exp $ 29*6a03354eSMatthew Dillon */ 30*6a03354eSMatthew Dillon 31*6a03354eSMatthew Dillon #ifndef _IP_DUMMYNET3_H_ 32*6a03354eSMatthew Dillon #define _IP_DUMMYNET3_H_ 33*6a03354eSMatthew Dillon 34*6a03354eSMatthew Dillon #ifndef _IP_DUMMYNET_H 35*6a03354eSMatthew Dillon 36*6a03354eSMatthew Dillon #define MODULE_DUMMYNET_ID 2 37*6a03354eSMatthew Dillon #define MODULE_DUMMYNET_NAME "dummynet" 38*6a03354eSMatthew Dillon 39*6a03354eSMatthew Dillon 40*6a03354eSMatthew Dillon #ifdef _KERNEL 41*6a03354eSMatthew Dillon //placeholder for kernel 42*6a03354eSMatthew Dillon #endif 43*6a03354eSMatthew Dillon 44*6a03354eSMatthew Dillon enum ipfw_dummynet_opcodes { 45*6a03354eSMatthew Dillon O_DUMMYNET_PIPE, 46*6a03354eSMatthew Dillon O_DUMMYNET_QUEUE, 47*6a03354eSMatthew Dillon }; 48*6a03354eSMatthew Dillon 49*6a03354eSMatthew Dillon /* 50*6a03354eSMatthew Dillon * We start with a heap, which is used in the scheduler to decide when to 51*6a03354eSMatthew Dillon * transmit packets etc. 52*6a03354eSMatthew Dillon * 53*6a03354eSMatthew Dillon * The key for the heap is used for two different values: 54*6a03354eSMatthew Dillon * 55*6a03354eSMatthew Dillon * 1. Timer ticks- max 10K/second, so 32 bits are enough; 56*6a03354eSMatthew Dillon * 57*6a03354eSMatthew Dillon * 2. Virtual times. These increase in steps of len/x, where len is the 58*6a03354eSMatthew Dillon * packet length, and x is either the weight of the flow, or the sum 59*6a03354eSMatthew Dillon * of all weights. 60*6a03354eSMatthew Dillon * If we limit to max 1000 flows and a max weight of 100, then x needs 61*6a03354eSMatthew Dillon * 17 bits. The packet size is 16 bits, so we can easily overflow if 62*6a03354eSMatthew Dillon * we do not allow errors. 63*6a03354eSMatthew Dillon * 64*6a03354eSMatthew Dillon * So we use a key "dn_key" which is 64 bits. 65*6a03354eSMatthew Dillon * 66*6a03354eSMatthew Dillon * MY_M is used as a shift count when doing fixed point arithmetic 67*6a03354eSMatthew Dillon * (a better name would be useful...). 68*6a03354eSMatthew Dillon */ 69*6a03354eSMatthew Dillon typedef uint64_t dn_key; /* sorting key */ 70*6a03354eSMatthew Dillon 71*6a03354eSMatthew Dillon /* 72*6a03354eSMatthew Dillon * Number of left shift to obtain a larger precision 73*6a03354eSMatthew Dillon * 74*6a03354eSMatthew Dillon * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the 75*6a03354eSMatthew Dillon * virtual time wraps every 15 days. 76*6a03354eSMatthew Dillon */ 77*6a03354eSMatthew Dillon #define MY_M 16 78*6a03354eSMatthew Dillon 79*6a03354eSMatthew Dillon #ifdef _KERNEL 80*6a03354eSMatthew Dillon 81*6a03354eSMatthew Dillon /* 82*6a03354eSMatthew Dillon * A heap entry is made of a key and a pointer to the actual object stored 83*6a03354eSMatthew Dillon * in the heap. 84*6a03354eSMatthew Dillon * 85*6a03354eSMatthew Dillon * The heap is an array of dn_heap_entry entries, dynamically allocated. 86*6a03354eSMatthew Dillon * Current size is "size", with "elements" actually in use. 87*6a03354eSMatthew Dillon * 88*6a03354eSMatthew Dillon * The heap normally supports only ordered insert and extract from the top. 89*6a03354eSMatthew Dillon * If we want to extract an object from the middle of the heap, we have to 90*6a03354eSMatthew Dillon * know where the object itself is located in the heap (or we need to scan 91*6a03354eSMatthew Dillon * the whole array). To this purpose, an object has a field (int) which 92*6a03354eSMatthew Dillon * contains the index of the object itself into the heap. When the object 93*6a03354eSMatthew Dillon * is moved, the field must also be updated. The offset of the index in the 94*6a03354eSMatthew Dillon * object is stored in the 'offset' field in the heap descriptor. The 95*6a03354eSMatthew Dillon * assumption is that this offset is non-zero if we want to support extract 96*6a03354eSMatthew Dillon * from the middle. 97*6a03354eSMatthew Dillon */ 98*6a03354eSMatthew Dillon struct dn_heap_entry { 99*6a03354eSMatthew Dillon dn_key key; /* sorting key. Topmost element is smallest one */ 100*6a03354eSMatthew Dillon void *object; /* object pointer */ 101*6a03354eSMatthew Dillon }; 102*6a03354eSMatthew Dillon 103*6a03354eSMatthew Dillon struct dn_heap { 104*6a03354eSMatthew Dillon int size; 105*6a03354eSMatthew Dillon int elements; 106*6a03354eSMatthew Dillon int offset; /* XXX if > 0 this is the offset of direct ptr to obj */ 107*6a03354eSMatthew Dillon struct dn_heap_entry *p; /* really an array of "size" entries */ 108*6a03354eSMatthew Dillon }; 109*6a03354eSMatthew Dillon 110*6a03354eSMatthew Dillon struct dn_flow_id { 111*6a03354eSMatthew Dillon uint16_t fid_type; /* ETHERTYPE_ */ 112*6a03354eSMatthew Dillon uint16_t pad; 113*6a03354eSMatthew Dillon union { 114*6a03354eSMatthew Dillon struct { 115*6a03354eSMatthew Dillon uint32_t dst_ip; 116*6a03354eSMatthew Dillon uint32_t src_ip; 117*6a03354eSMatthew Dillon uint16_t dst_port; 118*6a03354eSMatthew Dillon uint16_t src_port; 119*6a03354eSMatthew Dillon uint8_t proto; 120*6a03354eSMatthew Dillon uint8_t flags; 121*6a03354eSMatthew Dillon } inet; 122*6a03354eSMatthew Dillon } fid_u; 123*6a03354eSMatthew Dillon #define fid_dst_ip fid_u.inet.dst_ip 124*6a03354eSMatthew Dillon #define fid_src_ip fid_u.inet.src_ip 125*6a03354eSMatthew Dillon #define fid_dst_port fid_u.inet.dst_port 126*6a03354eSMatthew Dillon #define fid_src_port fid_u.inet.src_port 127*6a03354eSMatthew Dillon #define fid_proto fid_u.inet.proto 128*6a03354eSMatthew Dillon #define fid_flags fid_u.inet.flags 129*6a03354eSMatthew Dillon }; 130*6a03354eSMatthew Dillon 131*6a03354eSMatthew Dillon typedef void (*ip_dn_unref_priv_t)(void *); 132*6a03354eSMatthew Dillon struct lwkt_port; 133*6a03354eSMatthew Dillon 134*6a03354eSMatthew Dillon /* 135*6a03354eSMatthew Dillon * struct dn_pkt identifies a packet in the dummynet queue, but is also used 136*6a03354eSMatthew Dillon * to tag packets passed back to the various destinations (ip_input(), 137*6a03354eSMatthew Dillon * ip_output() and so on). 138*6a03354eSMatthew Dillon * 139*6a03354eSMatthew Dillon * It is a tag (PACKET_TAG_DUMMYNET) associated with the actual mbuf. 140*6a03354eSMatthew Dillon */ 141*6a03354eSMatthew Dillon struct dn_pkt { 142*6a03354eSMatthew Dillon struct mbuf *dn_m; 143*6a03354eSMatthew Dillon TAILQ_ENTRY(dn_pkt) dn_next; 144*6a03354eSMatthew Dillon 145*6a03354eSMatthew Dillon void *dn_priv; 146*6a03354eSMatthew Dillon ip_dn_unref_priv_t dn_unref_priv; 147*6a03354eSMatthew Dillon 148*6a03354eSMatthew Dillon uint32_t dn_flags; /* action when packet comes out. */ 149*6a03354eSMatthew Dillon #define DN_FLAGS_IS_PIPE 0x10 150*6a03354eSMatthew Dillon #define DN_FLAGS_DIR_MASK 0x0f 151*6a03354eSMatthew Dillon #define DN_TO_IP_OUT 1 152*6a03354eSMatthew Dillon #define DN_TO_IP_IN 2 153*6a03354eSMatthew Dillon #define DN_TO_ETH_DEMUX 4 154*6a03354eSMatthew Dillon #define DN_TO_ETH_OUT 5 155*6a03354eSMatthew Dillon #define DN_TO_MAX 6 156*6a03354eSMatthew Dillon 157*6a03354eSMatthew Dillon dn_key output_time; /* when the pkt is due for delivery */ 158*6a03354eSMatthew Dillon struct ifnet *ifp; /* interface, for ip_output */ 159*6a03354eSMatthew Dillon struct sockaddr_in *dn_dst; 160*6a03354eSMatthew Dillon struct route ro; /* route, for ip_output. MUST COPY */ 161*6a03354eSMatthew Dillon int flags; /* flags, for ip_output (IPv6 ?) */ 162*6a03354eSMatthew Dillon 163*6a03354eSMatthew Dillon u_short pipe_nr; /* pipe/flow_set number */ 164*6a03354eSMatthew Dillon u_short pad; 165*6a03354eSMatthew Dillon 166*6a03354eSMatthew Dillon struct dn_flow_id id; /* flow id */ 167*6a03354eSMatthew Dillon int cpuid; /* target cpuid, for assertion */ 168*6a03354eSMatthew Dillon struct lwkt_port *msgport; /* target msgport */ 169*6a03354eSMatthew Dillon }; 170*6a03354eSMatthew Dillon TAILQ_HEAD(dn_pkt_queue, dn_pkt); 171*6a03354eSMatthew Dillon 172*6a03354eSMatthew Dillon /* 173*6a03354eSMatthew Dillon * Overall structure of dummynet (with WF2Q+): 174*6a03354eSMatthew Dillon * 175*6a03354eSMatthew Dillon * In dummynet, packets are selected with the firewall rules, and passed to 176*6a03354eSMatthew Dillon * two different objects: PIPE or QUEUE. 177*6a03354eSMatthew Dillon * 178*6a03354eSMatthew Dillon * A QUEUE is just a queue with configurable size and queue management policy. 179*6a03354eSMatthew Dillon * It is also associated with a mask (to discriminate among different flows), 180*6a03354eSMatthew Dillon * a weight (used to give different shares of the bandwidth to different flows) 181*6a03354eSMatthew Dillon * and a "pipe", which essentially supplies the transmit clock for all queues 182*6a03354eSMatthew Dillon * associated with that pipe. 183*6a03354eSMatthew Dillon * 184*6a03354eSMatthew Dillon * A PIPE emulates a fixed-bandwidth link, whose bandwidth is configurable. 185*6a03354eSMatthew Dillon * The "clock" for a pipe comes from an internal timer. A pipe is also 186*6a03354eSMatthew Dillon * associated with one (or more, if masks are used) queue, where all packets 187*6a03354eSMatthew Dillon * for that pipe are stored. 188*6a03354eSMatthew Dillon * 189*6a03354eSMatthew Dillon * The bandwidth available on the pipe is shared by the queues associated with 190*6a03354eSMatthew Dillon * that pipe (only one in case the packet is sent to a PIPE) according to the 191*6a03354eSMatthew Dillon * WF2Q+ scheduling algorithm and the configured weights. 192*6a03354eSMatthew Dillon * 193*6a03354eSMatthew Dillon * In general, incoming packets are stored in the appropriate queue, which is 194*6a03354eSMatthew Dillon * then placed into one of a few heaps managed by a scheduler to decide when 195*6a03354eSMatthew Dillon * the packet should be extracted. The scheduler (a function called dummynet()) 196*6a03354eSMatthew Dillon * is run at every timer tick, and grabs queues from the head of the heaps when 197*6a03354eSMatthew Dillon * they are ready for processing. 198*6a03354eSMatthew Dillon * 199*6a03354eSMatthew Dillon * There are three data structures definining a pipe and associated queues: 200*6a03354eSMatthew Dillon * 201*6a03354eSMatthew Dillon * + dn_pipe, which contains the main configuration parameters related to 202*6a03354eSMatthew Dillon * delay and bandwidth; 203*6a03354eSMatthew Dillon * + dn_flow_set, which contains WF2Q+ configuration, flow masks, plr and 204*6a03354eSMatthew Dillon * RED configuration; 205*6a03354eSMatthew Dillon * + dn_flow_queue, which is the per-flow queue (containing the packets) 206*6a03354eSMatthew Dillon * 207*6a03354eSMatthew Dillon * Multiple dn_flow_set can be linked to the same pipe, and multiple 208*6a03354eSMatthew Dillon * dn_flow_queue can be linked to the same dn_flow_set. 209*6a03354eSMatthew Dillon * All data structures are linked in a linear list which is used for 210*6a03354eSMatthew Dillon * housekeeping purposes. 211*6a03354eSMatthew Dillon * 212*6a03354eSMatthew Dillon * During configuration, we create and initialize the dn_flow_set and dn_pipe 213*6a03354eSMatthew Dillon * structures (a dn_pipe also contains a dn_flow_set). 214*6a03354eSMatthew Dillon * 215*6a03354eSMatthew Dillon * At runtime: packets are sent to the appropriate dn_flow_set (either WFQ 216*6a03354eSMatthew Dillon * ones, or the one embedded in the dn_pipe for fixed-rate flows), which in 217*6a03354eSMatthew Dillon * turn dispatches them to the appropriate dn_flow_queue (created dynamically 218*6a03354eSMatthew Dillon * according to the masks). 219*6a03354eSMatthew Dillon * 220*6a03354eSMatthew Dillon * The transmit clock for fixed rate flows (ready_event()) selects the 221*6a03354eSMatthew Dillon * dn_flow_queue to be used to transmit the next packet. For WF2Q, 222*6a03354eSMatthew Dillon * wfq_ready_event() extract a pipe which in turn selects the right flow using 223*6a03354eSMatthew Dillon * a number of heaps defined into the pipe itself. 224*6a03354eSMatthew Dillon */ 225*6a03354eSMatthew Dillon 226*6a03354eSMatthew Dillon /* 227*6a03354eSMatthew Dillon * Per flow queue. This contains the flow identifier, the queue of packets, 228*6a03354eSMatthew Dillon * counters, and parameters used to support both RED and WF2Q+. 229*6a03354eSMatthew Dillon * 230*6a03354eSMatthew Dillon * A dn_flow_queue is created and initialized whenever a packet for a new 231*6a03354eSMatthew Dillon * flow arrives. 232*6a03354eSMatthew Dillon */ 233*6a03354eSMatthew Dillon struct dn_flow_queue { 234*6a03354eSMatthew Dillon struct dn_flow_id id; 235*6a03354eSMatthew Dillon LIST_ENTRY(dn_flow_queue) q_link; 236*6a03354eSMatthew Dillon 237*6a03354eSMatthew Dillon struct dn_pkt_queue queue; /* queue of packets */ 238*6a03354eSMatthew Dillon u_int len; 239*6a03354eSMatthew Dillon u_int len_bytes; 240*6a03354eSMatthew Dillon u_long numbytes; /* credit for transmission (dynamic queues) */ 241*6a03354eSMatthew Dillon 242*6a03354eSMatthew Dillon uint64_t tot_pkts; /* statistics counters */ 243*6a03354eSMatthew Dillon uint64_t tot_bytes; 244*6a03354eSMatthew Dillon uint32_t drops; 245*6a03354eSMatthew Dillon 246*6a03354eSMatthew Dillon int hash_slot; /* debugging/diagnostic */ 247*6a03354eSMatthew Dillon 248*6a03354eSMatthew Dillon /* RED parameters */ 249*6a03354eSMatthew Dillon int avg; /* average queue length est. (scaled) */ 250*6a03354eSMatthew Dillon int count; /* arrivals since last RED drop */ 251*6a03354eSMatthew Dillon int random; /* random value (scaled) */ 252*6a03354eSMatthew Dillon uint32_t q_time; /* start of queue idle time */ 253*6a03354eSMatthew Dillon 254*6a03354eSMatthew Dillon /* WF2Q+ support */ 255*6a03354eSMatthew Dillon struct dn_flow_set *fs; /* parent flow set */ 256*6a03354eSMatthew Dillon int heap_pos; /* position (index) of struct in heap */ 257*6a03354eSMatthew Dillon dn_key sched_time; /* current time when queue enters ready_heap */ 258*6a03354eSMatthew Dillon 259*6a03354eSMatthew Dillon dn_key S, F; /* start time, finish time */ 260*6a03354eSMatthew Dillon /* 261*6a03354eSMatthew Dillon * Setting F < S means the timestamp is invalid. We only need 262*6a03354eSMatthew Dillon * to test this when the queue is empty. 263*6a03354eSMatthew Dillon */ 264*6a03354eSMatthew Dillon }; 265*6a03354eSMatthew Dillon LIST_HEAD(dn_flowqueue_head, dn_flow_queue); 266*6a03354eSMatthew Dillon 267*6a03354eSMatthew Dillon /* 268*6a03354eSMatthew Dillon * flow_set descriptor. Contains the "template" parameters for the queue 269*6a03354eSMatthew Dillon * configuration, and pointers to the hash table of dn_flow_queue's. 270*6a03354eSMatthew Dillon * 271*6a03354eSMatthew Dillon * The hash table is an array of lists -- we identify the slot by hashing 272*6a03354eSMatthew Dillon * the flow-id, then scan the list looking for a match. 273*6a03354eSMatthew Dillon * The size of the hash table (buckets) is configurable on a per-queue basis. 274*6a03354eSMatthew Dillon * 275*6a03354eSMatthew Dillon * A dn_flow_set is created whenever a new queue or pipe is created (in the 276*6a03354eSMatthew Dillon * latter case, the structure is located inside the struct dn_pipe). 277*6a03354eSMatthew Dillon */ 278*6a03354eSMatthew Dillon struct dn_flow_set { 279*6a03354eSMatthew Dillon u_short fs_nr; /* flow_set number */ 280*6a03354eSMatthew Dillon u_short flags_fs; /* see 'Flow set flags' */ 281*6a03354eSMatthew Dillon 282*6a03354eSMatthew Dillon LIST_ENTRY(dn_flow_set) fs_link; 283*6a03354eSMatthew Dillon 284*6a03354eSMatthew Dillon struct dn_pipe *pipe; /* pointer to parent pipe */ 285*6a03354eSMatthew Dillon u_short parent_nr; /* parent pipe#, 0 if local to a pipe */ 286*6a03354eSMatthew Dillon 287*6a03354eSMatthew Dillon int weight; /* WFQ queue weight */ 288*6a03354eSMatthew Dillon int qsize; /* queue size in slots or bytes */ 289*6a03354eSMatthew Dillon int plr; /* pkt loss rate (2^31-1 means 100%) */ 290*6a03354eSMatthew Dillon 291*6a03354eSMatthew Dillon struct dn_flow_id flow_mask; 292*6a03354eSMatthew Dillon 293*6a03354eSMatthew Dillon /* hash table of queues onto this flow_set */ 294*6a03354eSMatthew Dillon int rq_size; /* number of slots */ 295*6a03354eSMatthew Dillon int rq_elements; /* active elements */ 296*6a03354eSMatthew Dillon struct dn_flowqueue_head *rq;/* array of rq_size entries */ 297*6a03354eSMatthew Dillon 298*6a03354eSMatthew Dillon uint32_t last_expired; /* do not expire too frequently */ 299*6a03354eSMatthew Dillon int backlogged; /* #active queues for this flowset */ 300*6a03354eSMatthew Dillon 301*6a03354eSMatthew Dillon /* RED parameters */ 302*6a03354eSMatthew Dillon int w_q; /* queue weight (scaled) */ 303*6a03354eSMatthew Dillon int max_th; /* maximum threshold for queue (scaled) */ 304*6a03354eSMatthew Dillon int min_th; /* minimum threshold for queue (scaled) */ 305*6a03354eSMatthew Dillon int max_p; /* maximum value for p_b (scaled) */ 306*6a03354eSMatthew Dillon u_int c_1; /* max_p/(max_th-min_th) (scaled) */ 307*6a03354eSMatthew Dillon u_int c_2; /* max_p*min_th/(max_th-min_th) (scaled) */ 308*6a03354eSMatthew Dillon u_int c_3; /* for GRED, (1-max_p)/max_th (scaled) */ 309*6a03354eSMatthew Dillon u_int c_4; /* for GRED, 1 - 2*max_p (scaled) */ 310*6a03354eSMatthew Dillon u_int *w_q_lookup; /* lookup table for computing (1-w_q)^t */ 311*6a03354eSMatthew Dillon u_int lookup_depth; /* depth of lookup table */ 312*6a03354eSMatthew Dillon int lookup_step; /* granularity inside the lookup table */ 313*6a03354eSMatthew Dillon int lookup_weight; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 314*6a03354eSMatthew Dillon int avg_pkt_size; /* medium packet size */ 315*6a03354eSMatthew Dillon int max_pkt_size; /* max packet size */ 316*6a03354eSMatthew Dillon }; 317*6a03354eSMatthew Dillon LIST_HEAD(dn_flowset_head, dn_flow_set); 318*6a03354eSMatthew Dillon 319*6a03354eSMatthew Dillon /* 320*6a03354eSMatthew Dillon * Pipe descriptor. Contains global parameters, delay-line queue, and the 321*6a03354eSMatthew Dillon * flow_set used for fixed-rate queues. 322*6a03354eSMatthew Dillon * 323*6a03354eSMatthew Dillon * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: 324*6a03354eSMatthew Dillon * + not_eligible_heap, for queues whose start time is higher than the 325*6a03354eSMatthew Dillon * virtual time. Sorted by start time. 326*6a03354eSMatthew Dillon * + scheduler_heap, for queues eligible for scheduling. Sorted by finish 327*6a03354eSMatthew Dillon * time. 328*6a03354eSMatthew Dillon * + idle_heap, all flows that are idle and can be removed. We do that on 329*6a03354eSMatthew Dillon * each tick so we do not slow down too much operations during forwarding. 330*6a03354eSMatthew Dillon */ 331*6a03354eSMatthew Dillon struct dn_pipe { /* a pipe */ 332*6a03354eSMatthew Dillon int pipe_nr; /* number */ 333*6a03354eSMatthew Dillon int bandwidth; /* really, bytes/tick. */ 334*6a03354eSMatthew Dillon int delay; /* really, ticks */ 335*6a03354eSMatthew Dillon 336*6a03354eSMatthew Dillon struct dn_pkt_queue p_queue;/* packets in delay line */ 337*6a03354eSMatthew Dillon LIST_ENTRY(dn_pipe) p_link; 338*6a03354eSMatthew Dillon 339*6a03354eSMatthew Dillon /* WF2Q+ */ 340*6a03354eSMatthew Dillon struct dn_heap scheduler_heap; /* top extract - key Finish time*/ 341*6a03354eSMatthew Dillon struct dn_heap not_eligible_heap; /* top extract- key Start time */ 342*6a03354eSMatthew Dillon struct dn_heap idle_heap; /* random extract - key Start=Finish time */ 343*6a03354eSMatthew Dillon 344*6a03354eSMatthew Dillon dn_key V; /* virtual time */ 345*6a03354eSMatthew Dillon int sum; /* sum of weights of all active sessions */ 346*6a03354eSMatthew Dillon int numbytes; /* bits I can transmit (more or less). */ 347*6a03354eSMatthew Dillon 348*6a03354eSMatthew Dillon dn_key sched_time; /* time pipe was scheduled in ready_heap */ 349*6a03354eSMatthew Dillon 350*6a03354eSMatthew Dillon struct dn_flow_set fs; /* used with fixed-rate flows */ 351*6a03354eSMatthew Dillon }; 352*6a03354eSMatthew Dillon LIST_HEAD(dn_pipe_head, dn_pipe); 353*6a03354eSMatthew Dillon 354*6a03354eSMatthew Dillon struct dn_sopt { 355*6a03354eSMatthew Dillon int dn_sopt_name; 356*6a03354eSMatthew Dillon void *dn_sopt_arg; 357*6a03354eSMatthew Dillon size_t dn_sopt_arglen; 358*6a03354eSMatthew Dillon }; 359*6a03354eSMatthew Dillon 360*6a03354eSMatthew Dillon typedef int ip_dn_ctl_t(struct dn_sopt *); 361*6a03354eSMatthew Dillon typedef int ip_dn_io_t(struct mbuf *); 362*6a03354eSMatthew Dillon 363*6a03354eSMatthew Dillon extern ip_dn_ctl_t *ip_dn_ctl_ptr; 364*6a03354eSMatthew Dillon extern ip_dn_io_t *ip_dn_io_ptr; 365*6a03354eSMatthew Dillon 366*6a03354eSMatthew Dillon void ip_dn_queue(struct mbuf *); 367*6a03354eSMatthew Dillon void ip_dn_packet_free(struct dn_pkt *); 368*6a03354eSMatthew Dillon void ip_dn_packet_redispatch(struct dn_pkt *); 369*6a03354eSMatthew Dillon int ip_dn_sockopt(struct sockopt *); 370*6a03354eSMatthew Dillon 371*6a03354eSMatthew Dillon #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL) 372*6a03354eSMatthew Dillon 373*6a03354eSMatthew Dillon #endif /* _KERNEL */ 374*6a03354eSMatthew Dillon 375*6a03354eSMatthew Dillon struct dn_ioc_flowid { 376*6a03354eSMatthew Dillon uint16_t type; /* ETHERTYPE_ */ 377*6a03354eSMatthew Dillon uint16_t pad; 378*6a03354eSMatthew Dillon union { 379*6a03354eSMatthew Dillon struct { 380*6a03354eSMatthew Dillon uint32_t dst_ip; 381*6a03354eSMatthew Dillon uint32_t src_ip; 382*6a03354eSMatthew Dillon uint16_t dst_port; 383*6a03354eSMatthew Dillon uint16_t src_port; 384*6a03354eSMatthew Dillon uint8_t proto; 385*6a03354eSMatthew Dillon uint8_t flags; 386*6a03354eSMatthew Dillon } ip; 387*6a03354eSMatthew Dillon uint8_t pad[64]; 388*6a03354eSMatthew Dillon } u; 389*6a03354eSMatthew Dillon }; 390*6a03354eSMatthew Dillon 391*6a03354eSMatthew Dillon struct dn_ioc_flowqueue { 392*6a03354eSMatthew Dillon u_int len; 393*6a03354eSMatthew Dillon u_int len_bytes; 394*6a03354eSMatthew Dillon 395*6a03354eSMatthew Dillon uint64_t tot_pkts; 396*6a03354eSMatthew Dillon uint64_t tot_bytes; 397*6a03354eSMatthew Dillon uint32_t drops; 398*6a03354eSMatthew Dillon 399*6a03354eSMatthew Dillon int hash_slot; /* debugging/diagnostic */ 400*6a03354eSMatthew Dillon dn_key S; /* virtual start time */ 401*6a03354eSMatthew Dillon dn_key F; /* virtual finish time */ 402*6a03354eSMatthew Dillon 403*6a03354eSMatthew Dillon struct dn_ioc_flowid id; 404*6a03354eSMatthew Dillon uint8_t reserved[16]; 405*6a03354eSMatthew Dillon }; 406*6a03354eSMatthew Dillon 407*6a03354eSMatthew Dillon struct dn_ioc_flowset { 408*6a03354eSMatthew Dillon u_short fs_type; /* DN_IS_{QUEUE,PIPE}, MUST be first */ 409*6a03354eSMatthew Dillon 410*6a03354eSMatthew Dillon u_short fs_nr; /* flow_set number */ 411*6a03354eSMatthew Dillon u_short flags_fs; /* see 'Flow set flags' */ 412*6a03354eSMatthew Dillon u_short parent_nr; /* parent pipe#, 0 if local to a pipe */ 413*6a03354eSMatthew Dillon 414*6a03354eSMatthew Dillon int weight; /* WFQ queue weight */ 415*6a03354eSMatthew Dillon int qsize; /* queue size in slots or bytes */ 416*6a03354eSMatthew Dillon int plr; /* pkt loss rate (2^31-1 means 100%) */ 417*6a03354eSMatthew Dillon 418*6a03354eSMatthew Dillon /* Hash table information */ 419*6a03354eSMatthew Dillon int rq_size; /* number of slots */ 420*6a03354eSMatthew Dillon int rq_elements; /* active elements */ 421*6a03354eSMatthew Dillon 422*6a03354eSMatthew Dillon /* RED parameters */ 423*6a03354eSMatthew Dillon int w_q; /* queue weight (scaled) */ 424*6a03354eSMatthew Dillon int max_th; /* maximum threshold for queue (scaled) */ 425*6a03354eSMatthew Dillon int min_th; /* minimum threshold for queue (scaled) */ 426*6a03354eSMatthew Dillon int max_p; /* maximum value for p_b (scaled) */ 427*6a03354eSMatthew Dillon int lookup_step; /* granularity inside the lookup table */ 428*6a03354eSMatthew Dillon int lookup_weight; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 429*6a03354eSMatthew Dillon 430*6a03354eSMatthew Dillon struct dn_ioc_flowid flow_mask; 431*6a03354eSMatthew Dillon uint8_t reserved[16]; 432*6a03354eSMatthew Dillon }; 433*6a03354eSMatthew Dillon 434*6a03354eSMatthew Dillon struct dn_ioc_pipe { 435*6a03354eSMatthew Dillon struct dn_ioc_flowset fs; /* MUST be first */ 436*6a03354eSMatthew Dillon 437*6a03354eSMatthew Dillon int pipe_nr; /* pipe number */ 438*6a03354eSMatthew Dillon int bandwidth; /* bit/second */ 439*6a03354eSMatthew Dillon int delay; /* milliseconds */ 440*6a03354eSMatthew Dillon 441*6a03354eSMatthew Dillon dn_key V; /* virtual time */ 442*6a03354eSMatthew Dillon 443*6a03354eSMatthew Dillon uint8_t reserved[16]; 444*6a03354eSMatthew Dillon }; 445*6a03354eSMatthew Dillon 446*6a03354eSMatthew Dillon /* 447*6a03354eSMatthew Dillon * Flow set flags 448*6a03354eSMatthew Dillon */ 449*6a03354eSMatthew Dillon #define DN_HAVE_FLOW_MASK 0x0001 450*6a03354eSMatthew Dillon #define DN_IS_RED 0x0002 451*6a03354eSMatthew Dillon #define DN_IS_GENTLE_RED 0x0004 452*6a03354eSMatthew Dillon #define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 453*6a03354eSMatthew Dillon #define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 454*6a03354eSMatthew Dillon #define DN_IS_PIPE 0x4000 455*6a03354eSMatthew Dillon #define DN_IS_QUEUE 0x8000 456*6a03354eSMatthew Dillon 457*6a03354eSMatthew Dillon /* 458*6a03354eSMatthew Dillon * Macros for RED 459*6a03354eSMatthew Dillon */ 460*6a03354eSMatthew Dillon #define SCALE_RED 16 461*6a03354eSMatthew Dillon #define SCALE(x) ((x) << SCALE_RED) 462*6a03354eSMatthew Dillon #define SCALE_VAL(x) ((x) >> SCALE_RED) 463*6a03354eSMatthew Dillon #define SCALE_MUL(x, y) (((x) * (y)) >> SCALE_RED) 464*6a03354eSMatthew Dillon 465*6a03354eSMatthew Dillon /* 466*6a03354eSMatthew Dillon * Maximum pipe number 467*6a03354eSMatthew Dillon */ 468*6a03354eSMatthew Dillon #define DN_PIPE_NR_MAX 65536 469*6a03354eSMatthew Dillon 470*6a03354eSMatthew Dillon #endif 471*6a03354eSMatthew Dillon #endif /* !_IP_DUMMYNET_H */ 472