sys/net/altq/altq_hfsc.h

   1 /*      $KAME: altq_hfsc.h,v 1.12 2003/12/05 05:40:46 kjc Exp $ */
   2 /*      $DragonFly: src/sys/net/altq/altq_hfsc.h,v 1.1 2005/02/11 22:25:57 joerg Exp $ */
   3
   4 /*
   5  * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved.
   6  *
   7  * Permission to use, copy, modify, and distribute this software and
   8  * its documentation is hereby granted (including for commercial or
   9  * for-profit use), provided that both the copyright notice and this
  10  * permission notice appear in all copies of the software, derivative
  11  * works, or modified versions, and any portions thereof.
  12  *
  13  * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF
  14  * WHICH MAY HAVE SERIOUS CONSEQUENCES.  CARNEGIE MELLON PROVIDES THIS
  15  * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED
  16  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18  * DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  20  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
  21  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  22  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  23  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
  25  * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
  26  * DAMAGE.
  27  *
  28  * Carnegie Mellon encourages (but does not require) users of this
  29  * software to return any improvements or extensions that they make,
  30  * and to grant Carnegie Mellon the rights to redistribute these
  31  * changes without encumbrance.
  32  */
  33 #ifndef _ALTQ_ALTQ_HFSC_H_
  34 #define _ALTQ_ALTQ_HFSC_H_
  35
  36 #include <net/altq/altq.h>
  37 #include <net/altq/altq_classq.h>
  38 #include <net/altq/altq_red.h>
  39 #include <net/altq/altq_rio.h>
  40
  41 struct service_curve {
  42         u_int   m1;     /* slope of the first segment in bits/sec */
  43         u_int   d;      /* the x-projection of the first segment in msec */
  44         u_int   m2;     /* slope of the second segment in bits/sec */
  45 };
  46
  47 /* special class handles */
  48 #define HFSC_NULLCLASS_HANDLE   0
  49 #define HFSC_MAX_CLASSES        64
  50
  51 /* hfsc class flags */
  52 #define HFCF_RED                0x0001  /* use RED */
  53 #define HFCF_ECN                0x0002  /* use RED/ECN */
  54 #define HFCF_RIO                0x0004  /* use RIO */
  55 #define HFCF_CLEARDSCP          0x0010  /* clear diffserv codepoint */
  56 #define HFCF_DEFAULTCLASS       0x1000  /* default class */
  57
  58 /* service curve types */
  59 #define HFSC_REALTIMESC         1
  60 #define HFSC_LINKSHARINGSC      2
  61 #define HFSC_UPPERLIMITSC       4
  62 #define HFSC_DEFAULTSC          (HFSC_REALTIMESC|HFSC_LINKSHARINGSC)
  63
  64 struct hfsc_classstats {
  65         u_int                   class_id;
  66         uint32_t                class_handle;
  67         struct service_curve    rsc;
  68         struct service_curve    fsc;
  69         struct service_curve    usc;    /* upper limit service curve */
  70
  71         uint64_t                total;  /* total work in bytes */
  72         uint64_t                cumul;  /* cumulative work in bytes
  73                                            done by real-time criteria */
  74         uint64_t                d;              /* deadline */
  75         uint64_t                e;              /* eligible time */
  76         uint64_t                vt;             /* virtual time */
  77         uint64_t                f;              /* fit time for upper-limit */
  78
  79         /* info helpful for debugging */
  80         uint64_t                initvt;         /* init virtual time */
  81         uint64_t                vtoff;          /* cl_vt_ipoff */
  82         uint64_t                cvtmax;         /* cl_maxvt */
  83         uint64_t                myf;            /* cl_myf */
  84         uint64_t                cfmin;          /* cl_mincf */
  85         uint64_t                cvtmin;         /* cl_mincvt */
  86         uint64_t                myfadj;         /* cl_myfadj */
  87         uint64_t                vtadj;          /* cl_vtadj */
  88         uint64_t                cur_time;
  89         uint32_t                machclk_freq;
  90
  91         u_int                   qlength;
  92         u_int                   qlimit;
  93         struct pktcntr          xmit_cnt;
  94         struct pktcntr          drop_cnt;
  95         u_int                   period;
  96
  97         u_int                   vtperiod;       /* vt period sequence no */
  98         u_int                   parentperiod;   /* parent's vt period seqno */
  99         int                     nactive;        /* number of active children */
 100
 101         /* red and rio related info */
 102         int                     qtype;
 103         struct redstats         red[3];
 104 };
 105
 106 #ifdef _KERNEL
 107 /*
 108  * kernel internal service curve representation
 109  *      coordinates are given by 64 bit unsigned integers.
 110  *      x-axis: unit is clock count.  for the intel x86 architecture,
 111  *              the raw Pentium TSC (Timestamp Counter) value is used.
 112  *              virtual time is also calculated in this time scale.
 113  *      y-axis: unit is byte.
 114  *
 115  *      the service curve parameters are converted to the internal
 116  *      representation.
 117  *      the slope values are scaled to avoid overflow.
 118  *      the inverse slope values as well as the y-projection of the 1st
 119  *      segment are kept in order to to avoid 64-bit divide operations
 120  *      that are expensive on 32-bit architectures.
 121  *
 122  *  note: Intel Pentium TSC never wraps around in several thousands of years.
 123  *      x-axis doesn't wrap around for 1089 years with 1GHz clock.
 124  *      y-axis doesn't wrap around for 4358 years with 1Gbps bandwidth.
 125  */
 126
 127 /* kernel internal representation of a service curve */
 128 struct internal_sc {
 129         uint64_t        sm1;    /* scaled slope of the 1st segment */
 130         uint64_t        ism1;   /* scaled inverse-slope of the 1st segment */
 131         uint64_t        dx;     /* the x-projection of the 1st segment */
 132         uint64_t        dy;     /* the y-projection of the 1st segment */
 133         uint64_t        sm2;    /* scaled slope of the 2nd segment */
 134         uint64_t        ism2;   /* scaled inverse-slope of the 2nd segment */
 135 };
 136
 137 /* runtime service curve */
 138 struct runtime_sc {
 139         uint64_t        x;      /* current starting position on x-axis */
 140         uint64_t        y;      /* current starting position on x-axis */
 141         uint64_t        sm1;    /* scaled slope of the 1st segment */
 142         uint64_t        ism1;   /* scaled inverse-slope of the 1st segment */
 143         uint64_t        dx;     /* the x-projection of the 1st segment */
 144         uint64_t        dy;     /* the y-projection of the 1st segment */
 145         uint64_t        sm2;    /* scaled slope of the 2nd segment */
 146         uint64_t        ism2;   /* scaled inverse-slope of the 2nd segment */
 147 };
 148
 149 /* for TAILQ based ellist and actlist implementation */
 150 struct hfsc_class;
 151 typedef TAILQ_HEAD(_eligible, hfsc_class) ellist_t;
 152 typedef TAILQ_ENTRY(hfsc_class) elentry_t;
 153 typedef TAILQ_HEAD(_active, hfsc_class) actlist_t;
 154 typedef TAILQ_ENTRY(hfsc_class) actentry_t;
 155 #define ellist_first(s)         TAILQ_FIRST(s)
 156 #define actlist_first(s)        TAILQ_FIRST(s)
 157 #define actlist_last(s)         TAILQ_LAST(s, _active)
 158
 159 struct hfsc_class {
 160         u_int           cl_id;          /* class id (just for debug) */
 161         uint32_t        cl_handle;      /* class handle */
 162         struct hfsc_if  *cl_hif;        /* back pointer to struct hfsc_if */
 163         int             cl_flags;       /* misc flags */
 164
 165         struct hfsc_class *cl_parent;   /* parent class */
 166         struct hfsc_class *cl_siblings; /* sibling classes */
 167         struct hfsc_class *cl_children; /* child classes */
 168
 169         class_queue_t   *cl_q;          /* class queue structure */
 170         struct red      *cl_red;        /* RED state */
 171         struct altq_pktattr *cl_pktattr; /* saved header used by ECN */
 172
 173         uint64_t        cl_total;       /* total work in bytes */
 174         uint64_t        cl_cumul;       /* cumulative work in bytes
 175                                            done by real-time criteria */
 176         uint64_t        cl_d;           /* deadline */
 177         uint64_t        cl_e;           /* eligible time */
 178         uint64_t        cl_vt;          /* virtual time */
 179         uint64_t        cl_f;           /* time when this class will fit for
 180                                            link-sharing, max(myf, cfmin) */
 181         uint64_t        cl_myf;         /* my fit-time (as calculated from this
 182                                            class's own upperlimit curve) */
 183         uint64_t        cl_myfadj;      /* my fit-time adjustment
 184                                            (to cancel history dependence) */
 185         uint64_t        cl_cfmin;       /* earliest children's fit-time (used
 186                                            with cl_myf to obtain cl_f) */
 187         uint64_t        cl_cvtmin;      /* minimal virtual time among the
 188                                            children fit for link-sharing
 189                                            (monotonic within a period) */
 190         uint64_t        cl_vtadj;       /* intra-period cumulative vt
 191                                            adjustment */
 192         uint64_t        cl_vtoff;       /* inter-period cumulative vt offset */
 193         uint64_t        cl_cvtmax;      /* max child's vt in the last period */
 194
 195         uint64_t        cl_initvt;      /* init virtual time (for debugging) */
 196
 197         struct internal_sc *cl_rsc;     /* internal real-time service curve */
 198         struct internal_sc *cl_fsc;     /* internal fair service curve */
 199         struct internal_sc *cl_usc;     /* internal upperlimit service curve */
 200         struct runtime_sc  cl_deadline; /* deadline curve */
 201         struct runtime_sc  cl_eligible; /* eligible curve */
 202         struct runtime_sc  cl_virtual;  /* virtual curve */
 203         struct runtime_sc  cl_ulimit;   /* upperlimit curve */
 204
 205         u_int           cl_vtperiod;    /* vt period sequence no */
 206         u_int           cl_parentperiod;  /* parent's vt period seqno */
 207         int             cl_nactive;     /* number of active children */
 208         actlist_t       *cl_actc;       /* active children list */
 209
 210         actentry_t      cl_actlist;     /* active children list entry */
 211         elentry_t       cl_ellist;      /* eligible list entry */
 212
 213         struct {
 214                 struct pktcntr  xmit_cnt;
 215                 struct pktcntr  drop_cnt;
 216                 u_int period;
 217         } cl_stats;
 218 };
 219
 220 /*
 221  * hfsc interface state
 222  */
 223 struct hfsc_if {
 224         struct hfsc_if          *hif_next;      /* interface state list */
 225         struct ifaltq           *hif_ifq;       /* backpointer to ifaltq */
 226         struct hfsc_class       *hif_rootclass;         /* root class */
 227         struct hfsc_class       *hif_defaultclass;      /* default class */
 228         struct hfsc_class       *hif_class_tbl[HFSC_MAX_CLASSES];
 229         struct hfsc_class       *hif_pollcache; /* cache for poll operation */
 230
 231         u_int   hif_classes;                    /* # of classes in the tree */
 232         u_int   hif_packets;                    /* # of packets in the tree */
 233         u_int   hif_classid;                    /* class id sequence number */
 234
 235         ellist_t *hif_eligible;                 /* eligible list */
 236 };
 237
 238 #endif /* _KERNEL */
 239
 240 #endif /* _ALTQ_ALTQ_HFSC_H_ */