sys/net/altq/altq_hfsc.h

   1 /*-
   2  * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved.
   3  *
   4  * Permission to use, copy, modify, and distribute this software and
   5  * its documentation is hereby granted (including for commercial or
   6  * for-profit use), provided that both the copyright notice and this
   7  * permission notice appear in all copies of the software, derivative
   8  * works, or modified versions, and any portions thereof.
   9  *
  10  * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF
  11  * WHICH MAY HAVE SERIOUS CONSEQUENCES.  CARNEGIE MELLON PROVIDES THIS
  12  * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED
  13  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  14  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  15  * DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
  16  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  17  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
  18  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  19  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  20  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
  22  * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
  23  * DAMAGE.
  24  *
  25  * Carnegie Mellon encourages (but does not require) users of this
  26  * software to return any improvements or extensions that they make,
  27  * and to grant Carnegie Mellon the rights to redistribute these
  28  * changes without encumbrance.
  29  *
  30  * $KAME: altq_hfsc.h,v 1.12 2003/12/05 05:40:46 kjc Exp $
  31  * $FreeBSD$
  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_codel.h>
  39 #include <net/altq/altq_red.h>
  40 #include <net/altq/altq_rio.h>
  41
  42 #ifdef __cplusplus
  43 extern "C" {
  44 #endif
  45
  46 struct service_curve_v0 {
  47         u_int   m1;     /* slope of the first segment in bits/sec */
  48         u_int   d;      /* the x-projection of the first segment in msec */
  49         u_int   m2;     /* slope of the second segment in bits/sec */
  50 };
  51
  52 struct service_curve_v1 {
  53         u_int64_t       m1;   /* slope of the first segment in bits/sec */
  54         u_int   d;            /* the x-projection of the first segment in msec */
  55         u_int64_t       m2;   /* slope of the second segment in bits/sec */
  56 };
  57
  58 /* Latest version of struct service_curve_vX */
  59 #define HFSC_SERVICE_CURVE_VERSION      1
  60
  61 /* special class handles */
  62 #define HFSC_NULLCLASS_HANDLE   0
  63 #define HFSC_MAX_CLASSES        64
  64
  65 /* hfsc class flags */
  66 #define HFCF_RED                0x0001  /* use RED */
  67 #define HFCF_ECN                0x0002  /* use RED/ECN */
  68 #define HFCF_RIO                0x0004  /* use RIO */
  69 #define HFCF_CODEL              0x0008  /* use CoDel */
  70 #define HFCF_CLEARDSCP          0x0010  /* clear diffserv codepoint */
  71 #define HFCF_DEFAULTCLASS       0x1000  /* default class */
  72
  73 /* service curve types */
  74 #define HFSC_REALTIMESC         1
  75 #define HFSC_LINKSHARINGSC      2
  76 #define HFSC_UPPERLIMITSC       4
  77 #define HFSC_DEFAULTSC          (HFSC_REALTIMESC|HFSC_LINKSHARINGSC)
  78
  79 struct hfsc_classstats_v0 {
  80         u_int                   class_id;
  81         u_int32_t               class_handle;
  82         struct service_curve_v0 rsc;
  83         struct service_curve_v0 fsc;
  84         struct service_curve_v0 usc;    /* upper limit service curve */
  85
  86         u_int64_t               total;  /* total work in bytes */
  87         u_int64_t               cumul;  /* cumulative work in bytes
  88                                            done by real-time criteria */
  89         u_int64_t               d;              /* deadline */
  90         u_int64_t               e;              /* eligible time */
  91         u_int64_t               vt;             /* virtual time */
  92         u_int64_t               f;              /* fit time for upper-limit */
  93
  94         /* info helpful for debugging */
  95         u_int64_t               initvt;         /* init virtual time */
  96         u_int64_t               vtoff;          /* cl_vt_ipoff */
  97         u_int64_t               cvtmax;         /* cl_maxvt */
  98         u_int64_t               myf;            /* cl_myf */
  99         u_int64_t               cfmin;          /* cl_mincf */
 100         u_int64_t               cvtmin;         /* cl_mincvt */
 101         u_int64_t               myfadj;         /* cl_myfadj */
 102         u_int64_t               vtadj;          /* cl_vtadj */
 103         u_int64_t               cur_time;
 104         u_int32_t               machclk_freq;
 105
 106         u_int                   qlength;
 107         u_int                   qlimit;
 108         struct pktcntr          xmit_cnt;
 109         struct pktcntr          drop_cnt;
 110         u_int                   period;
 111
 112         u_int                   vtperiod;       /* vt period sequence no */
 113         u_int                   parentperiod;   /* parent's vt period seqno */
 114         int                     nactive;        /* number of active children */
 115
 116         /* codel, red and rio related info */
 117         int                     qtype;
 118         struct redstats         red[3];
 119         struct codel_stats      codel;
 120 };
 121
 122 struct hfsc_classstats_v1 {
 123         u_int                   class_id;
 124         u_int32_t               class_handle;
 125         struct service_curve_v1 rsc;
 126         struct service_curve_v1 fsc;
 127         struct service_curve_v1 usc;    /* upper limit service curve */
 128
 129         u_int64_t               total;  /* total work in bytes */
 130         u_int64_t               cumul;  /* cumulative work in bytes
 131                                            done by real-time criteria */
 132         u_int64_t               d;              /* deadline */
 133         u_int64_t               e;              /* eligible time */
 134         u_int64_t               vt;             /* virtual time */
 135         u_int64_t               f;              /* fit time for upper-limit */
 136
 137         /* info helpful for debugging */
 138         u_int64_t               initvt;         /* init virtual time */
 139         u_int64_t               vtoff;          /* cl_vt_ipoff */
 140         u_int64_t               cvtmax;         /* cl_maxvt */
 141         u_int64_t               myf;            /* cl_myf */
 142         u_int64_t               cfmin;          /* cl_mincf */
 143         u_int64_t               cvtmin;         /* cl_mincvt */
 144         u_int64_t               myfadj;         /* cl_myfadj */
 145         u_int64_t               vtadj;          /* cl_vtadj */
 146         u_int64_t               cur_time;
 147         u_int32_t               machclk_freq;
 148
 149         u_int                   qlength;
 150         u_int                   qlimit;
 151         struct pktcntr          xmit_cnt;
 152         struct pktcntr          drop_cnt;
 153         u_int                   period;
 154
 155         u_int                   vtperiod;       /* vt period sequence no */
 156         u_int                   parentperiod;   /* parent's vt period seqno */
 157         int                     nactive;        /* number of active children */
 158
 159         /* codel, red and rio related info */
 160         int                     qtype;
 161         struct redstats         red[3];
 162         struct codel_stats      codel;
 163 };
 164
 165 /*
 166  * HFSC_STATS_VERSION is defined in altq.h to work around issues stemming
 167  * from mixing of public-API and internal bits in each scheduler-specific
 168  * header.
 169  */
 170
 171 #ifdef _KERNEL
 172 /*
 173  * kernel internal service curve representation
 174  *      coordinates are given by 64 bit unsigned integers.
 175  *      x-axis: unit is clock count.  for the intel x86 architecture,
 176  *              the raw Pentium TSC (Timestamp Counter) value is used.
 177  *              virtual time is also calculated in this time scale.
 178  *      y-axis: unit is byte.
 179  *
 180  *      the service curve parameters are converted to the internal
 181  *      representation.
 182  *      the slope values are scaled to avoid overflow.
 183  *      the inverse slope values as well as the y-projection of the 1st
 184  *      segment are kept in order to avoid 64-bit divide operations
 185  *      that are expensive on 32-bit architectures.
 186  *
 187  *  note: Intel Pentium TSC never wraps around in several thousands of years.
 188  *      x-axis doesn't wrap around for 1089 years with 1GHz clock.
 189  *      y-axis doesn't wrap around for 4358 years with 1Gbps bandwidth.
 190  */
 191
 192 /* kernel internal representation of a service curve */
 193 struct internal_sc {
 194         u_int64_t       sm1;    /* scaled slope of the 1st segment */
 195         u_int64_t       ism1;   /* scaled inverse-slope of the 1st segment */
 196         u_int64_t       dx;     /* the x-projection of the 1st segment */
 197         u_int64_t       dy;     /* the y-projection of the 1st segment */
 198         u_int64_t       sm2;    /* scaled slope of the 2nd segment */
 199         u_int64_t       ism2;   /* scaled inverse-slope of the 2nd segment */
 200 };
 201
 202 /* runtime service curve */
 203 struct runtime_sc {
 204         u_int64_t       x;      /* current starting position on x-axis */
 205         u_int64_t       y;      /* current starting position on x-axis */
 206         u_int64_t       sm1;    /* scaled slope of the 1st segment */
 207         u_int64_t       ism1;   /* scaled inverse-slope of the 1st segment */
 208         u_int64_t       dx;     /* the x-projection of the 1st segment */
 209         u_int64_t       dy;     /* the y-projection of the 1st segment */
 210         u_int64_t       sm2;    /* scaled slope of the 2nd segment */
 211         u_int64_t       ism2;   /* scaled inverse-slope of the 2nd segment */
 212 };
 213
 214 struct hfsc_class {
 215         u_int           cl_id;          /* class id (just for debug) */
 216         u_int           cl_slot;        /* slot in hif class table */
 217         u_int32_t       cl_handle;      /* class handle */
 218         struct hfsc_if  *cl_hif;        /* back pointer to struct hfsc_if */
 219         int             cl_flags;       /* misc flags */
 220
 221         struct hfsc_class *cl_parent;   /* parent class */
 222         struct hfsc_class *cl_siblings; /* sibling classes */
 223         struct hfsc_class *cl_children; /* child classes */
 224
 225         class_queue_t   *cl_q;          /* class queue structure */
 226         union {
 227                 struct red      *cl_red;        /* RED state */
 228                 struct codel    *cl_codel;      /* CoDel state */
 229         } cl_aqm;
 230 #define cl_red                  cl_aqm.cl_red
 231 #define cl_codel                cl_aqm.cl_codel
 232         struct altq_pktattr *cl_pktattr; /* saved header used by ECN */
 233
 234         u_int64_t       cl_total;       /* total work in bytes */
 235         u_int64_t       cl_cumul;       /* cumulative work in bytes
 236                                            done by real-time criteria */
 237         u_int64_t       cl_d;           /* deadline */
 238         u_int64_t       cl_e;           /* eligible time */
 239         u_int64_t       cl_vt;          /* virtual time */
 240         u_int64_t       cl_f;           /* time when this class will fit for
 241                                            link-sharing, max(myf, cfmin) */
 242         u_int64_t       cl_myf;         /* my fit-time (as calculated from this
 243                                            class's own upperlimit curve) */
 244         u_int64_t       cl_myfadj;      /* my fit-time adjustment
 245                                            (to cancel history dependence) */
 246         u_int64_t       cl_cfmin;       /* earliest children's fit-time (used
 247                                            with cl_myf to obtain cl_f) */
 248         u_int64_t       cl_cvtmin;      /* minimal virtual time among the
 249                                            children fit for link-sharing
 250                                            (monotonic within a period) */
 251         u_int64_t       cl_vtadj;       /* intra-period cumulative vt
 252                                            adjustment */
 253         u_int64_t       cl_vtoff;       /* inter-period cumulative vt offset */
 254         u_int64_t       cl_cvtmax;      /* max child's vt in the last period */
 255
 256         u_int64_t       cl_initvt;      /* init virtual time (for debugging) */
 257
 258         struct internal_sc *cl_rsc;     /* internal real-time service curve */
 259         struct internal_sc *cl_fsc;     /* internal fair service curve */
 260         struct internal_sc *cl_usc;     /* internal upperlimit service curve */
 261         struct runtime_sc  cl_deadline; /* deadline curve */
 262         struct runtime_sc  cl_eligible; /* eligible curve */
 263         struct runtime_sc  cl_virtual;  /* virtual curve */
 264         struct runtime_sc  cl_ulimit;   /* upperlimit curve */
 265
 266         u_int           cl_vtperiod;    /* vt period sequence no */
 267         u_int           cl_parentperiod;  /* parent's vt period seqno */
 268         int             cl_nactive;     /* number of active children */
 269
 270         TAILQ_HEAD(acthead, hfsc_class) cl_actc; /* active children list */
 271         TAILQ_ENTRY(hfsc_class) cl_actlist;     /* active children list entry */
 272         TAILQ_ENTRY(hfsc_class) cl_ellist;      /* eligible list entry */
 273
 274         struct {
 275                 struct pktcntr  xmit_cnt;
 276                 struct pktcntr  drop_cnt;
 277                 u_int period;
 278         } cl_stats;
 279 };
 280
 281 /*
 282  * hfsc interface state
 283  */
 284 struct hfsc_if {
 285         struct hfsc_if          *hif_next;      /* interface state list */
 286         struct ifaltq           *hif_ifq;       /* backpointer to ifaltq */
 287         struct hfsc_class       *hif_rootclass;         /* root class */
 288         struct hfsc_class       *hif_defaultclass;      /* default class */
 289         struct hfsc_class       *hif_class_tbl[HFSC_MAX_CLASSES];
 290         struct hfsc_class       *hif_pollcache; /* cache for poll operation */
 291
 292         u_int   hif_classes;                    /* # of classes in the tree */
 293         u_int   hif_packets;                    /* # of packets in the tree */
 294         u_int   hif_classid;                    /* class id sequence number */
 295
 296         TAILQ_HEAD(elighead, hfsc_class) hif_eligible; /* eligible list */
 297
 298 #ifdef ALTQ3_CLFIER_COMPAT
 299         struct acc_classifier   hif_classifier;
 300 #endif
 301 };
 302
 303 /*
 304  * Kernel code always wants the latest version - avoid a bunch of renames in
 305  * the code to the current latest versioned name.
 306  */
 307 #define service_curve   __CONCAT(service_curve_v, HFSC_SERVICE_CURVE_VERSION)
 308
 309 #else /* _KERNEL */
 310
 311 #ifdef PFIOC_USE_LATEST
 312 /*
 313  * Maintaining in-tree consumers of the ioctl interface is easier when that
 314  * code can be written in terms old names that refer to the latest interface
 315  * version as that reduces the required changes in the consumers to those
 316  * that are functionally necessary to accommodate a new interface version.
 317  */
 318 #define hfsc_classstats __CONCAT(hfsc_classstats_v, HFSC_STATS_VERSION)
 319 #define service_curve   __CONCAT(service_curve_v, HFSC_SERVICE_CURVE_VERSION)
 320
 321 #else
 322 /*
 323  * When building out-of-tree code that is written for the old interface,
 324  * such as may exist in ports for example, resolve the old struct tags to
 325  * the v0 versions.
 326  */
 327 #define hfsc_classstats __CONCAT(hfsc_classstats_v, 0)
 328 #define service_curve   __CONCAT(service_curve_v, 0)
 329
 330 #endif /* PFIOC_USE_LATEST */
 331
 332 #endif /* _KERNEL */
 333
 334 #ifdef __cplusplus
 335 }
 336 #endif
 337
 338 #endif /* _ALTQ_ALTQ_HFSC_H_ */