diff options
Diffstat (limited to 'sys/netinet/ip_dummynet.h')
| -rw-r--r-- | sys/netinet/ip_dummynet.h | 175 |
1 files changed, 149 insertions, 26 deletions
diff --git a/sys/netinet/ip_dummynet.h b/sys/netinet/ip_dummynet.h index a3869607a724..9105e967b137 100644 --- a/sys/netinet/ip_dummynet.h +++ b/sys/netinet/ip_dummynet.h @@ -41,11 +41,31 @@ * is pretty simple and this makes the code more portable. */ -typedef u_int32_t dn_key ; /* sorting key */ -#define DN_KEY_LT(a,b) ((int)((a)-(b)) < 0) -#define DN_KEY_LEQ(a,b) ((int)((a)-(b)) <= 0) -#define DN_KEY_GT(a,b) ((int)((a)-(b)) > 0) -#define DN_KEY_GEQ(a,b) ((int)((a)-(b)) >= 0) +/* + * The key for the heap is used for two different values + 1. timer ticks- max 10K/second, so 32 bits are enough + 2. virtual times. These increase in steps of len/x, where len is the + packet length, and x is either the weight of the flow, or the + sum of all weights. + If we limit to max 1000 flows and a max weight of 100, then + x needs 17 bits. The packet size is 16 bits, so we can easily + overflow if we do not allow errors. + + */ +typedef u_int64_t dn_key ; /* sorting key */ +#define DN_KEY_LT(a,b) ((int64_t)((a)-(b)) < 0) +#define DN_KEY_LEQ(a,b) ((int64_t)((a)-(b)) <= 0) +#define DN_KEY_GT(a,b) ((int64_t)((a)-(b)) > 0) +#define DN_KEY_GEQ(a,b) ((int64_t)((a)-(b)) >= 0) +/* XXX check names of next two macros */ +#define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) +#define MY_M 16 /* number of left shift to obtain a larger precision */ +/* + * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the + * virtual time wraps every 15 days. + */ + +#define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) ) struct dn_heap_entry { dn_key key ; /* sorting key. Topmost element is smallest one */ @@ -55,6 +75,7 @@ struct dn_heap_entry { struct dn_heap { int size ; int elements ; + int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */ struct dn_heap_entry *p ; /* really an array of "size" entries */ } ; @@ -66,6 +87,7 @@ struct dn_heap { #define MT_DUMMYNET MT_CONTROL + /* * struct dn_pkt identifies a packet in the dummynet queue. The * first part is really an m_hdr for implementation purposes, and some @@ -78,7 +100,6 @@ struct dn_pkt { #define dn_next hdr.mh_nextpkt /* next element in queue */ #define DN_NEXT(x) (struct dn_pkt *)(x)->dn_next #define dn_m hdr.mh_next /* packet to be forwarded */ -/* #define dn_dst hdr.mh_len -* dst, for ip_output */ #define dn_dir hdr.mh_flags /* action when pkt extracted from a queue */ #define DN_TO_IP_OUT 1 #define DN_TO_IP_IN 2 @@ -91,51 +112,153 @@ struct dn_pkt { int flags ; /* flags, for ip_output (IPv6 ?) */ }; -struct dn_queue { - struct dn_pkt *head, *tail; -} ; +/* + * Overall structure (with WFQ): + +We have 3 data structures definining a pipe and associated queues: + + dn_pipe, which contains the main configuration parameters related + to delay and bandwidth + + dn_flow_set which contains WFQ configuration, flow + masks, plr and RED configuration + + dn_flow_queue which is the per-flow queue. + Multiple dn_flow_set can be linked to the same pipe, and multiple + dn_flow_queue can be linked to the same dn_flow_set. + + During configuration we set the dn_flow_set and dn_pipe parameters. + At runtime: packets are sent to the dn_flow_set (either WFQ ones, or + the one embedded in the dn_pipe for fixed-rate flows) which in turn + dispatches them to the appropriate dn_flow_queue (created dynamically + according to the masks). + The transmit clock for fixed rate flows (ready_event) selects the + dn_flow_queue to be used to transmit the next packet. For WF2Q, + wfq_ready_event() extract a pipe which in turn selects the right + flow using a number of heaps defined into the pipe. + + * + */ /* * We use per flow queues. Hashing is used to select the right slot, * then we scan the list to match the flow-id. - * The pipe is shared as it is only a delay line and thus one is enough. */ struct dn_flow_queue { struct dn_flow_queue *next ; struct ipfw_flow_id id ; - struct dn_pipe *p ; /* parent pipe */ - struct dn_queue r; - long numbytes ; + struct dn_pkt *head, *tail ; /* queue of packets */ u_int len ; u_int len_bytes ; + long numbytes ; /* credit for transmission (dynamic queues) */ u_int64_t tot_pkts ; /* statistics counters */ u_int64_t tot_bytes ; u_int32_t drops ; int hash_slot ; /* debugging/diagnostic */ + + /* RED parameters */ + int avg ; /* average queue length est. (scaled) */ + int count ; /* arrivals since last RED drop */ + int random ; /* random value (scaled) */ + u_int32_t q_time ; /* start of queue idle time */ + + /* WF2Q+ support */ + struct dn_flow_set *fs ; /* parent flow set */ + int blh_pos ; /* position in backlogged_heap */ + dn_key sched_time ; /* current time when queue enters ready_heap */ + + dn_key S,F ; /* start-time, finishing time */ +} ; + +struct dn_flow_set { + struct dn_flow_set *next; /* next flow set in all_flow_sets list */ + + u_short fs_nr ; /* flow_set number */ + u_short flags_fs; +#define DN_HAVE_FLOW_MASK 0x0001 +#define DN_IS_PIPE 0x4000 +#define DN_IS_QUEUE 0x8000 +#define DN_IS_RED 0x0002 +#define DN_IS_GENTLE_RED 0x0004 +#define DN_QSIZE_IS_BYTES 0x0008 /* queue measured in bytes */ + + struct dn_pipe *pipe ; /* pointer to parent pipe */ + u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */ + + int weight ; /* WFQ queue weight */ + int qsize ; /* queue size in slots or bytes */ + int plr ; /* pkt loss rate (2^31-1 means 100%) */ + + struct ipfw_flow_id flow_mask ; + /* hash table of queues onto this flow_set */ + int rq_size ; /* number of slots */ + int rq_elements ; /* active elements */ + struct dn_flow_queue **rq; /* array of rq_size entries */ + u_int32_t last_expired ; /* do not expire too frequently */ + /* XXX some RED parameters as well ? */ + int backlogged ; /* #active queues for this flowset */ + + /* RED parameters */ +#define SCALE_RED 16 +#define SCALE(x) ( (x) << SCALE_RED ) +#define SCALE_VAL(x) ( (x) >> SCALE_RED ) +#define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED ) + int w_q ; /* queue weight (scaled) */ + int max_th ; /* maximum threshold for queue (scaled) */ + int min_th ; /* minimum threshold for queue (scaled) */ + int max_p ; /* maximum value for p_b (scaled) */ + u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ + u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ + u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ + u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ + u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ + u_int lookup_depth ; /* depth of lookup table */ + int lookup_step ; /* granularity inside the lookup table */ + int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ + int avg_pkt_size ; /* medium packet size */ + int max_pkt_size ; /* max packet size */ } ; /* - * Pipe descriptor. Contains global parameters, delay-line queue, - * and the hash array of the per-flow queues. + * Pipe descriptor. Contains global parameters, delay-line queue. + * + * For WF2Q support it also has 3 heaps holding dn_flow_queue: + * not_eligible_heap, for queues whose start time is higher + * than the virtual time. Sorted by start time. + * scheduler_heap, for queues eligible for scheduling. Sorted by + * finish time. + * backlogged_heap, all flows in the two heaps above, sorted by + * start time. This is used to compute the virtual time. + * */ struct dn_pipe { /* a pipe */ struct dn_pipe *next ; - u_short pipe_nr ; /* number */ - u_short flags ; /* to speed up things */ -#define DN_HAVE_FLOW_MASK 8 + int pipe_nr ; /* number */ int bandwidth; /* really, bytes/tick. */ - int queue_size ; - int queue_size_bytes ; int delay ; /* really, ticks */ - int plr ; /* pkt loss rate (2^31-1 means 100%) */ - struct dn_queue p ; - struct ipfw_flow_id flow_mask ; - int rq_size ; - int rq_elements ; - struct dn_flow_queue **rq ; /* array of rq_size entries */ + struct dn_pkt *head, *tail ; /* packets in delay line */ + + /* WF2Q+ */ + struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ + struct dn_heap not_eligible_heap; /* top extract- key Start time */ + struct dn_heap backlogged_heap ; /* random extract - key Start time */ + + dn_key V ; /* virtual time */ + int sum; /* sum of weights of all active sessions */ + int numbytes; /* bit i can transmit (more or less). */ + + dn_key sched_time ; /* first time pipe is scheduled in ready_heap */ + + /* the tx clock can come from an interface. In this case, the + * name is below, and the pointer is filled when the rule is + * configured. We identify this by setting the if_name to a + * non-empty string. + */ + char if_name[16]; + struct ifnet *ifp ; + int ready ; /* set if ifp != NULL and we got a signal from it */ + + struct dn_flow_set fs ; /* used with fixed-rate flows */ }; #ifdef _KERNEL |