The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/netinet/ip_dummynet.h

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
    3  * Portions Copyright (c) 2000 Akamba Corp.
    4  * All rights reserved
    5  *
    6  * Redistribution and use in source and binary forms, with or without
    7  * modification, are permitted provided that the following conditions
    8  * are met:
    9  * 1. Redistributions of source code must retain the above copyright
   10  *    notice, this list of conditions and the following disclaimer.
   11  * 2. Redistributions in binary form must reproduce the above copyright
   12  *    notice, this list of conditions and the following disclaimer in the
   13  *    documentation and/or other materials provided with the distribution.
   14  *
   15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   25  * SUCH DAMAGE.
   26  *
   27  * $FreeBSD: releng/6.4/sys/netinet/ip_dummynet.h 178486 2008-04-25 10:29:26Z oleg $
   28  */
   29 
   30 #ifndef _IP_DUMMYNET_H
   31 #define _IP_DUMMYNET_H
   32 
   33 /*
   34  * Definition of dummynet data structures. In the structures, I decided
   35  * not to use the macros in <sys/queue.h> in the hope of making the code
   36  * easier to port to other architectures. The type of lists and queue we
   37  * use here is pretty simple anyways.
   38  */
   39 
   40 /*
   41  * We start with a heap, which is used in the scheduler to decide when
   42  * to transmit packets etc.
   43  *
   44  * The key for the heap is used for two different values:
   45  *
   46  * 1. timer ticks- max 10K/second, so 32 bits are enough;
   47  *
   48  * 2. virtual times. These increase in steps of len/x, where len is the
   49  *    packet length, and x is either the weight of the flow, or the
   50  *    sum of all weights.
   51  *    If we limit to max 1000 flows and a max weight of 100, then
   52  *    x needs 17 bits. The packet size is 16 bits, so we can easily
   53  *    overflow if we do not allow errors.
   54  * So we use a key "dn_key" which is 64 bits. Some macros are used to
   55  * compare key values and handle wraparounds.
   56  * MAX64 returns the largest of two key values.
   57  * MY_M is used as a shift count when doing fixed point arithmetic
   58  * (a better name would be useful...).
   59  */
   60 typedef u_int64_t dn_key ;      /* sorting key */
   61 #define DN_KEY_LT(a,b)     ((int64_t)((a)-(b)) < 0)
   62 #define DN_KEY_LEQ(a,b)    ((int64_t)((a)-(b)) <= 0)
   63 #define DN_KEY_GT(a,b)     ((int64_t)((a)-(b)) > 0)
   64 #define DN_KEY_GEQ(a,b)    ((int64_t)((a)-(b)) >= 0)
   65 #define MAX64(x,y)  (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
   66 #define MY_M    16 /* number of left shift to obtain a larger precision */
   67 
   68 /*
   69  * XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
   70  * virtual time wraps every 15 days.
   71  */
   72 
   73 /*
   74  * The OFFSET_OF macro is used to return the offset of a field within
   75  * a structure. It is used by the heap management routines.
   76  */
   77 #define OFFSET_OF(type, field) ((int)&( ((type *)0)->field) )
   78 
   79 /*
   80  * The maximum hash table size for queues.  This value must be a power
   81  * of 2.
   82  */
   83 #define DN_MAX_HASH_SIZE 65536
   84 
   85 /*
   86  * A heap entry is made of a key and a pointer to the actual
   87  * object stored in the heap.
   88  * The heap is an array of dn_heap_entry entries, dynamically allocated.
   89  * Current size is "size", with "elements" actually in use.
   90  * The heap normally supports only ordered insert and extract from the top.
   91  * If we want to extract an object from the middle of the heap, we
   92  * have to know where the object itself is located in the heap (or we
   93  * need to scan the whole array). To this purpose, an object has a
   94  * field (int) which contains the index of the object itself into the
   95  * heap. When the object is moved, the field must also be updated.
   96  * The offset of the index in the object is stored in the 'offset'
   97  * field in the heap descriptor. The assumption is that this offset
   98  * is non-zero if we want to support extract from the middle.
   99  */
  100 struct dn_heap_entry {
  101     dn_key key ;        /* sorting key. Topmost element is smallest one */
  102     void *object ;      /* object pointer */
  103 } ;
  104 
  105 struct dn_heap {
  106     int size ;
  107     int elements ;
  108     int offset ; /* XXX if > 0 this is the offset of direct ptr to obj */
  109     struct dn_heap_entry *p ;   /* really an array of "size" entries */
  110 } ;
  111 
  112 #ifdef _KERNEL
  113 /*
  114  * Packets processed by dummynet have an mbuf tag associated with
  115  * them that carries their dummynet state.  This is used within
  116  * the dummynet code as well as outside when checking for special
  117  * processing requirements.
  118  */
  119 struct dn_pkt_tag {
  120     struct ip_fw *rule;         /* matching rule */
  121     int dn_dir;                 /* action when packet comes out. */
  122 #define DN_TO_IP_OUT    1
  123 #define DN_TO_IP_IN     2
  124 #define DN_TO_BDG_FWD   3
  125 #define DN_TO_ETH_DEMUX 4
  126 #define DN_TO_ETH_OUT   5
  127 #define DN_TO_IP6_IN    6
  128 #define DN_TO_IP6_OUT   7
  129 #define DN_TO_IFB_FWD   8
  130 
  131     dn_key output_time;         /* when the pkt is due for delivery     */
  132     struct ifnet *ifp;          /* interface, for ip_output             */
  133     struct _ip6dn_args ip6opt;  /* XXX ipv6 options                     */
  134 };
  135 #endif /* _KERNEL */
  136 
  137 /*
  138  * Overall structure of dummynet (with WF2Q+):
  139 
  140 In dummynet, packets are selected with the firewall rules, and passed
  141 to two different objects: PIPE or QUEUE.
  142 
  143 A QUEUE is just a queue with configurable size and queue management
  144 policy. It is also associated with a mask (to discriminate among
  145 different flows), a weight (used to give different shares of the
  146 bandwidth to different flows) and a "pipe", which essentially
  147 supplies the transmit clock for all queues associated with that
  148 pipe.
  149 
  150 A PIPE emulates a fixed-bandwidth link, whose bandwidth is
  151 configurable.  The "clock" for a pipe can come from either an
  152 internal timer, or from the transmit interrupt of an interface.
  153 A pipe is also associated with one (or more, if masks are used)
  154 queue, where all packets for that pipe are stored.
  155 
  156 The bandwidth available on the pipe is shared by the queues
  157 associated with that pipe (only one in case the packet is sent
  158 to a PIPE) according to the WF2Q+ scheduling algorithm and the
  159 configured weights.
  160 
  161 In general, incoming packets are stored in the appropriate queue,
  162 which is then placed into one of a few heaps managed by a scheduler
  163 to decide when the packet should be extracted.
  164 The scheduler (a function called dummynet()) is run at every timer
  165 tick, and grabs queues from the head of the heaps when they are
  166 ready for processing.
  167 
  168 There are three data structures definining a pipe and associated queues:
  169 
  170  + dn_pipe, which contains the main configuration parameters related
  171    to delay and bandwidth;
  172  + dn_flow_set, which contains WF2Q+ configuration, flow
  173    masks, plr and RED configuration;
  174  + dn_flow_queue, which is the per-flow queue (containing the packets)
  175 
  176 Multiple dn_flow_set can be linked to the same pipe, and multiple
  177 dn_flow_queue can be linked to the same dn_flow_set.
  178 All data structures are linked in a linear list which is used for
  179 housekeeping purposes.
  180 
  181 During configuration, we create and initialize the dn_flow_set
  182 and dn_pipe structures (a dn_pipe also contains a dn_flow_set).
  183 
  184 At runtime: packets are sent to the appropriate dn_flow_set (either
  185 WFQ ones, or the one embedded in the dn_pipe for fixed-rate flows),
  186 which in turn dispatches them to the appropriate dn_flow_queue
  187 (created dynamically according to the masks).
  188 
  189 The transmit clock for fixed rate flows (ready_event()) selects the
  190 dn_flow_queue to be used to transmit the next packet. For WF2Q,
  191 wfq_ready_event() extract a pipe which in turn selects the right
  192 flow using a number of heaps defined into the pipe itself.
  193 
  194  *
  195  */
  196 
  197 /*
  198  * per flow queue. This contains the flow identifier, the queue
  199  * of packets, counters, and parameters used to support both RED and
  200  * WF2Q+.
  201  *
  202  * A dn_flow_queue is created and initialized whenever a packet for
  203  * a new flow arrives.
  204  */
  205 struct dn_flow_queue {
  206     struct dn_flow_queue *next ;
  207     struct ipfw_flow_id id ;
  208 
  209     struct mbuf *head, *tail ;  /* queue of packets */
  210     u_int len ;
  211     u_int len_bytes ;
  212     u_long numbytes ;           /* credit for transmission (dynamic queues) */
  213 
  214     u_int64_t tot_pkts ;        /* statistics counters  */
  215     u_int64_t tot_bytes ;
  216     u_int32_t drops ;
  217 
  218     int hash_slot ;             /* debugging/diagnostic */
  219 
  220     /* RED parameters */
  221     int avg ;                   /* average queue length est. (scaled) */
  222     int count ;                 /* arrivals since last RED drop */
  223     int random ;                /* random value (scaled) */
  224     u_int32_t q_time ;          /* start of queue idle time */
  225 
  226     /* WF2Q+ support */
  227     struct dn_flow_set *fs ;    /* parent flow set */
  228     int heap_pos ;              /* position (index) of struct in heap */
  229     dn_key sched_time ;         /* current time when queue enters ready_heap */
  230 
  231     dn_key S,F ;                /* start time, finish time */
  232     /*
  233      * Setting F < S means the timestamp is invalid. We only need
  234      * to test this when the queue is empty.
  235      */
  236 } ;
  237 
  238 /*
  239  * flow_set descriptor. Contains the "template" parameters for the
  240  * queue configuration, and pointers to the hash table of dn_flow_queue's.
  241  *
  242  * The hash table is an array of lists -- we identify the slot by
  243  * hashing the flow-id, then scan the list looking for a match.
  244  * The size of the hash table (buckets) is configurable on a per-queue
  245  * basis.
  246  *
  247  * A dn_flow_set is created whenever a new queue or pipe is created (in the
  248  * latter case, the structure is located inside the struct dn_pipe).
  249  */
  250 struct dn_flow_set {
  251     SLIST_ENTRY(dn_flow_set)    next;   /* linked list in a hash slot */
  252 
  253     u_short fs_nr ;             /* flow_set number       */
  254     u_short flags_fs;
  255 #define DN_HAVE_FLOW_MASK       0x0001
  256 #define DN_IS_RED               0x0002
  257 #define DN_IS_GENTLE_RED        0x0004
  258 #define DN_QSIZE_IS_BYTES       0x0008  /* queue size is measured in bytes */
  259 #define DN_NOERROR              0x0010  /* do not report ENOBUFS on drops  */
  260 #define DN_IS_PIPE              0x4000
  261 #define DN_IS_QUEUE             0x8000
  262 
  263     struct dn_pipe *pipe ;      /* pointer to parent pipe */
  264     u_short parent_nr ;         /* parent pipe#, 0 if local to a pipe */
  265 
  266     int weight ;                /* WFQ queue weight */
  267     int qsize ;                 /* queue size in slots or bytes */
  268     int plr ;                   /* pkt loss rate (2^31-1 means 100%) */
  269 
  270     struct ipfw_flow_id flow_mask ;
  271 
  272     /* hash table of queues onto this flow_set */
  273     int rq_size ;               /* number of slots */
  274     int rq_elements ;           /* active elements */
  275     struct dn_flow_queue **rq;  /* array of rq_size entries */
  276 
  277     u_int32_t last_expired ;    /* do not expire too frequently */
  278     int backlogged ;            /* #active queues for this flowset */
  279 
  280         /* RED parameters */
  281 #define SCALE_RED               16
  282 #define SCALE(x)                ( (x) << SCALE_RED )
  283 #define SCALE_VAL(x)            ( (x) >> SCALE_RED )
  284 #define SCALE_MUL(x,y)          ( ( (x) * (y) ) >> SCALE_RED )
  285     int w_q ;                   /* queue weight (scaled) */
  286     int max_th ;                /* maximum threshold for queue (scaled) */
  287     int min_th ;                /* minimum threshold for queue (scaled) */
  288     int max_p ;                 /* maximum value for p_b (scaled) */
  289     u_int c_1 ;                 /* max_p/(max_th-min_th) (scaled) */
  290     u_int c_2 ;                 /* max_p*min_th/(max_th-min_th) (scaled) */
  291     u_int c_3 ;                 /* for GRED, (1-max_p)/max_th (scaled) */
  292     u_int c_4 ;                 /* for GRED, 1 - 2*max_p (scaled) */
  293     u_int * w_q_lookup ;        /* lookup table for computing (1-w_q)^t */
  294     u_int lookup_depth ;        /* depth of lookup table */
  295     int lookup_step ;           /* granularity inside the lookup table */
  296     int lookup_weight ;         /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
  297     int avg_pkt_size ;          /* medium packet size */
  298     int max_pkt_size ;          /* max packet size */
  299 };
  300 SLIST_HEAD(dn_flow_set_head, dn_flow_set);
  301 
  302 /*
  303  * Pipe descriptor. Contains global parameters, delay-line queue,
  304  * and the flow_set used for fixed-rate queues.
  305  *
  306  * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
  307  *   not_eligible_heap, for queues whose start time is higher
  308  *      than the virtual time. Sorted by start time.
  309  *   scheduler_heap, for queues eligible for scheduling. Sorted by
  310  *      finish time.
  311  *   idle_heap, all flows that are idle and can be removed. We
  312  *      do that on each tick so we do not slow down too much
  313  *      operations during forwarding.
  314  *
  315  */
  316 struct dn_pipe {                /* a pipe */
  317     SLIST_ENTRY(dn_pipe)        next;   /* linked list in a hash slot */
  318 
  319     int pipe_nr ;               /* number       */
  320     int bandwidth;              /* really, bytes/tick.  */
  321     int delay ;                 /* really, ticks        */
  322 
  323     struct      mbuf *head, *tail ;     /* packets in delay line */
  324 
  325     /* WF2Q+ */
  326     struct dn_heap scheduler_heap ; /* top extract - key Finish time*/
  327     struct dn_heap not_eligible_heap; /* top extract- key Start time */
  328     struct dn_heap idle_heap ; /* random extract - key Start=Finish time */
  329 
  330     dn_key V ;                  /* virtual time */
  331     int sum;                    /* sum of weights of all active sessions */
  332     int numbytes;               /* bits I can transmit (more or less). */
  333 
  334     dn_key sched_time ;         /* time pipe was scheduled in ready_heap */
  335 
  336     /*
  337      * When the tx clock come from an interface (if_name[0] != '\0'), its name
  338      * is stored below, whereas the ifp is filled when the rule is configured.
  339      */
  340     char if_name[IFNAMSIZ];
  341     struct ifnet *ifp ;
  342     int ready ; /* set if ifp != NULL and we got a signal from it */
  343 
  344     struct dn_flow_set fs ; /* used with fixed-rate flows */
  345 };
  346 SLIST_HEAD(dn_pipe_head, dn_pipe);
  347 
  348 #ifdef _KERNEL
  349 typedef int ip_dn_ctl_t(struct sockopt *); /* raw_ip.c */
  350 typedef void ip_dn_ruledel_t(void *); /* ip_fw.c */
  351 typedef int ip_dn_io_t(struct mbuf **m, int dir, struct ip_fw_args *fwa);
  352 extern  ip_dn_ctl_t *ip_dn_ctl_ptr;
  353 extern  ip_dn_ruledel_t *ip_dn_ruledel_ptr;
  354 extern  ip_dn_io_t *ip_dn_io_ptr;
  355 #define DUMMYNET_LOADED (ip_dn_io_ptr != NULL)
  356 
  357 /*
  358  * Return the IPFW rule associated with the dummynet tag; if any.
  359  * Make sure that the dummynet tag is not reused by lower layers.
  360  */
  361 static __inline struct ip_fw *
  362 ip_dn_claim_rule(struct mbuf *m)
  363 {
  364         struct m_tag *mtag = m_tag_find(m, PACKET_TAG_DUMMYNET, NULL);
  365         if (mtag != NULL) {
  366                 mtag->m_tag_id = PACKET_TAG_NONE;
  367                 return (((struct dn_pkt_tag *)(mtag+1))->rule);
  368         } else
  369                 return (NULL);
  370 }
  371 #endif
  372 #endif /* _IP_DUMMYNET_H */

Cache object: 2163559eab9f98596fc846ae33c3868f


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.