1/* 2 * Copyright (c) 2000-2013 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28/* 29 * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa 30 * Portions Copyright (c) 2000 Akamba Corp. 31 * All rights reserved 32 * 33 * Redistribution and use in source and binary forms, with or without 34 * modification, are permitted provided that the following conditions 35 * are met: 36 * 1. Redistributions of source code must retain the above copyright 37 * notice, this list of conditions and the following disclaimer. 38 * 2. Redistributions in binary form must reproduce the above copyright 39 * notice, this list of conditions and the following disclaimer in the 40 * documentation and/or other materials provided with the distribution. 41 * 42 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 43 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 44 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 45 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 46 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 47 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 48 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 49 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 50 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 51 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 52 * SUCH DAMAGE. 53 * 54 * $FreeBSD: src/sys/netinet/ip_dummynet.h,v 1.32 2004/08/17 22:05:54 andre Exp $ 55 */ 56 57#ifndef _IP_DUMMYNET_H 58#define _IP_DUMMYNET_H 59 60#include <sys/appleapiopts.h> 61 62#ifdef PRIVATE 63 64#include <netinet/ip_flowid.h> 65 66/* Apply ipv6 mask on ipv6 addr */ 67#define APPLY_MASK(addr,mask) \ 68 (addr)->__u6_addr.__u6_addr32[0] &= (mask)->__u6_addr.__u6_addr32[0]; \ 69 (addr)->__u6_addr.__u6_addr32[1] &= (mask)->__u6_addr.__u6_addr32[1]; \ 70 (addr)->__u6_addr.__u6_addr32[2] &= (mask)->__u6_addr.__u6_addr32[2]; \ 71 (addr)->__u6_addr.__u6_addr32[3] &= (mask)->__u6_addr.__u6_addr32[3]; 72 73/* 74 * Definition of dummynet data structures. In the structures, I decided 75 * not to use the macros in <sys/queue.h> in the hope of making the code 76 * easier to port to other architectures. The type of lists and queue we 77 * use here is pretty simple anyways. 78 */ 79 80/* 81 * We start with a heap, which is used in the scheduler to decide when 82 * to transmit packets etc. 83 * 84 * The key for the heap is used for two different values: 85 * 86 * 1. timer ticks- max 10K/second, so 32 bits are enough; 87 * 88 * 2. virtual times. These increase in steps of len/x, where len is the 89 * packet length, and x is either the weight of the flow, or the 90 * sum of all weights. 91 * If we limit to max 1000 flows and a max weight of 100, then 92 * x needs 17 bits. The packet size is 16 bits, so we can easily 93 * overflow if we do not allow errors. 94 * So we use a key "dn_key" which is 64 bits. Some macros are used to 95 * compare key values and handle wraparounds. 96 * MAX64 returns the largest of two key values. 97 * MY_M is used as a shift count when doing fixed point arithmetic 98 * (a better name would be useful...). 99 */ 100typedef u_int64_t dn_key ; /* sorting key */ 101#define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) 102#define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) 103#define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0) 104#define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0) 105#define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) 106#define MY_M 16 /* number of left shift to obtain a larger precision */ 107 108/* 109 * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the 110 * virtual time wraps every 15 days. 111 */ 112 113/* 114 * The OFFSET_OF macro is used to return the offset of a field within 115 * a structure. It is used by the heap management routines. 116 */ 117#define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) ) 118 119/* 120 * The maximum hash table size for queues. This value must be a power 121 * of 2. 122 */ 123#define DN_MAX_HASH_SIZE 65536 124 125/* 126 * A heap entry is made of a key and a pointer to the actual 127 * object stored in the heap. 128 * The heap is an array of dn_heap_entry entries, dynamically allocated. 129 * Current size is "size", with "elements" actually in use. 130 * The heap normally supports only ordered insert and extract from the top. 131 * If we want to extract an object from the middle of the heap, we 132 * have to know where the object itself is located in the heap (or we 133 * need to scan the whole array). To this purpose, an object has a 134 * field (int) which contains the index of the object itself into the 135 * heap. When the object is moved, the field must also be updated. 136 * The offset of the index in the object is stored in the 'offset' 137 * field in the heap descriptor. The assumption is that this offset 138 * is non-zero if we want to support extract from the middle. 139 */ 140struct dn_heap_entry { 141 dn_key key ; /* sorting key. Topmost element is smallest one */ 142 void *object ; /* object pointer */ 143} ; 144 145struct dn_heap { 146 int size ; 147 int elements ; 148 int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ 149 struct dn_heap_entry *p ; /* really an array of "size" entries */ 150} ; 151 152/* 153 * Packets processed by dummynet have an mbuf tag associated with 154 * them that carries their dummynet state. This is used within 155 * the dummynet code as well as outside when checking for special 156 * processing requirements. 157 */ 158#ifdef KERNEL 159#include <netinet/ip_var.h> /* for ip_out_args */ 160#include <netinet/ip6.h> /* for ip6_out_args */ 161#include <netinet6/ip6_var.h> /* for ip6_out_args */ 162 163struct dn_pkt_tag { 164 struct ip_fw *dn_ipfw_rule; /* matching IPFW rule */ 165 void *dn_pf_rule; /* matching PF rule */ 166 int dn_dir; /* action when packet comes out. */ 167#define DN_TO_IP_OUT 1 168#define DN_TO_IP_IN 2 169#define DN_TO_BDG_FWD 3 170#define DN_TO_IP6_IN 4 171#define DN_TO_IP6_OUT 5 172 dn_key dn_output_time; /* when the pkt is due for delivery */ 173 struct ifnet *dn_ifp; /* interface, for ip[6]_output */ 174 union { 175 struct sockaddr_in _dn_dst; 176 struct sockaddr_in6 _dn_dst6 ; 177 } dn_dst_; 178#define dn_dst dn_dst_._dn_dst 179#define dn_dst6 dn_dst_._dn_dst6 180 union { 181 struct route _dn_ro; /* route, for ip_output. MUST COPY */ 182 struct route_in6 _dn_ro6; /* route, for ip6_output. MUST COPY */ 183 } dn_ro_; 184#define dn_ro dn_ro_._dn_ro 185#define dn_ro6 dn_ro_._dn_ro6 186 struct route_in6 dn_ro6_pmtu; /* for ip6_output */ 187 struct ifnet *dn_origifp; /* for ip6_output */ 188 u_int32_t dn_mtu; /* for ip6_output */ 189 int dn_alwaysfrag; /* for ip6_output */ 190 u_int32_t dn_unfragpartlen; /* for ip6_output */ 191 struct ip6_exthdrs dn_exthdrs; /* for ip6_output */ 192 int dn_flags ; /* flags, for ip[6]_output */ 193 int dn_client; 194#define DN_CLIENT_IPFW 1 195#define DN_CLIENT_PF 2 196 union { 197 struct ip_out_args _dn_ipoa; /* output args, for ip_output. MUST COPY */ 198 struct ip6_out_args _dn_ip6oa; /* output args, for ip_output. MUST COPY */ 199 } dn_ipoa_; 200#define dn_ipoa dn_ipoa_._dn_ipoa 201#define dn_ip6oa dn_ipoa_._dn_ip6oa 202}; 203#else 204struct dn_pkt; 205#endif /* KERNEL */ 206 207/* 208 * Overall structure of dummynet (with WF2Q+): 209 210In dummynet, packets are selected with the firewall rules, and passed 211to two different objects: PIPE or QUEUE. 212 213A QUEUE is just a queue with configurable size and queue management 214policy. It is also associated with a mask (to discriminate among 215different flows), a weight (used to give different shares of the 216bandwidth to different flows) and a "pipe", which essentially 217supplies the transmit clock for all queues associated with that 218pipe. 219 220A PIPE emulates a fixed-bandwidth link, whose bandwidth is 221configurable. The "clock" for a pipe can come from either an 222internal timer, or from the transmit interrupt of an interface. 223A pipe is also associated with one (or more, if masks are used) 224queue, where all packets for that pipe are stored. 225 226The bandwidth available on the pipe is shared by the queues 227associated with that pipe (only one in case the packet is sent 228to a PIPE) according to the WF2Q+ scheduling algorithm and the 229configured weights. 230 231In general, incoming packets are stored in the appropriate queue, 232which is then placed into one of a few heaps managed by a scheduler 233to decide when the packet should be extracted. 234The scheduler (a function called dummynet()) is run at every timer 235tick, and grabs queues from the head of the heaps when they are 236ready for processing. 237 238There are three data structures definining a pipe and associated queues: 239 240 + dn_pipe, which contains the main configuration parameters related 241 to delay and bandwidth; 242 + dn_flow_set, which contains WF2Q+ configuration, flow 243 masks, plr and RED configuration; 244 + dn_flow_queue, which is the per-flow queue (containing the packets) 245 246Multiple dn_flow_set can be linked to the same pipe, and multiple 247dn_flow_queue can be linked to the same dn_flow_set. 248All data structures are linked in a linear list which is used for 249housekeeping purposes. 250 251During configuration, we create and initialize the dn_flow_set 252and dn_pipe structures (a dn_pipe also contains a dn_flow_set). 253 254At runtime: packets are sent to the appropriate dn_flow_set (either 255WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows), 256which in turn dispatches them to the appropriate dn_flow_queue 257(created dynamically according to the masks). 258 259The transmit clock for fixed rate flows (ready_event()) selects the 260dn_flow_queue to be used to transmit the next packet. For WF2Q, 261wfq_ready_event() extract a pipe which in turn selects the right 262flow using a number of heaps defined into the pipe itself. 263 264 * 265 */ 266 267/* 268 * per flow queue. This contains the flow identifier, the queue 269 * of packets, counters, and parameters used to support both RED and 270 * WF2Q+. 271 * 272 * A dn_flow_queue is created and initialized whenever a packet for 273 * a new flow arrives. 274 */ 275struct dn_flow_queue { 276 struct dn_flow_queue *next ; 277 struct ip_flow_id id ; 278 279 struct mbuf *head, *tail ; /* queue of packets */ 280 u_int len ; 281 u_int len_bytes ; 282 u_int32_t numbytes ; /* credit for transmission (dynamic queues) */ 283 284 u_int64_t tot_pkts ; /* statistics counters */ 285 u_int64_t tot_bytes ; 286 u_int32_t drops ; 287 288 int hash_slot ; /* debugging/diagnostic */ 289 290 /* RED parameters */ 291 int avg ; /* average queue length est. (scaled) */ 292 int count ; /* arrivals since last RED drop */ 293 int random ; /* random value (scaled) */ 294 u_int32_t q_time ; /* start of queue idle time */ 295 296 /* WF2Q+ support */ 297 struct dn_flow_set *fs ; /* parent flow set */ 298 int heap_pos ; /* position (index) of struct in heap */ 299 dn_key sched_time ; /* current time when queue enters ready_heap */ 300 301 dn_key S,F ; /* start time, finish time */ 302 /* 303 * Setting F < S means the timestamp is invalid. We only need 304 * to test this when the queue is empty. 305 */ 306} ; 307 308/* 309 * flow_set descriptor. Contains the "template" parameters for the 310 * queue configuration, and pointers to the hash table of dn_flow_queue's. 311 * 312 * The hash table is an array of lists -- we identify the slot by 313 * hashing the flow-id, then scan the list looking for a match. 314 * The size of the hash table (buckets) is configurable on a per-queue 315 * basis. 316 * 317 * A dn_flow_set is created whenever a new queue or pipe is created (in the 318 * latter case, the structure is located inside the struct dn_pipe). 319 */ 320struct dn_flow_set { 321 SLIST_ENTRY(dn_flow_set) next; /* linked list in a hash slot */ 322 323 u_short fs_nr ; /* flow_set number */ 324 u_short flags_fs; 325#define DN_HAVE_FLOW_MASK 0x0001 326#define DN_IS_RED 0x0002 327#define DN_IS_GENTLE_RED 0x0004 328#define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 329#define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 330#define DN_IS_PIPE 0x4000 331#define DN_IS_QUEUE 0x8000 332 333 struct dn_pipe *pipe ; /* pointer to parent pipe */ 334 u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ 335 336 int weight ; /* WFQ queue weight */ 337 int qsize ; /* queue size in slots or bytes */ 338 int plr ; /* pkt loss rate (2^31-1 means 100%) */ 339 340 struct ip_flow_id flow_mask ; 341 342 /* hash table of queues onto this flow_set */ 343 int rq_size ; /* number of slots */ 344 int rq_elements ; /* active elements */ 345 struct dn_flow_queue **rq; /* array of rq_size entries */ 346 347 u_int32_t last_expired ; /* do not expire too frequently */ 348 int backlogged ; /* #active queues for this flowset */ 349 350 /* RED parameters */ 351#define SCALE_RED 16 352#define SCALE(x) ( (x) << SCALE_RED ) 353#define SCALE_VAL(x) ( (x) >> SCALE_RED ) 354#define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) 355 int w_q ; /* queue weight (scaled) */ 356 int max_th ; /* maximum threshold for queue (scaled) */ 357 int min_th ; /* minimum threshold for queue (scaled) */ 358 int max_p ; /* maximum value for p_b (scaled) */ 359 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 360 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 361 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 362 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 363 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 364 u_int lookup_depth ; /* depth of lookup table */ 365 int lookup_step ; /* granularity inside the lookup table */ 366 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 367 int avg_pkt_size ; /* medium packet size */ 368 int max_pkt_size ; /* max packet size */ 369} ; 370 371SLIST_HEAD(dn_flow_set_head, dn_flow_set); 372 373/* 374 * Pipe descriptor. Contains global parameters, delay-line queue, 375 * and the flow_set used for fixed-rate queues. 376 * 377 * For WF2Q+ support it also has 3 heaps holding dn_flow_queue: 378 * not_eligible_heap, for queues whose start time is higher 379 * than the virtual time. Sorted by start time. 380 * scheduler_heap, for queues eligible for scheduling. Sorted by 381 * finish time. 382 * idle_heap, all flows that are idle and can be removed. We 383 * do that on each tick so we do not slow down too much 384 * operations during forwarding. 385 * 386 */ 387struct dn_pipe { /* a pipe */ 388 SLIST_ENTRY(dn_pipe) next; /* linked list in a hash slot */ 389 390 int pipe_nr ; /* number */ 391 int bandwidth; /* really, bytes/tick. */ 392 int delay ; /* really, ticks */ 393 394 struct mbuf *head, *tail ; /* packets in delay line */ 395 396 /* WF2Q+ */ 397 struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ 398 struct dn_heap not_eligible_heap; /* top extract- key Start time */ 399 struct dn_heap idle_heap ; /* random extract - key Start=Finish time */ 400 401 dn_key V ; /* virtual time */ 402 int sum; /* sum of weights of all active sessions */ 403 int numbytes; /* bits I can transmit (more or less). */ 404 405 dn_key sched_time ; /* time pipe was scheduled in ready_heap */ 406 407 /* 408 * When the tx clock come from an interface (if_name[0] != '\0'), its name 409 * is stored below, whereas the ifp is filled when the rule is configured. 410 */ 411 char if_name[IFNAMSIZ]; 412 struct ifnet *ifp ; 413 int ready ; /* set if ifp != NULL and we got a signal from it */ 414 415 struct dn_flow_set fs ; /* used with fixed-rate flows */ 416}; 417 418SLIST_HEAD(dn_pipe_head, dn_pipe); 419 420#ifdef BSD_KERNEL_PRIVATE 421 422void ip_dn_init(void); /* called from raw_ip.c:load_ipfw() */ 423 424typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */ 425typedef int ip_dn_io_t(struct mbuf *m, int pipe_nr, int dir, 426 struct ip_fw_args *fwa, int ); 427extern ip_dn_ctl_t *ip_dn_ctl_ptr; 428extern ip_dn_io_t *ip_dn_io_ptr; 429void dn_ipfw_rule_delete(void *); 430#define DUMMYNET_LOADED (ip_dn_io_ptr != NULL) 431 432#pragma pack(4) 433 434struct dn_heap_32 { 435 int size ; 436 int elements ; 437 int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ 438 user32_addr_t p ; /* really an array of "size" entries */ 439} ; 440 441struct dn_flow_queue_32 { 442 user32_addr_t next ; 443 struct ip_flow_id id ; 444 445 user32_addr_t head, tail ; /* queue of packets */ 446 u_int len ; 447 u_int len_bytes ; 448 u_int32_t numbytes ; /* credit for transmission (dynamic queues) */ 449 450 u_int64_t tot_pkts ; /* statistics counters */ 451 u_int64_t tot_bytes ; 452 u_int32_t drops ; 453 454 int hash_slot ; /* debugging/diagnostic */ 455 456 /* RED parameters */ 457 int avg ; /* average queue length est. (scaled) */ 458 int count ; /* arrivals since last RED drop */ 459 int random ; /* random value (scaled) */ 460 u_int32_t q_time ; /* start of queue idle time */ 461 462 /* WF2Q+ support */ 463 user32_addr_t fs ; /* parent flow set */ 464 int heap_pos ; /* position (index) of struct in heap */ 465 dn_key sched_time ; /* current time when queue enters ready_heap */ 466 467 dn_key S,F ; /* start time, finish time */ 468 /* 469 * Setting F < S means the timestamp is invalid. We only need 470 * to test this when the queue is empty. 471 */ 472} ; 473 474struct dn_flow_set_32 { 475 user32_addr_t next; /* next flow set in all_flow_sets list */ 476 477 u_short fs_nr ; /* flow_set number */ 478 u_short flags_fs; 479#define DN_HAVE_FLOW_MASK 0x0001 480#define DN_IS_RED 0x0002 481#define DN_IS_GENTLE_RED 0x0004 482#define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 483#define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 484#define DN_IS_PIPE 0x4000 485#define DN_IS_QUEUE 0x8000 486 487 user32_addr_t pipe ; /* pointer to parent pipe */ 488 u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ 489 490 int weight ; /* WFQ queue weight */ 491 int qsize ; /* queue size in slots or bytes */ 492 int plr ; /* pkt loss rate (2^31-1 means 100%) */ 493 494 struct ip_flow_id flow_mask ; 495 496 /* hash table of queues onto this flow_set */ 497 int rq_size ; /* number of slots */ 498 int rq_elements ; /* active elements */ 499 user32_addr_t rq; /* array of rq_size entries */ 500 501 u_int32_t last_expired ; /* do not expire too frequently */ 502 int backlogged ; /* #active queues for this flowset */ 503 504 /* RED parameters */ 505#define SCALE_RED 16 506#define SCALE(x) ( (x) << SCALE_RED ) 507#define SCALE_VAL(x) ( (x) >> SCALE_RED ) 508#define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) 509 int w_q ; /* queue weight (scaled) */ 510 int max_th ; /* maximum threshold for queue (scaled) */ 511 int min_th ; /* minimum threshold for queue (scaled) */ 512 int max_p ; /* maximum value for p_b (scaled) */ 513 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 514 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 515 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 516 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 517 user32_addr_t w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 518 u_int lookup_depth ; /* depth of lookup table */ 519 int lookup_step ; /* granularity inside the lookup table */ 520 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 521 int avg_pkt_size ; /* medium packet size */ 522 int max_pkt_size ; /* max packet size */ 523} ; 524 525struct dn_pipe_32 { /* a pipe */ 526 user32_addr_t next ; 527 528 int pipe_nr ; /* number */ 529 int bandwidth; /* really, bytes/tick. */ 530 int delay ; /* really, ticks */ 531 532 user32_addr_t head, tail ; /* packets in delay line */ 533 534 /* WF2Q+ */ 535 struct dn_heap_32 scheduler_heap ; /* top extract - key Finish time*/ 536 struct dn_heap_32 not_eligible_heap; /* top extract- key Start time */ 537 struct dn_heap_32 idle_heap ; /* random extract - key Start=Finish time */ 538 539 dn_key V ; /* virtual time */ 540 int sum; /* sum of weights of all active sessions */ 541 int numbytes; /* bits I can transmit (more or less). */ 542 543 dn_key sched_time ; /* time pipe was scheduled in ready_heap */ 544 545 /* 546 * When the tx clock come from an interface (if_name[0] != '\0'), its name 547 * is stored below, whereas the ifp is filled when the rule is configured. 548 */ 549 char if_name[IFNAMSIZ]; 550 user32_addr_t ifp ; 551 int ready ; /* set if ifp != NULL and we got a signal from it */ 552 553 struct dn_flow_set_32 fs ; /* used with fixed-rate flows */ 554}; 555#pragma pack() 556 557 558struct dn_heap_64 { 559 int size ; 560 int elements ; 561 int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ 562 user64_addr_t p ; /* really an array of "size" entries */ 563} ; 564 565 566struct dn_flow_queue_64 { 567 user64_addr_t next ; 568 struct ip_flow_id id ; 569 570 user64_addr_t head, tail ; /* queue of packets */ 571 u_int len ; 572 u_int len_bytes ; 573 u_int32_t numbytes ; /* credit for transmission (dynamic queues) */ 574 575 u_int64_t tot_pkts ; /* statistics counters */ 576 u_int64_t tot_bytes ; 577 u_int32_t drops ; 578 579 int hash_slot ; /* debugging/diagnostic */ 580 581 /* RED parameters */ 582 int avg ; /* average queue length est. (scaled) */ 583 int count ; /* arrivals since last RED drop */ 584 int random ; /* random value (scaled) */ 585 u_int32_t q_time ; /* start of queue idle time */ 586 587 /* WF2Q+ support */ 588 user64_addr_t fs ; /* parent flow set */ 589 int heap_pos ; /* position (index) of struct in heap */ 590 dn_key sched_time ; /* current time when queue enters ready_heap */ 591 592 dn_key S,F ; /* start time, finish time */ 593 /* 594 * Setting F < S means the timestamp is invalid. We only need 595 * to test this when the queue is empty. 596 */ 597} ; 598 599struct dn_flow_set_64 { 600 user64_addr_t next; /* next flow set in all_flow_sets list */ 601 602 u_short fs_nr ; /* flow_set number */ 603 u_short flags_fs; 604#define DN_HAVE_FLOW_MASK 0x0001 605#define DN_IS_RED 0x0002 606#define DN_IS_GENTLE_RED 0x0004 607#define DN_QSIZE_IS_BYTES 0x0008 /* queue size is measured in bytes */ 608#define DN_NOERROR 0x0010 /* do not report ENOBUFS on drops */ 609#define DN_IS_PIPE 0x4000 610#define DN_IS_QUEUE 0x8000 611 612 user64_addr_t pipe ; /* pointer to parent pipe */ 613 u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ 614 615 int weight ; /* WFQ queue weight */ 616 int qsize ; /* queue size in slots or bytes */ 617 int plr ; /* pkt loss rate (2^31-1 means 100%) */ 618 619 struct ip_flow_id flow_mask ; 620 621 /* hash table of queues onto this flow_set */ 622 int rq_size ; /* number of slots */ 623 int rq_elements ; /* active elements */ 624 user64_addr_t rq; /* array of rq_size entries */ 625 626 u_int32_t last_expired ; /* do not expire too frequently */ 627 int backlogged ; /* #active queues for this flowset */ 628 629 /* RED parameters */ 630#define SCALE_RED 16 631#define SCALE(x) ( (x) << SCALE_RED ) 632#define SCALE_VAL(x) ( (x) >> SCALE_RED ) 633#define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) 634 int w_q ; /* queue weight (scaled) */ 635 int max_th ; /* maximum threshold for queue (scaled) */ 636 int min_th ; /* minimum threshold for queue (scaled) */ 637 int max_p ; /* maximum value for p_b (scaled) */ 638 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 639 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 640 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 641 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 642 user64_addr_t w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 643 u_int lookup_depth ; /* depth of lookup table */ 644 int lookup_step ; /* granularity inside the lookup table */ 645 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 646 int avg_pkt_size ; /* medium packet size */ 647 int max_pkt_size ; /* max packet size */ 648} ; 649 650struct dn_pipe_64 { /* a pipe */ 651 user64_addr_t next ; 652 653 int pipe_nr ; /* number */ 654 int bandwidth; /* really, bytes/tick. */ 655 int delay ; /* really, ticks */ 656 657 user64_addr_t head, tail ; /* packets in delay line */ 658 659 /* WF2Q+ */ 660 struct dn_heap_64 scheduler_heap ; /* top extract - key Finish time*/ 661 struct dn_heap_64 not_eligible_heap; /* top extract- key Start time */ 662 struct dn_heap_64 idle_heap ; /* random extract - key Start=Finish time */ 663 664 dn_key V ; /* virtual time */ 665 int sum; /* sum of weights of all active sessions */ 666 int numbytes; /* bits I can transmit (more or less). */ 667 668 dn_key sched_time ; /* time pipe was scheduled in ready_heap */ 669 670 /* 671 * When the tx clock come from an interface (if_name[0] != '\0'), its name 672 * is stored below, whereas the ifp is filled when the rule is configured. 673 */ 674 char if_name[IFNAMSIZ]; 675 user64_addr_t ifp ; 676 int ready ; /* set if ifp != NULL and we got a signal from it */ 677 678 struct dn_flow_set_64 fs ; /* used with fixed-rate flows */ 679}; 680 681 682 683/* 684 * Return the IPFW rule associated with the dummynet tag; if any. 685 * Make sure that the dummynet tag is not reused by lower layers. 686 */ 687static __inline struct ip_fw * 688ip_dn_claim_rule(struct mbuf *m) 689{ 690 struct m_tag *mtag = m_tag_locate(m, KERNEL_MODULE_TAG_ID, 691 KERNEL_TAG_TYPE_DUMMYNET, NULL); 692 if (mtag != NULL) { 693 mtag->m_tag_type = KERNEL_TAG_TYPE_NONE; 694 return (((struct dn_pkt_tag *)(mtag+1))->dn_ipfw_rule); 695 } else 696 return (NULL); 697} 698#endif /* BSD_KERNEL_PRIVATE */ 699#endif /* PRIVATE */ 700#endif /* _IP_DUMMYNET_H */ 701