sbin/pfctl/missing/altq/altq_hfsc.h

   1 /*      $FreeBSD$       */
   2 /*      $KAME: altq_hfsc.h,v 1.10 2003/07/10 12:07:48 kjc 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, and that
  12  * both notices appear in supporting documentation, and that credit
  13  * is given to Carnegie Mellon University in all publications reporting
  14  * on direct or indirect use of this code or its derivatives.
  15  *
  16  * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF
  17  * WHICH MAY HAVE SERIOUS CONSEQUENCES.  CARNEGIE MELLON PROVIDES THIS
  18  * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED
  19  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  21  * DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
  22  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
  24  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  25  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  26  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
  28  * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
  29  * DAMAGE.
  30  *
  31  * Carnegie Mellon encourages (but does not require) users of this
  32  * software to return any improvements or extensions that they make,
  33  * and to grant Carnegie Mellon the rights to redistribute these
  34  * changes without encumbrance.
  35  */
  36 #ifndef _ALTQ_ALTQ_HFSC_H_
  37 #define _ALTQ_ALTQ_HFSC_H_
  38
  39 #include <altq/altq.h>
  40 #include <altq/altq_classq.h>
  41 #include <altq/altq_red.h>
  42 #include <altq/altq_rio.h>
  43
  44 #ifdef __cplusplus
  45 extern "C" {
  46 #endif
  47
  48 struct service_curve {
  49         u_int   m1;     /* slope of the first segment in bits/sec */
  50         u_int   d;      /* the x-projection of the first segment in msec */
  51         u_int   m2;     /* slope of the second segment in bits/sec */
  52 };
  53
  54 /* special class handles */
  55 #define HFSC_NULLCLASS_HANDLE   0
  56 #define HFSC_ROOTCLASS_HANDLE   1
  57 #define HFSC_MAX_CLASSES        64
  58
  59 /* hfsc class flags */
  60 #define HFCF_RED                0x0001  /* use RED */
  61 #define HFCF_ECN                0x0002  /* use RED/ECN */
  62 #define HFCF_RIO                0x0004  /* use RIO */
  63 #define HFCF_CLEARDSCP          0x0010  /* clear diffserv codepoint */
  64 #define HFCF_DEFAULTCLASS       0x1000  /* default class */
  65
  66 /* service curve types */
  67 #define HFSC_REALTIMESC         1
  68 #define HFSC_LINKSHARINGSC      2
  69 #define HFSC_UPPERLIMITSC       4
  70 #define HFSC_DEFAULTSC          (HFSC_REALTIMESC|HFSC_LINKSHARINGSC)
  71
  72 struct hfsc_classstats {
  73         u_int                   class_id;
  74         u_int32_t               class_handle;
  75         struct service_curve    rsc;
  76         struct service_curve    fsc;
  77         struct service_curve    usc;    /* upper limit service curve */
  78
  79         u_int64_t               total;  /* total work in bytes */
  80         u_int64_t               cumul;  /* cumulative work in bytes
  81                                            done by real-time criteria */
  82         u_int64_t               d;              /* deadline */
  83         u_int64_t               e;              /* eligible time */
  84         u_int64_t               vt;             /* virtual time */
  85         u_int64_t               f;              /* fit time for upper-limit */
  86
  87         /* info helpful for debugging */
  88         u_int64_t               initvt;         /* init virtual time */
  89         u_int64_t               vtoff;          /* cl_vt_ipoff */
  90         u_int64_t               cvtmax;         /* cl_maxvt */
  91         u_int64_t               myf;            /* cl_myf */
  92         u_int64_t               cfmin;          /* cl_mincf */
  93         u_int64_t               cvtmin;         /* cl_mincvt */
  94         u_int64_t               myfadj;         /* cl_myfadj */
  95         u_int64_t               vtadj;          /* cl_vtadj */
  96         u_int64_t               cur_time;
  97         u_int32_t               machclk_freq;
  98
  99         u_int                   qlength;
 100         u_int                   qlimit;
 101         struct pktcntr          xmit_cnt;
 102         struct pktcntr          drop_cnt;
 103         u_int                   period;
 104
 105         u_int                   vtperiod;       /* vt period sequence no */
 106         u_int                   parentperiod;   /* parent's vt period seqno */
 107         int                     nactive;        /* number of active children */
 108
 109         /* red and rio related info */
 110         int                     qtype;
 111         struct redstats         red[3];
 112 };
 113
 114 #ifdef ALTQ3_COMPAT
 115 struct hfsc_interface {
 116         char    hfsc_ifname[IFNAMSIZ];  /* interface name (e.g., fxp0) */
 117 };
 118
 119 struct hfsc_attach {
 120         struct hfsc_interface   iface;
 121         u_int                   bandwidth;  /* link bandwidth in bits/sec */
 122 };
 123
 124 struct hfsc_add_class {
 125         struct hfsc_interface   iface;
 126         u_int32_t               parent_handle;
 127         struct service_curve    service_curve;
 128         int                     qlimit;
 129         int                     flags;
 130
 131         u_int32_t               class_handle;  /* return value */
 132 };
 133
 134 struct hfsc_delete_class {
 135         struct hfsc_interface   iface;
 136         u_int32_t               class_handle;
 137 };
 138
 139 struct hfsc_modify_class {
 140         struct hfsc_interface   iface;
 141         u_int32_t               class_handle;
 142         struct service_curve    service_curve;
 143         int                     sctype;
 144 };
 145
 146 struct hfsc_add_filter {
 147         struct hfsc_interface   iface;
 148         u_int32_t               class_handle;
 149         struct flow_filter      filter;
 150
 151         u_long                  filter_handle;  /* return value */
 152 };
 153
 154 struct hfsc_delete_filter {
 155         struct hfsc_interface   iface;
 156         u_long                  filter_handle;
 157 };
 158
 159 struct hfsc_class_stats {
 160         struct hfsc_interface   iface;
 161         int                     nskip;          /* skip # of classes */
 162         int                     nclasses;       /* # of class stats (WR) */
 163         u_int64_t               cur_time;       /* current time */
 164         u_int32_t               machclk_freq;   /* machine clock frequency */
 165         u_int                   hif_classes;    /* # of classes in the tree */
 166         u_int                   hif_packets;    /* # of packets in the tree */
 167         struct hfsc_classstats  *stats;         /* pointer to stats array */
 168 };
 169
 170 #define HFSC_IF_ATTACH          _IOW('Q', 1, struct hfsc_attach)
 171 #define HFSC_IF_DETACH          _IOW('Q', 2, struct hfsc_interface)
 172 #define HFSC_ENABLE             _IOW('Q', 3, struct hfsc_interface)
 173 #define HFSC_DISABLE            _IOW('Q', 4, struct hfsc_interface)
 174 #define HFSC_CLEAR_HIERARCHY    _IOW('Q', 5, struct hfsc_interface)
 175 #define HFSC_ADD_CLASS          _IOWR('Q', 7, struct hfsc_add_class)
 176 #define HFSC_DEL_CLASS          _IOW('Q', 8, struct hfsc_delete_class)
 177 #define HFSC_MOD_CLASS          _IOW('Q', 9, struct hfsc_modify_class)
 178 #define HFSC_ADD_FILTER         _IOWR('Q', 10, struct hfsc_add_filter)
 179 #define HFSC_DEL_FILTER         _IOW('Q', 11, struct hfsc_delete_filter)
 180 #define HFSC_GETSTATS           _IOWR('Q', 12, struct hfsc_class_stats)
 181 #endif /* ALTQ3_COMPAT */
 182
 183 #ifdef _KERNEL
 184 /*
 185  * kernel internal service curve representation
 186  *      coordinates are given by 64 bit unsigned integers.
 187  *      x-axis: unit is clock count.  for the intel x86 architecture,
 188  *              the raw Pentium TSC (Timestamp Counter) value is used.
 189  *              virtual time is also calculated in this time scale.
 190  *      y-axis: unit is byte.
 191  *
 192  *      the service curve parameters are converted to the internal
 193  *      representation.
 194  *      the slope values are scaled to avoid overflow.
 195  *      the inverse slope values as well as the y-projection of the 1st
 196  *      segment are kept in order to to avoid 64-bit divide operations
 197  *      that are expensive on 32-bit architectures.
 198  *
 199  *  note: Intel Pentium TSC never wraps around in several thousands of years.
 200  *      x-axis doesn't wrap around for 1089 years with 1GHz clock.
 201  *      y-axis doesn't wrap around for 4358 years with 1Gbps bandwidth.
 202  */
 203
 204 /* kernel internal representation of a service curve */
 205 struct internal_sc {
 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 /* runtime service curve */
 215 struct runtime_sc {
 216         u_int64_t       x;      /* current starting position on x-axis */
 217         u_int64_t       y;      /* current starting position on x-axis */
 218         u_int64_t       sm1;    /* scaled slope of the 1st segment */
 219         u_int64_t       ism1;   /* scaled inverse-slope of the 1st segment */
 220         u_int64_t       dx;     /* the x-projection of the 1st segment */
 221         u_int64_t       dy;     /* the y-projection of the 1st segment */
 222         u_int64_t       sm2;    /* scaled slope of the 2nd segment */
 223         u_int64_t       ism2;   /* scaled inverse-slope of the 2nd segment */
 224 };
 225
 226 /* for TAILQ based ellist and actlist implementation */
 227 struct hfsc_class;
 228 typedef TAILQ_HEAD(_eligible, hfsc_class) ellist_t;
 229 typedef TAILQ_ENTRY(hfsc_class) elentry_t;
 230 typedef TAILQ_HEAD(_active, hfsc_class) actlist_t;
 231 typedef TAILQ_ENTRY(hfsc_class) actentry_t;
 232 #define ellist_first(s)         TAILQ_FIRST(s)
 233 #define actlist_first(s)        TAILQ_FIRST(s)
 234 #define actlist_last(s)         TAILQ_LAST(s, _active)
 235
 236 struct hfsc_class {
 237         u_int           cl_id;          /* class id (just for debug) */
 238         u_int32_t       cl_handle;      /* class handle */
 239         struct hfsc_if  *cl_hif;        /* back pointer to struct hfsc_if */
 240         int             cl_flags;       /* misc flags */
 241
 242         struct hfsc_class *cl_parent;   /* parent class */
 243         struct hfsc_class *cl_siblings; /* sibling classes */
 244         struct hfsc_class *cl_children; /* child classes */
 245
 246         class_queue_t   *cl_q;          /* class queue structure */
 247         struct red      *cl_red;        /* RED state */
 248         struct altq_pktattr *cl_pktattr; /* saved header used by ECN */
 249
 250         u_int64_t       cl_total;       /* total work in bytes */
 251         u_int64_t       cl_cumul;       /* cumulative work in bytes
 252                                            done by real-time criteria */
 253         u_int64_t       cl_d;           /* deadline */
 254         u_int64_t       cl_e;           /* eligible time */
 255         u_int64_t       cl_vt;          /* virtual time */
 256         u_int64_t       cl_f;           /* time when this class will fit for
 257                                            link-sharing, max(myf, cfmin) */
 258         u_int64_t       cl_myf;         /* my fit-time (as calculated from this
 259                                            class's own upperlimit curve) */
 260         u_int64_t       cl_myfadj;      /* my fit-time adjustment
 261                                            (to cancel history dependence) */
 262         u_int64_t       cl_cfmin;       /* earliest children's fit-time (used
 263                                            with cl_myf to obtain cl_f) */
 264         u_int64_t       cl_cvtmin;      /* minimal virtual time among the
 265                                            children fit for link-sharing
 266                                            (monotonic within a period) */
 267         u_int64_t       cl_vtadj;       /* intra-period cumulative vt
 268                                            adjustment */
 269         u_int64_t       cl_vtoff;       /* inter-period cumulative vt offset */
 270         u_int64_t       cl_cvtmax;      /* max child's vt in the last period */
 271
 272         u_int64_t       cl_initvt;      /* init virtual time (for debugging) */
 273
 274         struct internal_sc *cl_rsc;     /* internal real-time service curve */
 275         struct internal_sc *cl_fsc;     /* internal fair service curve */
 276         struct internal_sc *cl_usc;     /* internal upperlimit service curve */
 277         struct runtime_sc  cl_deadline; /* deadline curve */
 278         struct runtime_sc  cl_eligible; /* eligible curve */
 279         struct runtime_sc  cl_virtual;  /* virtual curve */
 280         struct runtime_sc  cl_ulimit;   /* upperlimit curve */
 281
 282         u_int           cl_vtperiod;    /* vt period sequence no */
 283         u_int           cl_parentperiod;  /* parent's vt period seqno */
 284         int             cl_nactive;     /* number of active children */
 285         actlist_t       *cl_actc;       /* active children list */
 286
 287         actentry_t      cl_actlist;     /* active children list entry */
 288         elentry_t       cl_ellist;      /* eligible list entry */
 289
 290         struct {
 291                 struct pktcntr  xmit_cnt;
 292                 struct pktcntr  drop_cnt;
 293                 u_int period;
 294         } cl_stats;
 295 };
 296
 297 /*
 298  * hfsc interface state
 299  */
 300 struct hfsc_if {
 301         struct hfsc_if          *hif_next;      /* interface state list */
 302         struct ifaltq           *hif_ifq;       /* backpointer to ifaltq */
 303         struct hfsc_class       *hif_rootclass;         /* root class */
 304         struct hfsc_class       *hif_defaultclass;      /* default class */
 305         struct hfsc_class       *hif_class_tbl[HFSC_MAX_CLASSES];
 306         struct hfsc_class       *hif_pollcache; /* cache for poll operation */
 307
 308         u_int   hif_classes;                    /* # of classes in the tree */
 309         u_int   hif_packets;                    /* # of packets in the tree */
 310         u_int   hif_classid;                    /* class id sequence number */
 311
 312         ellist_t *hif_eligible;                 /* eligible list */
 313
 314 #ifdef ALTQ3_CLFIER_COMPAT
 315         struct acc_classifier   hif_classifier;
 316 #endif
 317 };
 318
 319 #endif /* _KERNEL */
 320
 321 #ifdef __cplusplus
 322 }
 323 #endif
 324
 325 #endif /* _ALTQ_ALTQ_HFSC_H_ */